Start learning free

LESSON 334 OF 347 · GRAPHS

Find if Path Exists in a Graph in C#: 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] = [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 <= edges.length <= 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

    C# · GRAPHS

    Find If Path Exist In A Graph in C#, explained

    Problem overview

    You get a graph with n vertices numbered 0 to n - 1, a list of edges, and two vertices, source and destination. Each edge connects two vertices and works in both directions. ValidPath returns true when 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 to 2 you can take the direct edge or go through 1, so the answer is true. In the second example the vertices 0, 1, 2 form one group and 3, 4, 5 form another, with no edge between the groups. There is no path from 0 to 5, so the answer is false.

    Approach: explore everything reachable from the source

    The question "is there a path?" is the same as "is the destination in the set of vertices reachable from the source?". Depth-first search (DFS) builds that set. It starts at the source, goes to a neighbour, then to a neighbour of that neighbour, and keeps going deeper. When it reaches a vertex with no unvisited neighbours it backs up and tries the next option.

    Two things make this work:

    • A visited set remembers which vertices the search has reached. A graph can contain cycles, like the triangle above. Without the set, the search would walk 0, 1, 2, 0, 1, 2 forever.
    • An adjacency list stores each vertex's neighbours, so the search can find them without scanning the whole edge list every time.

    After the search finishes, the visited set holds exactly the vertices connected to the source, and the answer is whether it contains destination.

    Step by step

    1. Build graph as a List<List<int>> and add n empty lists with a for loop. Index v then holds the neighbours of vertex v. Without the empty lists, graph[v] would be out of range.
    2. Declare a HashSet<int> named visited. It answers "have I been here?" in constant time on average.
    3. Loop over edges and record every edge in both directions: graph[edge[0]].Add(edge[1]) and graph[edge[1]].Add(edge[0]). The graph is bi-directional, so a search arriving at either end must be able to cross the edge.
    4. Call Dfs(source, graph, visited). When it returns, visited contains everything reachable from source.
    5. Return visited.Contains(destination). It already is a bool, so no if is needed.
    6. Write the helper Dfs with the current node, the graph and the visited set as parameters.
    7. Mark node as visited first. A neighbour that leads back to this vertex then finds it already marked.
    8. Loop over graph[node]. For each neighbour that is not in visited, call Dfs on it.

    The solution in C#

    class Solution {
    public bool ValidPath(int n, List<List<int>> edges, int source, int destination) {
        List<List<int>> graph = new List<List<int>>();
        for (int i = 0; i < n; i++) graph.Add(new List<int>());
        HashSet<int> visited = new HashSet<int>();
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        Dfs(source, graph, visited);
        return visited.Contains(destination);
    }

    private void Dfs(int node, List<List<int>> graph, HashSet<int> visited) {
        visited.Add(node);
        foreach (int adjacentNode in graph[node]) {
            if (!visited.Contains(adjacentNode)) {
                Dfs(adjacentNode, graph, visited);
            }
        }
    }
}

    Trace the second example. The adjacency lists are: 0 has 1 and 2; 1 has 0; 2 has 0; 3 has 5 and 4; 4 has 5 and 3; 5 has 3 and 4. Starting from 0, the search visits 0, then 1 (a dead end), then 2. The visited set ends as {0, 1, 2}, which doesn't contain 5, so the result is false.

    Some C# details:

    • Nested lists. List<List<int>> is a list whose elements are lists. graph.Add(new List<int>()) adds a fresh, independent list each time. Adding the same list object repeatedly would make all vertices share one neighbour list.
    • Edges are lists, too. Here edges is a List<List<int>>, so edge[0] and edge[1] use the list indexer, and var in the foreach lets the compiler infer the element type List<int>.
    • Shared state. List and HashSet are reference types, so Dfs receives a reference to the same objects that ValidPath created. Adding to visited inside Dfs is visible to the caller.
    • Private helper. private void Dfs is callable only from inside Solution. It returns nothing and communicates through the set.
    • HashSet.Add and duplicates. Adding a value that is already present is harmless; the method just returns false. The explicit Contains check before recursing is still what prevents the endless recursion.

    Complexity

    Time: O(n + m), where m is the number of edges. Building the lists costs O(n + m). The search enters each vertex at most once, and it looks at every adjacency list entry once, which sums to 2m entries.

    Space: O(n + m) for the adjacency lists, plus O(n) for the visited set and the recursion. The recursion depth can reach n on a graph shaped like a single long path.

    Edge cases and common mistakes

    • Source equals destination. The search marks the source first, so the answer is true even with no edges at all, as in n = 1.
    • Adding each edge in one direction only. With edges = [[1,0]], source = 0 and destination = 1, the answer must be true. A one-directional adjacency list would give false.
    • Marking visited too late. Marking a vertex after the loop over its neighbours lets two neighbours call each other before either is marked, and the recursion never ends.
    • Disconnected components. The vertices that the search never touches simply don't appear in visited. There is no need to check them one by one.
    • Very deep recursion. Each recursive call uses stack space. A graph that is one long path of 200,000 vertices can exhaust the call stack and crash a recursive DFS. When the depth could be that large, keep your own Stack<int> and loop instead, or use breadth-first search with a Queue<int>.

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