Start learning free

LESSON 330 OF 343 · GRAPHS

Find if Path Exists in 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 11
    Ctrl + Enter to check

    C++ · GRAPHS

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

    Problem overview

    The method validPath receives n, the number of vertices labelled 0 to n - 1, a vector of edges, and two vertices, source and destination. Each entry [u, v] is a two-way connection between vertices u and v. The method returns true when you can walk from source to destination along edges, and false otherwise. There are no self-edges and no duplicate edges.

    In the first example, n = 3 and the edges form a triangle, so 0 reaches 2 directly: the answer is true. In the second, the edges split the six vertices into two groups, {0, 1, 2} and {3, 4, 5}, with no edge between them. Vertex 0 can't reach 5, so the answer is false.

    Approach: explore everything reachable from the source

    The question is whether destination sits in the same connected piece of the graph as source. To answer it, explore from source and see whether the exploration ever reaches destination.

    Depth-first search (DFS) explores by going as deep as it can: from a vertex, step to one unvisited neighbour, then continue from there, and only come back to try the next neighbour when that branch is exhausted. A recursive function expresses this in a few lines.

    Two preparations are needed first:

    • An adjacency list. The input lists edges, but DFS asks "which vertices touch this one?" many times. Storing each vertex's neighbours in a vector answers that quickly.
    • A visited set. Graphs can contain cycles, such as the triangle in the first example. Without a record of where you have been, the search would walk around the cycle forever. Marking each vertex when you enter it guarantees every vertex is processed once.

    After the search finishes, the visited set holds exactly the vertices reachable from source. The answer is whether destination is in it.

    Step by step

    1. Create the adjacency list graph as a vector<vector<int>> with n entries. The size constructor makes n empty inner vectors, so graph[i] is ready to receive neighbours of vertex i.
    2. Create the visited set as an unordered_set<int> named visited. Membership tests take constant time on average.
    3. Loop over edges with auto& edge, so each edge is read in place rather than copied.
    4. Record one direction: push edge[1] into graph[edge[0]].
    5. Record the other direction: push edge[0] into graph[edge[1]]. The graph is bi-directional, so the search must be able to cross each edge both ways. Skipping this line turns the graph into a directed one and loses paths that run "backwards".
    6. Run the search by calling a dfs helper, defined below, with source, graph and visited.
    7. Answer the question: visited.count(destination) is 1 if the vertex is in the set and 0 if not, so comparing it with 0 gives the boolean.
    8. Define dfs as a void function that takes the starting node, plus the graph and the set by reference. Passing by reference makes every recursive call update the same set.
    9. Mark the vertex first. Inserting node before looking at its neighbours means a neighbour that leads back here already sees it as visited.
    10. Loop over the neighbours in graph[node].
    11. Recurse on unvisited ones only. If visited.count(adjacentNode) is 0, call dfs on it. Without the check, two neighbouring vertices would call each other endlessly.

    The solution in C++

    class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n);
        unordered_set<int> visited;
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        dfs(source, graph, visited);
        return visited.count(destination) > 0;
    }

    void dfs(int node, vector<vector<int>>& graph, unordered_set<int>& visited) {
        visited.insert(node);
        for (int adjacentNode : graph[node]) {
            if (!visited.count(adjacentNode)) {
                dfs(adjacentNode, graph, visited);
            }
        }
    }
};

    C++ details to notice:

    • Pass containers by reference. With unordered_set<int>& visited every recursive call shares one set. If you wrote the parameter without &, each call would get its own copy, the marks would vanish when the call returned, and the search would revisit vertices. It would also copy a large set at every step.
    • Member functions can call each other in any order. validPath calls dfs, which is defined below it. Inside a class, that is fine.
    • vector<vector<int>> graph(n) calls the size constructor, which creates n empty inner vectors. That is why graph[edge[0]].push_back(...) works at once, with no setup loop.
    • count versus insert. For a set, count returns 0 or 1, so it works as a membership test. Elements are added with insert, since sets have no push_back.
    • Range-based loops over neighbours. for (int adjacentNode : graph[node]) copies each int, which is as cheap as a reference. The loop never changes graph[node], so the iteration is safe.
    • Recursion depth. Each call of dfs uses stack space. On a graph that is one long chain, the depth can reach the number of vertices. With n up to 200,000, that is deep enough to risk a stack overflow on some systems. The fix is an explicit stack (a vector<int> you push and pop yourself) or a queue-based search.

    Complexity

    Time: O(n + e), where e is the number of edges. Building the adjacency list touches each edge once. The search enters each vertex at most once, thanks to the visited set, and scans each vertex's neighbour list once, which in total covers every edge twice (once from each end).

    Space: O(n + e). The adjacency list stores two entries per edge plus one vector per vertex. The visited set holds up to n vertices, and the recursion can be up to n levels deep.

    Edge cases and common mistakes

    • Source equals destination. The search inserts source first, so the set contains it and the method returns true. With n = 1 and no edges, the answer is true.
    • No edges at all. With n = 2, an empty edges and different endpoints, the search visits only the source, and the answer is false.
    • Disconnected graphs. The second example is the typical case: the destination lives in a piece the search never enters.
    • Forgetting the reverse edge. With only graph[edge[0]] filled, an edge written as [2, 0] would only be usable from 2 to 0.
    • Marking too late. If a vertex is marked only after its neighbours are explored, a cycle brings the search back to it before it is marked, and the recursion never ends.
    • Isolated vertices. Vertices with no edges just have empty neighbour lists. The loops simply don't run for them.

    Testing

    • n = 3, edges = [[0,1],[1,2],[2,0]], from 0 to 2 gives true.
    • n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], from 0 to 5 gives false.
    • n = 1, no edges, from 0 to 0 gives true.
    • n = 2, no edges, from 0 to 1 gives false.
    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