Start learning free

LESSON 331 OF 344 · GRAPHS

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

Practice O(V+E) Read the full explanation

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

Constraints:

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= source, destination <= n - 1
There are no duplicate edges.
There are no self edges.

STEP 1 OF 11

Guided

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

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.
Create the visited set, visited, to remember reached vertices. Membership tests on a set take constant time on average.
Loop over edges, with each pair in the variable edge.
Record one direction: append edge[1] to the neighbors of edge[0].
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.
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.
Mark the node visited first. Marking before exploring means any neighbor that leads back finds this vertex already visited.
Loop over the node's neighbors, with each one in adjacent_node.
Recurse only on unvisited neighbors: if adjacent_node not in visited, call dfs on it.
Start the search by calling dfs(source) in the body of validPath. Defining a function doesn't run it.
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 PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free