Skip to content

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:

  1. 0 <= n <= 100000
  2. All node numbers are within the range [0, n].
  3. 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:

  1. If the current node $i$ equals the target node $target$, return true.
  2. If the current node $i$ has been visited, return false.
  3. 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findWhetherExistsPath(
        self, n: int, graph: List[List[int]], start: int, target: int
    ) -&