Start learning free

LESSON 335 OF 348 · GRAPHS

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

    KOTLIN · GRAPHS

    Find If Path Exist In A Graph in Kotlin, explained

    Problem overview

    You get an undirected graph with n vertices numbered 0 to n - 1. The edges arrive as edges, a list of two-element IntArrays, where [u, v] means vertices u and v are connected in both directions. The function validPath returns true when some chain of edges leads from source to destination, and false when none does. No edge repeats and no vertex has an edge to itself.

    In the first example, n = 3 and the edges form a triangle: [[0, 1], [1, 2], [2, 0]]. From 0 to 2 you can go directly, or through 1, so the answer is true. In the second example, n = 6, vertices 0, 1 and 2 form one group and vertices 3, 4 and 5 another, with no edge between them, so there is no path from 0 to 5 and the answer is false.

    Approach: explore everything reachable from the source

    Raw edge pairs are awkward for this question, because finding the neighbours of a vertex means scanning all edges. So first convert them into an adjacency list: for every vertex, the list of vertices it touches. Then run depth-first search (DFS) from source. DFS visits a vertex, then goes as deep as possible along its neighbours before backing up to try the others. When it finishes, the set of visited vertices is exactly the set reachable from source, and the answer is whether destination is in it.

    The one thing DFS must never do is revisit a vertex. In an undirected graph every edge can be crossed both ways, so without a record of visited vertices, two neighbours would call each other forever. The solution marks a vertex as visited as soon as it enters it, which also breaks longer cycles such as the triangle above.

    On the triangle, DFS starts at 0 and marks it. The neighbours of 0 are 1 and 2. It enters 1, marks it, and sees neighbours 0 (visited) and 2. It enters 2, marks it, and finds nothing new. Back at the start, 2 is already marked. The visited set is {0, 1, 2}, which contains the destination.

    Step by step

    1. Create the adjacency list. graph is an array of n empty mutable lists, so graph[i] will hold the neighbours of vertex i. The Array(n) { ... } constructor runs its lambda once per index, so every vertex gets its own list.
    2. Create the visited set. A hash-based set answers "have we been here?" quickly.
    3. Loop over edges. Each edge is a pair, with its endpoints in edge[0] and edge[1].
    4. Record each edge in both directions. The graph is undirected, so each endpoint goes into the other's list. If one direction is missing, searches that must travel "backwards" fail.
    5. Start the search. Call a helper named dfs on source with graph and visited. The helper is written next.
    6. Answer from the set. Return whether visited contains destination. contains already returns a Boolean, so no if is needed.
    7. Declare dfs. It takes the current node, the graph and the visited set. The set is passed by reference, so the helper's changes are visible to validPath.
    8. Mark the node first. Adding it to visited before looking at its neighbours is what stops cycles from causing infinite recursion.
    9. Loop over graph[node] with adjacentNode as the loop variable.
    10. Recurse only on unvisited neighbours. Skipping visited ones guarantees that each vertex is entered once.

    The solution in Kotlin

    class Solution {
    fun validPath(n: Int, edges: List<IntArray>, source: Int, destination: Int): Boolean {
        val graph = Array(n) { mutableListOf<Int>() }
        val visited = mutableSetOf<Int>()
        for (edge in edges) {
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])
        }
        dfs(source, graph, visited)
        return visited.contains(destination)
    }

    fun dfs(node: Int, graph: Array<MutableList<Int>>, visited: MutableSet<Int>) {
        visited.add(node)
        for (adjacentNode in graph[node]) {
            if (!visited.contains(adjacentNode)) {
                dfs(adjacentNode, graph, visited)
            }
        }
    }
}

    The Kotlin details worth a closer look:

    • Array(n) { mutableListOf<Int>() } builds an array whose element at each index comes from the lambda. Because the lambda runs once per index, the lists are separate objects. Filling an array with one shared list would make every vertex see every edge. Its type is Array<MutableList<Int>>, which is the type dfs declares for its parameter.
    • mutableSetOf<Int>() creates a MutableSet<Int>. A plain Set is a read-only view with no add method.
    • Passing collections gives the callee a reference, not a copy. That is how dfs fills the caller's set without returning anything.
    • Calling a sibling method by name. dfs is a member of the same class, so validPath calls it directly, even though it is declared below.
    • !visited.contains(adjacentNode) is the negated membership test. Kotlin also allows adjacentNode !in visited, which means the same.
    • Deep recursion. Each recursive call uses a stack frame. On a long chain of vertices, say a path with thousands of vertices, the default JVM stack can overflow and throw StackOverflowError. The search with an explicit stack of its own avoids that limit.

    Complexity

    Time: O(n + e), where e is the number of edges. Building the lists touches each edge once. The search enters each vertex at most once and looks at each neighbour list once, so it examines each edge a constant number of times.

    Space: O(n + e). The adjacency lists hold two entries per edge, the visited set holds up to n vertices, and the recursion can be up to n calls deep.

    Edge cases and common mistakes

    • source == destination. n = 1 with no edges and both ends 0 gives true, since the search marks the source before anything else.
    • No edges. With n = 2, an empty list of edges and different endpoints, the answer is false. The visited set holds only the source.
    • Edges listed in the "wrong" direction. With n = 4, the single edge [2, 3], source = 3 and destination = 2 returns true, because each edge is stored both ways. Adding only graph[edge[0]].add(edge[1]) would answer false.
    • Marking too late. If a node were added to visited only after its neighbours had been processed, a cycle would recurse forever.
    • Disconnected graphs. The second example shows it: the other group of vertices is never reached, so destination isn't in visited.
    • Shared lists. Building the array with one list object repeated n times merges every vertex's neighbours into one pile.

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