一魚多吃: 從不同方法確認 兩點之間的路徑存在與否
今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目，來回顧以前學過的DFS、BFS和Disjoint Set，鞏固圖論演算法的知識點。
題目敘述
給定我們已知n個節點的圖，和圖上的每一條無向邊edges。
請問給定的起點start和終點end是否存在一條路徑可以抵達?
測試範例
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 * 10^5
節點總數介於 1 ~ 二十萬之間。
0 <= edges.length <= 2 * 10^5
邊的總數介於 0 ~ 二十萬之間。
edges[i].length == 2
每個邊由兩個端點所構成。
0 <= ui, vi<= n - 1
節點編號一定是介於 0~n-1 的整數
ui!= vi
不會有自我指向邊。
0 <= source, destination <= n - 1
起點、終點一定是合法節點編號。
- There are no duplicate edges.
不會有重複的邊。(也就是說不會有平行邊)
- There are no self edges.
不會有自我指向邊。
想法
前面在圖論的演算法統整已經學過，看到路徑存在性檢查優先想到DFS，看到等權圖最短路徑想到BFS，看到有權圖的最短路徑想到Dijkstra、Bellman-Ford、Floyd-Warshall。
我們就先從最直覺的DFS出發，接著是等價的BFS寫法。
再來是其他的解法，也可以用集合的觀點來想，每加入一條邊就把相鄰的兩點併入到同一個集合，最後假如起點和終點在同一個集合，代表彼此可以透過圖上的邊來拜訪對方，也就是說，起點到終點至少存在一條路徑可以抵達。
DFS演算法 從起點出發，有路就一直往前走
從起點出發，有路就一直往前走，假如可以走到終點，
那代表至少有一條路徑可以抵達終點。
時間複雜度: O(V+E) 每個節點最多拜訪一次，每條邊最多拜訪一次。
空間複雜度: O(V) 每個節點，最多拜訪一次，而且不會重複拜訪。
遞回深度最深為O(V)
DFS演算法 遞回版本 程式碼
class Solution:
def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
# represent graph by adjacency matrix
graph = defaultdict(list)
# update graph by input edges
for v, u in edges:
graph[v].append(u)
graph[u].append(v)
visited = set()
path = []
# Launch DFS from start node
def dfs( cur ):
visited.add(cur)
path.append( cur )
if cur == end:
#print(path) # uncomment this line if you want to see the path from start to end on debug console
return True
for neighbor in graph[cur]:
if neighbor not in visited and dfs(neighbor):
return True
path.pop( )
return False
# --------------------------------------
return dfs(start)
BFS演算法 從起點出發，同心圓一層一層向外擴散
從起點出發，以起點為同心圓一層一層向外擴散，假如可以碰到終點，
那代表至少有一條路徑可以抵達終點。
時間複雜度: O(V+E) 每個節點最多拜訪一次，每條邊最多拜訪一次。
空間複雜度: O(V) 每個節點，最多拜訪一次，而且不會重複拜訪。
Queue長度最深為O(V)
BFS演算法 迭代版本 程式碼
class Solution:
def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
# represent graph by adjacency matrix
graph = defaultdict(list)
# update graph by input edges
for v, u in edges:
graph[v].append(u)
graph[u].append(v)
path = []
visited = set()
queue = deque([start])
# Launch BFS from start node
while queue:
cur = queue.popleft()
visited.add(cur)
path.append(cur)
if cur == end:
#print(path) # uncomment this line if you want to see the path from start to end on debug console
return True
for neighbor in graph[cur]:
if neighbor not in visited: queue.append(neighbor)
return False
Disjoint Set 演算法 合併相連的點到同一個集合
用集合的觀點來想，每加入一條邊就把相鄰的兩點併入到同一個集合。
最後假如起點和終點在同一個集合，代表彼此可以透過圖上的邊來拜訪對方，也就是說，起點到終點至少存在一條路徑可以抵達。
時間複雜度: O(V+E)
O(V) Disjoint Set 初始化的時間成本。
O(E * alpha(V) ) ~ O( E ) Disjoint Set 合併和查詢的成本。
alpha() 是inverse Ackermann function，實務上可視為常數。
空間複雜度: O(V) 初始化每個節點各自一個做為一個集合。
Disjoint Set 演算法 迭代版本程式碼
# Disjoin Set Union
class DSU:
def __init__(self, n):
self.parent = { i: i for i in range(n) }
self.rank = { i: 1 for i in range(n) }
def find(self, x):
cur = x
if self.parent[cur] != cur:
self.parent[cur] = self.find( self.parent[cur] )
return self.parent[cur]
else:
return cur
def union(self, x, y):
parent_x, parent_y = self.find(x), self.find(y)
rank_pax, rank_pay = self.rank[parent_x], self.rank[parent_y]
if parent_x != parent_y:
if rank_pax >= rank_pay:
self.parent[parent_y] = parent_x
self.rank[parent_x] = rank_pax + rank_pay
else:
self.parent[parent_x] = parent_y
self.rank[parent_x] = rank_pay + rank_pax
return
class Solution:
def validPath(self, n: int, edges: List[List[int]], start: int, end: int) -> bool:
graph = DSU(n)
# Keep union two nodes which are connected
for node_u, node_v in edges:
graph.union( node_u, node_v)
# If we know start and end node belong to the same set,
# then there is at least one path from start to end
if graph.find(start) == graph.find(end):
return True
# Special case handle
# n == 1 means Graph with one node, in this case, start == end == node_#0
# source node also acts as destination node
return (n == 1) or False
結語
條條大路通羅馬，萬變不離其宗。
一個題目可以有好多種解法，但是背後核心觀念都是類似的。
只要掌握基本原理，根據題意，找出目標的明確定義，
接著採用合適的圖論演算法去計算所求(起點到終點的路徑是否存在)即可!
希望能幫助讀者、觀眾徹底理解基本圖論演算法BFS / DFS 的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
