圖——深度優先算法(DFS)

在DFS周遊過程中，需要調用四個數組

          Color[u]: 用以區分結點是否被通路

                        WHITE: 未被發現的結點；

                        GRAY: 已經發現，但是尚未完成計算的結點；

                        BLACK: 已經完成計算的結點。

           pred[u]: 前序結點指針，指向結點u的前序結點

           d[u]: 從源結點到u的距離——結點變為GRAY的時間

           f[u]: 結束時間，關于結點u的所有操作結束時的時間——結點變為 BLACK的時間

僞代碼解析

DFS(G)
Input: A graph G
Output: None
for 𝑢 𝑖𝑛 𝑉 do
    𝑐𝑜𝑙𝑜𝑟[𝑢] ←WHITE; //undiscovered
    𝑝𝑟𝑒𝑑[𝑢] ←NULL; //no predecessor
end
𝑡𝑖𝑚𝑒 ← 0;
for 𝑢 𝑖𝑛 𝑉 do
//start a new tree
    if 𝑐𝑜𝑙𝑜𝑟 𝑢 𝑖𝑠 𝑒𝑞𝑢𝑎𝑙 𝑡𝑜 𝑊𝐻𝐼𝑇𝐸 then
        DFSVisit(𝑢);
    end
end
           

 DFSVisit(u)  遞歸逐層進行通路

DFSVisit(u)  #遞歸函數
Input: A vertex u
Output: None
𝑐𝑜𝑙𝑜𝑟[𝑢] ←GRAY;   //u is discovered
𝑑 [𝑢 ]← ++𝑡𝑖𝑚𝑒;   //u’s discovery time
for 𝑣 ∈ 𝐴𝑑𝑗(𝑢) do
    //Visit undiscovered vertex
    if 𝑐𝑜𝑙𝑜𝑟 [𝑣] 𝑖𝑠 𝑒𝑞𝑢𝑎𝑙 𝑡𝑜 𝑊𝐻𝐼𝑇𝐸 then
        𝑝𝑟𝑒𝑑 [𝑣] ← 𝑢;
        DFSVisit(𝑣);
    end
end
𝑐𝑜𝑙𝑜𝑟[𝑢] ←BLACK;   //u has finished
𝑓 [𝑢] ← ++𝑡𝑖𝑚𝑒;     //u’s finish time