Start learning free

LESSON 559 OF 673 · GRAPHS

Find if Path Exists in Graph in Python: Depth-First Search

Practice O(V+E) Read the full explanation

You get an undirected graph with n vertices, labeled 0 to n - 1. Each entry edges[i] = [ui, vi] joins vertices ui and vi. You can follow an edge in both directions.

Return True if you can walk along edges from vertex source to vertex destination. Otherwise, return False. A vertex always reaches itself.

 

Example 1:

3 0 4 2 1
Input: n = 5, edges = [[3,0],[0,4],[4,2],[2,1],[1,4]], source = 3, destination = 1
Output: True
Explanation: The blue edges show the path 3 → 0 → 4 → 1.
The path 3 → 0 → 4 → 2 → 1 also works.

Example 2:

0 5 2 1 3 4
Input: n = 6, edges = [[0,5],[5,2],[1,3],[3,4]], source = 2, destination = 4
Output: False
Explanation: The graph has two separate parts.
From 2, you can only reach 5 and 0.
No edge leads to the part with 1, 3 and 4.

Example 3:

0 1 2
Input: n = 3, edges = [[1,2]], source = 0, destination = 0
Output: True
Explanation: Vertex 0 has no edges.
But source and destination are the same vertex.
The walk starts and ends right there.

 

Constraints:

  • 2 to 200,000 vertices.
  • At most 200,000 entries in edges.
  • Every vertex in edges is from 0 to n - 1. So are source and destination.
  • No edge joins a vertex to itself.
  • The same edge can be listed twice, for example as [1, 4] and [4, 1].
STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · GRAPHS

    Find If Path Exist In A Graph in Python, explained

    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 [u, v] connects two vertices in both directions. The method returns True if you can walk from source to destination along edges, and False otherwise.

    In the first example, n = 3 and the edges form a triangle: [[0, 1], [1, 2], [2, 0]]. From 0 you can reach 2 directly, or through 1, so the answer is True. In the second example, n = 6 with edges [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]]. Vertices 0, 1 and 2 form one group, and 3, 4 and 5 form another. No edge joins the groups, so there is no path from 0 to 5 and the answer is False.

    Approach: explore everything reachable from the source

    Checking every possible path would be wasteful. A simpler question is enough: which vertices can be reached from source? If destination is one of them, a path exists.

    Depth-first search (DFS) answers that question. Stand on a vertex, mark it as visited, then go to one unvisited neighbor and repeat from there. When a vertex has no unvisited neighbors left, the search backs up to the previous vertex and tries its next neighbor. In the end, the visited set holds every vertex connected to the source.

    Two things make this work. First, the graph needs an adjacency list, a map from each vertex to its neighbors, so the neighbors of a vertex are found without scanning all the edges. Second, the search needs the visited set. Without it, a cycle such as the triangle in the first example would send the search around forever: 0 to 1 to 2 and back to 0.

    On the first example, DFS from 0 visits 0, then its first neighbor 1, then 1's unvisited neighbor 2. The vertex 2 sees only visited neighbors, so the search backs out. The visited set is {0, 1, 2}, which contains the destination 2.

    Step by step

    1. Create the adjacency list. graph is a defaultdict(list), so reading a vertex that has no neighbors yet gives an empty list, not a KeyError.
    2. Create the visited set, visited, to remember reached vertices. Membership tests on a set take constant time on average.
    3. Loop over edges, with each pair in the variable edge.
    4. Record one direction: append edge[1] to the neighbors of edge[0].
    5. Record the other direction: append edge[0] to the neighbors of edge[1]. The graph is bi-directional, so a walk must be able to cross each edge both ways.
    6. Define the inner function dfs(node). It is nested inside validPath, so it reads graph and visited directly, and only the node needs to be passed in.
    7. Mark the node visited first. Marking before exploring means any neighbor that leads back finds this vertex already visited.
    8. Loop over the node's neighbors, with each one in adjacent_node.
    9. Recurse only on unvisited neighbors: if adjacent_node not in visited, call dfs on it.
    10. Start the search by calling dfs(source) in the body of validPath. Defining a function doesn't run it.
    11. Return whether destination is in visited. The expression destination in visited is already a boolean.

    The solution in Python

    from collections import defaultdict
    
    
    class Solution:
        def validPath(self, n, edges, source, destination) -> bool:
            graph = defaultdict(list)
            visited = set()
    
            # Build the graph
            for edge in edges:
                graph[edge[0]].append(edge[1])
                graph[edge[1]].append(edge[0])
    
            def dfs(node):
                visited.add(node)
                for adjacent_node in graph[node]:
                    if adjacent_node not in visited:
                        dfs(adjacent_node)
    
            dfs(source)
    
            return destination in visited
    

    The Python details worth a closer look:

    • defaultdict(list). When you read or write a missing key, it creates an empty list for that key first. That is why graph[edge[0]].append(...) works on a key seen for the first time. A side effect is that reading graph[node] for an isolated vertex also inserts an empty entry. That is harmless here.
    • A set, not {}. Empty braces {} create an empty dict. An empty set is written set().
    • Closures. dfs uses visited and graph from the enclosing method. Since it only calls visited.add and never assigns a new value to the name, it needs no nonlocal declaration.
    • Source equals destination. The search starts by adding source to visited, so validPath(1, [], 0, 0) returns True.
    • Recursion depth. Python allows about 1000 nested calls by default and then raises a RecursionError. A graph that is one long chain of a few thousand vertices makes dfs go that deep. For graphs like that, the same search is written with an explicit stack: a list used with append and pop, holding vertices still to explore.

    Complexity

    Time: O(n + e), where e is the number of edges. Building the graph touches each edge once. The search visits each vertex once, because a visited vertex is never expanded again, and it looks at each edge from both of its ends, so it examines every neighbor list entry once.

    Space: O(n + e). The adjacency list stores two entries per edge. The visited set holds at most n vertices, and the recursion can be up to n calls deep.

    Edge cases and common mistakes

    • No edges. With edges = [], the answer is True when source == destination and False otherwise. validPath(2, [], 0, 1) returns False.
    • Disconnected graph. The second example shows this: the search never leaves the source's group.
    • Adding only one direction. Without the second append, the graph becomes directed. A path that needs to walk an edge backwards is then missed.
    • Marking visited too late. If a vertex is added to visited only after the loop over its neighbors, two neighbors can call each other forever, until the recursion limit is hit.
    • Forgetting the visited check. A cycle makes the search endless.
    • Returning inside the search. Returning early works too, but this version is simpler: finish the search, then test membership once.
    • Unused n. The method never needs n, because the adjacency list is built from the edges. A vertex with no edges has no entry in graph, and the dictionary supplies an empty list when it is looked up.

    Testing

    • n = 3, edges = [[0, 1], [1, 2], [2, 0]], source = 0, destination = 2 gives True.
    • n = 6, edges = [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]], source = 0, destination = 5 gives False.
    • n = 1, edges = [], source = 0, destination = 0 gives True.
    • n = 2, edges = [], source = 0, destination = 1 gives False.
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free