檢查無向圖中環

 def has_cycle(graph):

visited = set()

def dfs(node, parent):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            if dfs(neighbor, node):
                return True
        elif neighbor != parent:
            return True
    return False

for node in graph:
    if node not in visited:
        if dfs(node, -1):
            return True
return False

測試

graph_list = {
0: [1],
1: [0, 2],
2: [1, 3],
3: [2, 0] # 環
}
print(“圖中是否有環:”, has_cycle(graph_list)) # 預期輸出: True

這段程式碼的功能是檢查無向圖中是否存在環。它使用深度優先搜尋 (DFS) 遍歷圖中的每個節點，並判斷是否有路徑能回到已訪問的祖先節點，從而檢測環的存在。以下是逐步解釋：

---

主函式 has_cycle(graph)

• visited = set(): 建立一個空集合 visited，用來記錄已訪問的節點，避免重複遍歷。

• dfs(node, parent): 定義了一個內部遞迴函式 dfs，用來執行深度優先搜尋。這個函式接收兩個參數：

  • node: 當前正在訪問的節點。
  • parent: 來自哪個節點（父節點）進入當前節點，用來檢查是否回到祖先節點。

• for node in graph: 遍歷圖中所有的節點。如果某節點未被訪問，則從該節點出發執行 DFS。

• if dfs(node, -1): 如果 DFS 函式返回 True，表示圖中存在環，主函式返回 True，結束檢查。

• return False: 如果遍歷所有節點後沒有找到環，則返回 False。

---

DFS 函式 dfs(node, parent)

這個遞迴函式負責實際的深度優先搜尋，並檢查是否存在環。

1. 將節點標記為已訪問：visited.add(node)。
2. 遍歷鄰居節點：
   • for neighbor in graph[node]: 對於當前節點 node 的每個鄰居節點 neighbor：
     • 如果鄰居節點未被訪問：if neighbor not in visited
       • 遞迴調用 dfs(neighbor, node)，將當前節點 node 作為 neighbor 的父節點。
       • 如果遞迴返回 True，則表示在該鄰居路徑中找到環，返回 True。
     • 如果鄰居已被訪問且不是父節點：elif neighbor != parent
       • 表示存在一條回到已訪問節點的路徑，這條路徑構成環，因此返回 True。
3. 返回 False：如果所有鄰居都檢查過後沒有找到環，返回 False。

---

測試範例

graph_list = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2, 0]  # 環
}
print("圖中是否有環:", has_cycle(graph_list))  # 預期輸出: True

在這個範例中，圖包含節點 0, 1, 2, 3，並且 0-1-2-3-0 構成了一個環。所以 has_cycle 函式會返回 True。

---

總結

1. 這個程式碼使用 DFS 遍歷圖，檢查是否有路徑回到祖先節點。
2. parent 用於判斷是否是從父節點回到的鄰居，以避免誤判。
3. 一旦找到環，即返回 True，否則返回 False。

這種方法適用於無向圖的環檢測。

這一行程式碼的作用是：在 has_cycle 函式的主迴圈中，檢查從每個未訪問的節點開始的深度優先搜尋 (DFS) 是否會找到一個環。

---

補充說明

if dfs(node, -1):
    return True

1. dfs(node, -1)：這個呼叫啟動了 dfs 函式，從節點 node 開始進行深度優先搜尋，並將 -1 傳給 parent 參數。

   • parent = -1 表示這個起始點沒有「父節點」，因為我們是從這個節點出發的。用 -1 標記它可以避免誤判。

2. 檢查 dfs 的結果：dfs(node, -1) 會在遍歷過程中檢查圖中是否存在環：

   • 如果在 node 的 DFS 遍歷中發現環，dfs 會返回 True。
   • 若 dfs 返回 True，說明在以該節點為起點的路徑中有環，因此 has_cycle 函式也會立即返回 True。
   • 若 dfs 返回 False，說明在這個節點的 DFS 遍歷中沒有環，那麼主函式 has_cycle 繼續檢查圖中的其他未訪問節點。

3. 遍歷所有連通分量：

   • 如果圖是連通的，則只需從一個節點開始就可以遍歷整個圖。
   • 如果圖是非連通的（有多個連通分量），那麼主迴圈 for node in graph 就會檢查每個獨立的連通分量。

為何需要這一行

這行程式碼的主要目的是：

• 檢查整個圖中是否存在環，即使圖包含多個不相連的部分。
• 如果任意一個節點的 DFS 發現了環，就可以提前返回 True，無需繼續遍歷其他部分，這樣提高了效率。

總結

• 這一行啟動了 DFS，並檢查從節點 node 開始的路徑中是否有環。
• 只要任何一個節點的 DFS 返回 True，主函式 has_cycle 就立即返回 True，表示圖中存在環。
• 如果整個圖檢查完畢後都沒有找到環，則 has_cycle 返回 False。