Route Between Two Nodes in Graph

Question

• lintcode: (176) Route Between Two Nodes in Graph
• Find if there is a path between two vertices in a directed graph - GeeksforGeeks

Problem Statement

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

Example

Given graph:

A----->B----->C
 \     |
  \    |
   \   |
    \  v
     ->D----->E

for s = B and t = E, return true

for s = D and t = C, return false

题解1 - DFS

检测图中两点是否通路，图搜索的简单问题，DFS 或者 BFS 均可，注意检查是否有环即可。这里使用哈希表记录节点是否被处理较为方便。深搜时以起点出发，递归处理其邻居节点，需要注意的是处理邻居节点的循环时不是直接 return, 而只在找到路径为真时才返回 true, 否则会过早返回 false 而忽略后续可能满足条件的路径。

• reference

# Definition for a Directed graph node
class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution:
    def dfs(self, i, countrd, graph, t):
        if countrd[i] == 1:
            return False
        if i == t:
            return True
        countrd[i] = 1
        for j in i.neighbors:
            if countrd[j] == 0 and self.dfs(j, countrd, graph, t):
                return True
        return False
    """
    @param graph: A list of Directed graph node
    @param s: the starting Directed graph node
    @param t: the terminal Directed graph node
    @return: a boolean value
    """

    def routeBetweenTwoNodesInGraph(self, graph, s, t):
        countrd = {}
        for x in graph:
            countrd[x] = 0
        return self.dfs(s, countrd, graph, t)

sol=Solution()
A=UndirectedGraphNode('A')
B=UndirectedGraphNode('B')
C=UndirectedGraphNode('C')
D=UndirectedGraphNode('D')
E=UndirectedGraphNode('E')

A.neighbors=[B,D]
B.neighbors=[C,D]
C.neighbors=[]
D.neighbors=[E]
E.neighbors=[]
graph=[A,B,C,D,E]

sol.routeBetweenTwoNodesInGraph(graph,D,C)

源码分析

根据构造函数的实现，Java 中判断是否有邻居节点时使用.size，而不是null. 注意深搜前检测是否被处理过。行

if (dfs(graph, node, t, visited)) return true;

中注意不是直接 return, 只在为 true 时返回。

复杂度分析

遍历所有点及边，时间复杂度为 $$O(V+E)$$.

题解2 - BFS

除了深搜处理邻居节点，我们也可以采用 BFS 结合队列处理，优点是不会爆栈，缺点是空间复杂度稍高和实现复杂点。

源码分析

同题解一。

复杂度分析

时间复杂度同题解一，也是 $$O(V+E)$$, 空间复杂度最坏情况下为两层多叉树，为 $$O(V+E)$$.