一魚多吃: 從不同方法確認 兩點之間的路徑存在與否

Nagy Szabi on Unsplash

今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目，來回顧以前學過的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 的原理，

並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！

感謝收看囉! 我們下篇文章再見~