Start learning free

LESSON 359 OF 414 · GRAPHS

Find if Path Exists in Graph in Rust: DFS with a HashSet

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] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. 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 * 105
  • 0 <= (number of edges) <= 2 * 105
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= source, destination <= n - 1
  • There are no duplicate edges.
  • There are no self edges.
STEP 1 OF 10
    Ctrl + Enter to check

    RUST · GRAPHS

    Find If Path Exist In A Graph in Rust, explained

    Problem overview

    The function valid_path receives the number of vertices n (labeled 0 to n - 1), a vector of edges, and two vertices, source and destination. Each edge [u, v] connects two vertices in both directions. The function returns true when you can walk from source to destination along edges, and false otherwise.

    In the first example, n = 3 with edges [[0, 1], [1, 2], [2, 0]] forms a triangle, so vertex 2 is reachable from vertex 0 and the answer is true. In the second, n = 6 with edges [[0, 1], [0, 2], [3, 5], [5, 4], [4, 3]] has two separate groups, {0, 1, 2} and {3, 4, 5}. Vertex 5 can't be reached from vertex 0, so the answer is false.

    Approach: explore everything reachable from the source

    Checking every possible path would be wasteful, and the number of paths can be huge. The question is only whether the destination belongs to the same connected group as the source. So explore the whole group once, remembering each vertex you have seen, and look at the end whether the destination is among them.

    Depth-first search does the exploring. From a vertex, step to an unvisited neighbor and keep going deeper from there; when a vertex has no new neighbors, return to the previous one and try its next neighbor. The set of visited vertices does two jobs. It makes sure no vertex is processed twice, and it stops the search from running around a cycle forever, like the triangle in the first example.

    Before searching, the edge list is turned into an adjacency list: a vector whose position i holds the neighbors of vertex i. Finding a vertex's neighbors then takes no scan over all the edges.

    On the first example the adjacency list is [[1, 2], [0, 2], [1, 0]]. The search visits 0 and goes to its neighbor 1. From 1 it skips 0, which is visited, and goes to 2. Now visited is {0, 1, 2}, which contains the destination 2.

    Step by step

    1. Create the adjacency list graph as a mutable Vec<Vec<i32>> holding n empty vectors. The length must be a usize, hence n as usize.
    2. Create an empty HashSet<i32> called visited, to remember which vertices the search has reached.
    3. Loop over &edges. Borrowing keeps the vector from being moved, and each edge is a reference to a Vec<i32>.
    4. Record each edge in both directions. Push edge[1] onto the list of edge[0] and edge[0] onto the list of edge[1], indexing with as usize. Without the second push, the search could not walk an edge backward.
    5. Start the search with Self::dfs(source, &graph, &mut visited). The graph is borrowed immutably and the set mutably, so the helper fills the caller's set.
    6. Return whether visited contains the destination, as the final expression. contains takes a reference, so pass &destination.
    7. Write the helper dfs, with parameters node: i32, graph: &Vec<Vec<i32>> and visited: &mut HashSet<i32>.
    8. Insert the current node into visited first. Marking before exploring is what stops two neighbors from calling each other forever.
    9. Loop over the node's neighbors, &graph[node as usize], with the pattern &adjacent_node to copy each number out of its reference.
    10. Recurse on every neighbor that is not yet visited, passing graph and visited on as they are: they are already references.

    The solution in Rust

    impl Solution {
    fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        let mut graph: Vec<Vec<i32>> = vec![Vec::new(); n as usize];
        let mut visited: HashSet<i32> = HashSet::new();
        for edge in &edges {
            graph[edge[0] as usize].push(edge[1]);
            graph[edge[1] as usize].push(edge[0]);
        }
        Self::dfs(source, &graph, &mut visited);
        visited.contains(&destination)
    }

    fn dfs(node: i32, graph: &Vec<Vec<i32>>, visited: &mut HashSet<i32>) {
        visited.insert(node);
        for &adjacent_node in &graph[node as usize] {
            if !visited.contains(&adjacent_node) {
                Self::dfs(adjacent_node, graph, visited);
            }
        }
    }
}

    The Rust details worth a closer look:

    • HashSet comes from std::collections. A standalone program needs use std::collections::HashSet; at the top.
    • vec![Vec::new(); n] clones the empty vector n times, so every vertex gets its own independent list.
    • Borrowing. &graph hands the helper a shared read-only view, and &mut visited hands it exclusive write access. Inside dfs the parameters are already references, so recursion passes graph and visited without another & or &mut. Rust does not let two &mut borrows of the same set overlap, but passing the existing one down is fine.
    • Casting indexes. Vertices are stored as i32, but indexing a vector needs a usize, so every index is written x as usize.
    • for &adjacent_node in &graph[...]. Iterating a borrowed vector yields &i32 items; the & in the pattern copies each one into a plain i32.
    • No return value in dfs. It works by side effect, filling visited. Its last statement is a for loop, so it returns ().

    Complexity

    Time: O(n + m), where m is the number of edges. Building the adjacency list touches each edge once. The search visits each vertex once, and over the whole search every adjacency list is read once, which adds up to 2m neighbor checks.

    Space: O(n + m). The adjacency list holds 2m entries plus n vectors, and the set holds up to n vertices. The recursion also uses stack space proportional to the longest chain of vertices followed, up to n in the worst case.

    Edge cases and common mistakes

    • Source equals destination. With n = 1, no edges and source = destination = 0, the search marks 0 as visited and the answer is true.
    • No edges at all. Every vertex is alone, so the answer is true only when the source is the destination.
    • Edges given "backwards". For n = 2 and edges = [[1, 0]] the answer from 0 to 1 is true, because both directions are recorded. Adding only one direction would make it false.
    • Cycles. Skipping the contains check, or marking a vertex only after its neighbors are explored, sends the triangle example into endless recursion.
    • Very long chains. Each recursive call uses a stack frame. A single line of 200,000 vertices, which the input limits allow, can make this recursive version overflow the stack and abort the program. An explicit stack replaces the recursion: push the source, then repeatedly pop a vertex and push each neighbor for which visited.insert(neighbor) returns true. That version handled the same 200,000-vertex chain, and insert returns false when the value was already in the set.

    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 = [[1,0]], source = 0, destination = 1 gives true.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free