Start learning free

LESSON 360 OF 415 · GRAPHS

Find if Path Exists in Graph in Swift: 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 <= (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

    SWIFT · GRAPHS

    Find If Path Exist In A Graph in Swift, explained

    Problem overview

    The method validPath receives n, the number of vertices labeled 0 to n - 1, a list of edges, and two vertices, source and destination. Every edge [u, v] is bi-directional: you can walk it from u to v and from v to u. The method returns true when some chain of edges leads from source to destination, and false otherwise.

    In the first example, n = 3 with edges [[0,1],[1,2],[2,0]] forms a triangle, so vertex 0 reaches vertex 2 directly or through vertex 1: the answer is true. In the second, n = 6 and the edges split the graph into two separate groups, {0, 1, 2} and {3, 4, 5}. Vertex 0 can't reach vertex 5, so the answer is false.

    Approach: explore everything reachable from the source

    The edges list is awkward to search, because finding the neighbors of a vertex would mean scanning every edge. The first step is to build an adjacency list: an array with one entry per vertex, holding the vertices that vertex is connected to.

    Then run a depth-first search (DFS) from source. DFS visits a vertex, then follows its first unvisited neighbor as far as it can go, then backs up and tries the next neighbor. Every vertex that is connected to source gets visited exactly once. A Set of visited vertices serves two purposes: it records the answer, and it stops the search from walking in circles around a cycle.

    After the search finishes, destination is reachable exactly when it is in the visited set. On the second example, the search from 0 visits 0, 1 and 2 only, and 5 is not among them.

    Step by step

    1. Create the adjacency list graph as a var: an array of n empty [Int] arrays, so index i holds the neighbors of vertex i.
    2. Create the empty set visited of type Set<Int>. It is a var because the search inserts into it.
    3. Loop over edges. Each edge is a pair of endpoints.
    4. Record the edge both ways. Append edge[1] to the neighbors of edge[0], and edge[0] to the neighbors of edge[1]. Without the second append, the search could not walk an edge backwards.
    5. Call dfs on source, passing graph and &visited. The ampersand marks an inout argument, which lets the helper change the caller's set.
    6. Return whether visited contains destination. contains already returns a Bool.
    7. Declare dfs with the current node, the graph, and the visited set as an inout parameter. Without inout, the helper would work on its own copy of the set.
    8. Insert the node into visited first. Marking a node before exploring its neighbors means a neighbor that leads back sees it as visited and doesn't return to it.
    9. Loop over graph[node] with the variable adjacentNode.
    10. Recurse only when the neighbor isn't visited yet. Without this check, two connected vertices would call each other forever.

    The solution in Swift

    class Solution {
    func validPath(_ n: Int, _ edges: [[Int]], _ source: Int, _ destination: Int) -> Bool {
        var graph = [[Int]](repeating: [Int](), count: n)
        var visited = Set<Int>()
        for edge in edges {
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        }
        dfs(source, graph, &visited)
        return visited.contains(destination)
    }

    func dfs(_ node: Int, _ graph: [[Int]], _ visited: inout Set<Int>) {
        visited.insert(node)
        for adjacentNode in graph[node] {
            if !visited.contains(adjacentNode) {
                dfs(adjacentNode, graph, &visited)
            }
        }
    }
}

    The Swift details worth a closer look:

    • Independent empty arrays. [[Int]](repeating: [Int](), count: n) repeats one empty array n times. Arrays are value types, so each copy is independent, and appending to graph[0] doesn't affect graph[1]. In a language where arrays are shared references, this pattern would be a trap.
    • inout and &. Swift passes sets and arrays by value, copying lazily. A parameter marked inout is written back to the caller's variable when the function returns. The call site must write &visited to make that visible. Passing the graph without inout is fine because the helper only reads it, and Swift doesn't copy it unless someone changes it.
    • Set<Int>. Checking whether it contains a value takes constant time on average, and insert does nothing if the value is already there.
    • Unlabeled parameters. The underscores let callers write dfs(source, graph, &visited) without labels.
    • Methods calling each other. validPath calls dfs by plain name. Inside a class method, Swift finds other methods of the same class without writing self..

    Complexity

    Let V be the number of vertices and E the number of edges.

    Time: O(V + E). Building the adjacency list touches each edge once. The search visits each vertex once and looks at each vertex's neighbor list once, which adds up to 2E entries.

    Space: O(V + E). The adjacency list stores 2E entries plus an array per vertex. The visited set holds up to V vertices, and the recursion can go as deep as V calls.

    Edge cases and common mistakes

    • Source equals destination. n = 1 with no edges and source = destination = 0 returns true, because the source is inserted into visited first.
    • No edges. With n = 2, no edges and different endpoints, the result is false.
    • Edges written in either order. [[1,0],[2,1]] from 2 to 0 returns true, thanks to the two-way recording.
    • Recording each edge once. Adding only graph[edge[0]] treats the graph as directed, and paths that use an edge backwards are missed.
    • Marking a vertex after the recursive calls. On a cycle the search comes back to a vertex that isn't marked yet and never stops.
    • Forgetting inout. Without it the helper changes only a local copy, and validPath sees an empty set.
    • Very long chains. The recursion depth equals the length of the longest path the search follows. A single chain of a few hundred thousand vertices can overflow the call stack and crash the program; the exact limit depends on the stack size. For huge inputs, a loop with an explicit stack avoids the limit.

    Testing

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