圖或樹的遍歷算法之所以會陷入死循環，其最核心、最普遍的原因在於待遍歷的“圖”數據結構中，存在着一個或多個“環路”，而遍歷算法在執行過程中，又缺少一個有效的“已訪問”狀態記錄機制。這套問題的產生，主要涉及五個關鍵因素：圖結構中存在“環路”、遍歷過程中缺少“已訪問”狀態的記錄機制、深度優先搜索的遞歸實現導致“無限遞歸”、廣度優先搜索的隊列處理不當、以及未能正確處理“非連通圖”的多個起點。
具體來説，一個“環路”的存在，意味着從圖中某個節點出發，沿着一系列的邊進行移動，最終，能夠再次回到這個出發點。如果一個遍歷算法，在訪問過一個節點後，沒有為其打上“我已經來過這裏”的標記，那麼，當它順着環路，再次回到這個已訪問過的節點時，就會將其，視為一個全新的、未被發現的節點，並再次，沿着它走過的舊路，重新開始一次新的遍歷。這個過程，會周而復始，永不終止，從而將程序，拖入無盡的循環之中。
一、基礎概念：理解“圖”與“樹”
在深入探討“為何會死循環”之前，我們必須首先，在概念上，對“圖”和“樹”這兩個數據結構，建立一個清晰、準確的認知。
- 什麼是圖？
在計算機科學中，圖，是一種用於表示“對象”與“對象”之間“關聯關係”的、非線性的數據結構。它由兩個基本元素構成：
頂點：代表了一個獨立的“對象”或“實體”。例如，一個社交網絡中的“用户”，或一張地圖上的“城市”。
邊：代表了兩個頂點之間的“關聯關係”。例如，用户之間的“好友關係”，或城市之間的“航線”。根據邊的方向性，圖又可以分為“有向圖”（邊有明確的方向，如A指向B）和“無向圖”（邊沒有方向，A與B相互連接）。
- 什麼是樹？
樹，是一種非常特殊的、受到更多約束的“圖”。一個數據結構，要被稱為“樹”，它必須同時滿足兩個核心條件：
它必須是“連通的”，即從任何一個頂點出發，都能到達其他任何一個頂點。
它絕對不能，包含任何“環路”。
- 核心概念：“環路”
環路，是指在圖中，存在一條路徑，其起點和終點，是同一個頂點。例如，在一個圖中，存在這樣的路徑：頂點A -> 頂點B -> 頂點C -> 頂點A。
這個“環路”的概念，是理解本文所有問題的“鑰匙”。根據定義，樹狀結構，是絕對不允許存在環路的。而一個通用的、普通的圖，則完全可以，包含一個甚至多個複雜的環路。
因此，一個設計正確的遍歷算法，在遍歷一棵“樹”時，通常是“天生安全”的，因為它無論如何行走，都永遠不會“回到過去”。但是，當同一個算法，被應用於一個可能包含“環路”的“圖”時，如果它沒有一套額外的“防範機制”，那麼，陷入“死循環”的風險，就變得極高。
二、遍歷的雙雄：深度優先與廣度優先
圖的遍歷，最經典的，有兩種核心算法：深度優先搜索和廣度優先搜索。
1. 深度優先搜索
深度優先搜索的策略，如同在探索一個“迷宮”時，始終堅持“一條路走到黑”。
執行過程：從一個起始頂點出發，訪問它。然後，從它所有“尚未被訪問”的鄰居中，任選一個，再對這個鄰居，進行同樣地、深入地探索。直到當前路徑的盡頭，再也沒有“未被訪問”的鄰居了，程序，才會“回溯”到上一個“岔路口”，去探索另一條“未曾走過”的路。
實現方式：這種“後進先出”的回溯行為，天然地，就非常適合，用“遞歸”或一個顯式的“棧”數據結構來實現。
2. 廣度優先搜索
廣度優先搜索的策略，則更像是在水中，投下一顆石子，所產生的“漣漪”。它是一種“逐層向外”的探索方式。
執行過程：從一個起始頂點出發，訪問它。然後，一次性地，訪問它“所有”的、尚未被訪問的鄰居（這構成了“第一層”漣漪）。然後，再依次地，從這些“第一層”的鄰居出發，去訪問它們所有的、尚未被訪問的鄰居（這構成了“第二層”漣漪），如此反覆，直至所有可達的頂點，都被訪問完畢。
實現方式：這種“先進先出”的逐層處理行為，天然地，就需要藉助一個“隊列”數據結構來實現。
三、死循環的“元兇”：未被標記的“環路”
現在，讓我們來看看，當上述這兩種經典的算法，遇到了一個包含了“環路”的、且算法自身又缺乏“防範機制”的圖時，會發生怎樣的“災難”。
- 問題的重現
假設，我們有如下一個簡單的、包含了“環路”的有向圖：
A -> B
B -> C
C -> A (這條邊，構成了 A->B->C->A 的環路)
- 深度優先搜索的“無限遞歸”
如果我們，從頂點A開始，進行一次“天真”的（即，沒有“已訪問”標記的）深度優先搜索，其執行過程（以遞歸為例）將是：
調用 DFS(A)：訪問A。找到A的鄰居B，於是，遞歸調用 DFS(B)。
調用 DFS(B)：訪問B。找到B的鄰居C，於是，遞歸調用 DFS(C)。
調用 DFS(C)：訪問C。找到C的鄰居A，於是，遞歸調用 DFS(A)。
調用 DFS(A)：訪問A。找到A的鄰居B，於是，遞歸調用 DFS(B)。
......
我們發現，程序，進入了一個A -> B -> C -> A -> ...的、永不終止的無限遞歸調用鏈。其最終的，也必然的結局，就是因為耗盡了“調用棧”的內存空間，而拋出一個“棧溢出”的致命錯誤。
- 廣度優先搜索的“無限入隊”
如果我們，從頂點A開始，進行一次“天真”的廣度優先搜索，其執行過程將是：
訪問A。將A的所有鄰居（即B），加入隊列。當前隊列：[B]。
從隊列中，取出B，並訪問它。將B的所有鄰居（即C），加入隊列。當前隊列：[C]。
從隊列中，取出C，並訪問它。將C的所有鄰居（即A），加入隊列。當前隊列：[A]。
從隊列中，取出A，並訪問它。將A的所有鄰居（即B），加入隊列。當前隊列：[B]。
......
我們發現，程序，同樣地，進入了一個在隊列中，反覆地“存入B、取出B、存入C、取出C、存入A、取出A……”的、永不終止的死循環。這個程序，可能不會像遞歸那樣，因為“棧溢出”而快速地崩潰，但它會永遠地運行下去，持續地，消耗着中央處理器的資源和內存。
四、解決方案：建立“已訪問”集合
要“斬斷”這個由“環路”所導致的“無限循環”，其唯一的、也是最根本的解決方案，就是為我們的遍歷算法，賦予“記憶”。
- 核心思想：“凡走過，必留痕”
這個“記憶”，在算法的實現中，通常，是一個被稱為“已訪問”的集合（可以使用“哈希集合”或“布爾數組”來實現）。
其核心思想是，在算法的整個生命週期中，維護這份“已訪問”列表。在即將訪問任何一個“新”的頂點之前，都必須，首先，查閲一下這份“記憶”，看看，我們“之前，是否已經來過這裏？”
- 修正後的深度優先搜索
Java
// visitedSet 是一個在遍歷開始前創建的、全局的集合
void correctedDFS(Node node, Set<Node> visitedSet) {
// 第一步：檢查“記憶”，如果已訪問過，則立即返回，斬斷循環
if (visitedSet.contains(node)) {
return;
}
// 第二步：如果未訪問，則立即“留下痕跡”，並進行訪問
visitedSet.add(node);
System.out.println("訪問節點: " + node.name);
// 第三步：繼續探索其鄰居
for (Node neighbor : node.getNeighbors()) {
correctedDFS(neighbor, visitedSet);
}}
通過在函數入口處，增加的這短短兩三行“檢查與標記”的代碼，我們就為深度優先搜索，安裝上了強大的“環路剎車”。
- 修正後的廣度優先搜索
Java
void correctedBFS(Node startNode) {
Queue<Node> queue = new LinkedList<>();
Set<Node> visitedSet = new HashSet<>();
// 將起點，同時，放入隊列和“已訪問”集合
queue.add(startNode);
visitedSet.add(startNode);
while (!queue.isEmpty()) {
Node currentNode = queue.poll();
System.out.println("訪問節點: " + currentNode.name);
for (Node neighbor : currentNode.getNeighbors()) {
// 在將任何一個新鄰居“入隊”之前，都必須，先檢查它是否已被訪問
if (!visitedSet.contains(neighbor)) {
// 如果未訪問，則同時，進行“標記”和“入隊”
visitedSet.add(neighbor);
queue.add(neighbor);
}
}
}}
五、在實踐中“防範”
要將上述的理論，轉化為工程實踐中的可靠保障，我們需要流程和工具的支撐。
將遍歷邏輯“模塊化”：應將這些經過了充分驗證的、包含了“已訪問”集合邏輯的、健壯的圖遍歷算法，封裝為可被團隊複用的、通用的“工具類”或“庫函數”。
編寫“邊界”單元測試：一個用於測試圖算法的、完備的單元測試集，必須，強制性地，包含一個或多個，專門用於檢驗算法在“有環圖”上，是否能正常終止的測試用例。
代碼審查與規範：團隊的編碼規範中，應明確指出，在處理任何可能存在“環路”的數據結構時，都必須考慮並實現“已訪問”的檢查機制。這份規範，可以被沉澱和共享在像 Worktile 這樣的通用協作平台的知識庫中。而在 PingCode 這樣的研發管理平台中，代碼審查是其核心的流程環節，審查者，應將“檢查是否存在不安全的遍歷邏輯”，作為一個重要的審查點。
常見問答 (FAQ)
Q1: “樹”的遍歷，需不需要“已訪問”集合？
A1: 理論上，不需要。因為“樹”的嚴格定義，就是“無環的連通圖”。因此，在遍歷一棵“完美”的樹時，你永遠不會，重複地，訪問到同一個節點。但是，在工程實踐中，為了代碼的“健壯性”（以防止輸入的數據，並非一棵“嚴格”的樹），增加一個“已訪問”的檢查，是一種更安全的、防禦性的編程習慣。
Q2: 深度優先搜索和廣度優先搜索，哪個更容易陷入死循環？
A2: 在都沒有“已訪問”檢查的情況下，兩者，在遇到“環路”時，都必然會陷入死循環。只是，其“表現形式”不同：深度優先搜索，通常，會因為“無限遞歸”，而快速地，以“棧溢出”的方式崩潰；而廣度優先搜索，則會因為“無限入隊”，而陷入一個不會自動崩潰、但會持續消耗資源的死循環。
Q3: 什麼是“有向無環圖”？它的遍歷有什麼特殊之處？
A3: “有向無環圖”，是一種特殊的圖，它雖然有向，但卻保證不存在任何環路。這種數據結構，在工程中，應用極其廣泛，例如，用於描述任務的“依賴關係”（A必須在B之前完成），或構建軟件的“編譯順序”。對於它，有一種特殊的、極其重要的遍歷算法，叫做“拓撲排序”。
Q4: 除了棧溢出或死循環，錯誤的圖遍歷還會導致什麼問題？
A4: 即便程序，因為某種巧合，沒有陷入死循環，一個沒有“已訪問”檢查的遍歷，也可能會，對同一個節點，進行“多次重複的訪問和處理”。如果，你的業務邏輯，是“每訪問一個節點，就將其計數加一”，那麼，這種重複訪問，就會導致最終的計算結果，完全錯誤。
