Problem overview
The method validPath receives the number of vertices n, a list of edges, a source vertex and a destination vertex. Vertices are labeled 0 to n - 1. Each edge is an int[] pair [u, v] joining two vertices, and it works in both directions. The method returns true when some chain of edges leads from source to destination, and false otherwise.
In the first example, n = 3 and the edges form a triangle: 0-1, 1-2 and 2-0. From vertex 0 you can reach 2 directly or through 1, so the answer is true. In the second example, vertices 0, 1 and 2 are joined together, and 3, 4 and 5 form a separate group. There is no way from 0 to 5, so the answer is false.
Approach: explore everything reachable from the source
A list of edges is hard to search directly, since finding the neighbors of one vertex would mean scanning every edge. So the first move is to rebuild the data as an adjacency list: for each vertex, the list of vertices it connects to. After that, "where can I go from here?" is a single lookup.
Then run a depth-first search (DFS) from source. DFS visits a vertex, then picks an unvisited neighbor and goes as deep as it can before backing up. Each vertex it reaches goes into a visited set. When the search ends, visited holds exactly the vertices connected to the source, so the answer is whether destination is in that set.
The visited set also keeps the search finite. Graphs have cycles, such as the triangle above. Without it, the search would go 0, then 1, then 2, then 0 again, forever.
Step by step
- Create the adjacency list as a
List<List<Integer>>and add an emptyArrayListfor each of thenvertices, so thatgraph.get(i)holds the neighbors of vertexi. - Create the
visitedset as aHashSet. Membership checks take constant time on average. - Loop over
edgeswith the variableedgeof typeint[]. The two endpoints areedge[0]andedge[1]. - Record the edge in both directions. Add
edge[1]to the list ofedge[0], andedge[0]to the list ofedge[1]. Skipping the second one would turn the graph into a directed one and miss paths that cross an edge backwards. - Run the search: call
dfs(source, graph, visited), a helper written next. It fillsvisited. - Return
visited.contains(destination), which already gives theboolean. - Write
dfsas aprivate voidmethod taking the currentnode, thegraphand thevisitedset. Every recursive call shares the same set. - Mark the node visited first, before looking at neighbors. Then a neighbor that leads back to this node already sees it as visited.
- Loop over
graph.get(node)with anintvariableadjacentNode, and recurse only into the neighbors that aren't invisitedyet.
The solution in Java
class Solution {
public boolean validPath(int n, List<int[]> edges, int source, int destination) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
Set<Integer> visited = new HashSet<>();
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
dfs(source, graph, visited);
return visited.contains(destination);
}
private void dfs(int node, List<List<Integer>> graph, Set<Integer> visited) {
visited.add(node);
for (int adjacentNode : graph.get(node)) {
if (!visited.contains(adjacentNode)) {
dfs(adjacentNode, graph, visited);
}
}
}
}
Java details worth a closer look:
- A list of lists is built in two steps.
new ArrayList<>()for the outer list creates an empty list. Each vertex's inner list must then be added separately. The diamond<>lets the compiler fill in the element type from the declaration. - Edges come as a
List<int[]>. Each element is an array, so the endpoints are read with brackets,edge[0], while the list itself is read withget. - Autoboxing. A
List<Integer>storesIntegerobjects.graph.get(edge[0]).add(edge[1])boxes theinton the way in, andfor (int adjacentNode : ...)unboxes on the way out. - Shared state through references. Java passes the reference to
visitedby value, so the caller and all recursive calls see the same set. That is whydfscan returnvoid. - Recursion depth. DFS goes one frame deeper for each vertex along a path. The constraints allow up to 200,000 vertices, and a graph that is one long chain can make the recursion deep enough to throw
StackOverflowError. This lesson's solution is fine for the lesson, but a long chain is the reason many programmers write DFS with an explicitArrayDequeused as a stack.
Complexity
Let m be the number of edges.
Time: O(n + m). Building the lists takes O(n) for the empty lists and O(m) for the edges. The search visits each vertex once and looks at each edge from both ends, so O(n + m) in total. Set operations take constant time on average.
Space: O(n + m). The adjacency list holds each edge twice, and the set and the recursion stack are at most n in size.
Edge cases and common mistakes
- Source equals destination. The source is added to
visitedbefore anything else, so the answer istrueeven with no edges. For example,n = 1, no edges andsource = destination = 0givestrue. - No edges and different vertices. Nothing is reachable, and the answer is
false. - Disconnected graph. The second example shows it: only the group of the source is ever visited.
- Adding each edge in one direction only. A path like
0, 1, 2built from edges[1,0]and[2,1]would then be missed. - Marking vertices visited too late. If a node is marked only after its neighbors have been explored, cycles cause endless recursion.
- Forgetting the inner lists. An
ArrayListstarts empty, sograph.get(i)throws anIndexOutOfBoundsExceptionuntil the loop has added the vertex lists.
Testing
n = 3,edges = [[0,1],[1,2],[2,0]],source = 0,destination = 2givestrue.n = 6,edges = [[0,1],[0,2],[3,5],[5,4],[4,3]],source = 0,destination = 5givesfalse.n = 1,edges = [],source = 0,destination = 0givestrue.