04.01. Route Between Nodes

Description

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Example1:


 Input: n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2

 Output: true

Example2:


 Input: n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4

 Output true

Note:

0 <= n <= 100000
All node numbers are within the range [0, n].
There might be self cycles and duplicated edges.

Solutions

Solution 1: DFS

First, we construct an adjacency list $g$ based on the given graph, where $g[i]$ represents all the neighboring nodes of node $i$. We use a hash table or array $vis$ to record the visited nodes, and then start a depth-first search from node $start$. If we search to node $target$, we return true, otherwise we return false.

The process of depth-first search is as follows:

If the current node $i$ equals the target node $target$, return true.
If the current node $i$ has been visited, return false.
Otherwise, mark the current node $i$ as visited, and then traverse all the neighboring nodes $j$ of node $i$, and recursively search node $j$.

The time complexity is $O(n + m)$, and the space complexity is $O(n + m)$, where $n$ and $m$ are the number of nodes and edges respectively.

Python3JavaC++GoTypeScriptSwift

class Solution:
    def findWhetherExistsPath(
        self, n: int, graph: List[List[int]], start: int, target: int
    ) -> bool:
        def dfs(i: int):
            if i == target:
                return True
            if i in vis:
                return False
            vis.add(i)
            return any(dfs(j) for j in g[i])

        g = [[] for _ in range(n)]
        for a, b in graph:
            g[a].append(b)
        vis = set()
        return dfs(start)

class Solution {
    private List<Integer>[] g;
    private boolean[] vis;
    private int target;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        vis = new boolean[n];
        g = new List[n];
        this.target = target;
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : graph) {
            g[e[0]].add(e[1]);
        }
        return dfs(start);
    }

    private boolean dfs(int i) {
        if (i == target) {
            return true;
        }
        if (vis[i]) {
            return false;
        }
        vis[i] = true;
        for (int j : g[i]) {
            if (dfs(j)) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        vector<int> g[n];
        vector<bool> vis(n);
        for (auto& e : graph) {
            g[e[0]].push_back(e[1]);
        }
        function<bool(int)> dfs = [&](int i) {
            if (i == target) {
                return true;
            }
            if (vis[i]) {
                return false;
            }
            vis[i] = true;
            for (int j : g[i]) {
                if (dfs(j)) {
                    return true;
                }
            }
            return false;
        };
        return dfs(start);
    }
};

func findWhetherExistsPath(n int, graph [][]int, start int, target int) bool {
    g := make([][]int, n)
    vis := make([]bool, n)
    for _, e := range graph {
        g[e[0]] = append(g[e[0]], e[1])
    }
    var dfs func(int) bool
    dfs = func(i int) bool {
        if i == target {
            return true
        }
        if vis[i] {
            return false
        }
        vis[i] = true
        for _, j := range g[i] {
            if dfs(j) {
                return true
            }
        }
        return false
    }
    return dfs(start)
}

function findWhetherExistsPath(
    n: number,
    graph: number[][],
    start: number,
    target: number,
): boolean {
    const g: number[][] = Array.from({ length: n }, () => []);
    const vis: boolean[] = Array.from({ length: n }, () => false);
    for (const [a, b] of graph) {
        g[a].push(b);
    }
    const dfs = (i: number): boolean => {
        if (i === target) {
            return true;
        }
        if (vis[i]) {
            return false;
        }
        vis[i] = true;
        return g[i].some(dfs);
    };
    return dfs(start);
}

class Solution {
    private var g: [[Int]]!
    private var vis: [Bool]!
    private var target: Int!

    func findWhetherExistsPath(_ n: Int, _ graph: [[Int]], _ start: Int, _ target: Int) -> Bool {
        vis = [Bool](repeating: false, count: n)
        g = [[Int]](repeating: [], count: n)
        self.target = target
        for e in graph {
            g[e[0]].append(e[1])
        }
        return dfs(start)
    }

    private func dfs(_ i: Int) -> Bool {
        if i == target {
            return true
        }
        if vis[i] {
            return false
        }
        vis[i] = true
        for j in g[i] {
            if dfs(j) {
                return true
            }
        }
        return false
    }
}

Solution 2: BFS

Similar to Solution 1, we first construct an adjacency list $g$ based on the given graph, where $g[i]$ represents all the neighboring nodes of node $i$. We use a hash table or array $vis$ to record the visited nodes, and then start a breadth-first search from node $start$. If we search to node $target$, we return true, otherwise we return false.