Start learning free

LESSON 326 OF 338 · GRAPHS

Find if Path Exists in Graph in Go: 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

    GO · GRAPHS

    Find If Path Exist In A Graph in Go, explained

    Problem overview

    The function validPath receives a number of vertices n (labeled 0 to n - 1), a list of edges, a source and a 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 0 reaches 2 directly and validPath returns true. In the second, n = 6: vertices 0, 1 and 2 form one group and 3, 4 and 5 another, with no edge between the groups. Going from 0 to 5 is impossible, so the answer is false.

    Approach: explore everything reachable from the source

    Asking whether a path exists is the same as asking whether destination belongs to the set of vertices reachable from source. Depth-first search (DFS) builds exactly that set. It stands on a vertex, marks it as visited, and then moves on to each neighbor that hasn't been visited yet, going as deep as it can before backing up.

    The marking is what keeps the search finite. In a graph with a cycle, such as the triangle above, a search without marking would go 0, 1, 2, 0, 1, 2 and so on forever. Marking a vertex before exploring its neighbors guarantees that a neighbor leading back sees it as already visited.

    Two preparations are needed. DFS asks "which vertices touch this one?" over and over, and the list of edges answers that slowly. So first convert the edges into an adjacency list: for each vertex, the list of its neighbors. And because every edge works both ways, each edge must be recorded for both endpoints.

    Step by step

    1. Create the adjacency list graph with make([][]int, n), one slice of neighbors per vertex. The inner slices start out nil, and append works on a nil slice.
    2. Create visited as a map[int]bool. Reading a missing key gives false, so every vertex starts as unvisited with no setup.
    3. Loop over edges, naming each pair edge.
    4. Append each endpoint to the other's list. Do it in both directions, or the search can't cross an edge backwards. append returns the grown slice, so assign it back.
    5. Call dfs on source, passing graph and visited. Afterwards visited holds every vertex reachable from the source.
    6. Return visited[destination]. It is true only if the search reached that vertex.
    7. Write dfs with the parameters node, graph and visited.
    8. Mark node as visited first, before looking at neighbors, so cycles can't cause infinite recursion.
    9. Range over graph[node], naming each neighbor adjacentNode.
    10. Recurse only on unvisited neighbors, with if !visited[adjacentNode].

    The solution in Go

    func validPath(n int, edges [][]int, source int, destination int) bool {
    graph := make([][]int, n)
    visited := make(map[int]bool)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    dfs(source, graph, visited)
    return visited[destination]
}

func dfs(node int, graph [][]int, visited map[int]bool) {
    visited[node] = true
    for _, adjacentNode := range graph[node] {
        if !visited[adjacentNode] {
            dfs(adjacentNode, graph, visited)
        }
    }
}

    The Go details worth knowing:

    • make([][]int, n) creates a slice of n elements, each a nil []int. That is a usable empty list, and append allocates it on first use.
    • A missing map key gives the zero value. For map[int]bool that is false. This is why !visited[adjacentNode] and the final visited[destination] need no v, ok := form here: "absent" and "false" mean the same thing.
    • Maps are reference-like. Passing visited to dfs passes a handle to the same map, so every recursive call marks the same set. Without the map, each call would work on its own copy of a flag.
    • Slices of slices are updated in place. graph[edge[0]] = append(...) must assign back because append may return a new slice header when the slice grows.
    • Recursion depth. Go's stacks grow as needed, so even a single chain of 200,000 vertices, the largest the constraints allow, runs without trouble.
    • The order of function declarations doesn't matter. validPath calls dfs, which is declared below it.

    Complexity

    Building the adjacency list takes O(E) for E edges. DFS marks each vertex once and looks at each neighbor list entry once, so it costs O(V + E) in total. The adjacency list, the map and the recursion stack all use O(V + E) space at most.

    Edge cases and common mistakes

    • Source equals destination. validPath(1, [][]int{}, 0, 0) returns true, because the search marks the source immediately and zero steps is a valid path.
    • No edges and two vertices. validPath(2, [][]int{}, 0, 1) returns false: the search marks only the source.
    • Adding each edge only one way. With edges [[1,0],[2,1]], searching from 0 to 2 only works because both directions are recorded. One direction would leave 0 with no neighbors.
    • Marking after the recursive call. If visited[node] = true came after the loop, a cycle would recurse forever.
    • Forgetting the visited check. Even with marking, recursing without the if sends the search back along the edge it just came from, so the check is what stops the repetition.
    • Disconnected groups. The search from the source never leaves its own group, which is what makes the second example answer false.

    Testing

    • n = 3, edges [[0,1],[1,2],[2,0]], source 0, destination 2 returns true.
    • n = 6, edges [[0,1],[0,2],[3,5],[5,4],[4,3]], source 0, destination 5 returns false.
    • n = 3, edges [[1,0],[2,1]], source 0, destination 2 returns true.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free