從節點1開始DFS,把遍歷到的節點加入棧中。搜尋到節點u=6時,DFN[6]=LOW[6],找到了一個強連通分量。退棧到u=v為止,{6}為一個強連通分量。
初始化時Low[u]=DFN[u]=++index
返回節點5,發現DFN[5]=LOW[5],退棧後{5}為一個強連通分量。
返回節點3,繼續搜尋到節點4,把4加入堆疊。發現節點4向節點1有後向邊,節點1還在棧中,所以LOW[4]=1。節點6已經出棧,(4,6)是橫叉邊,返回3,(3,4)為樹枝邊,所以LOW[3]=LOW[4]=1。
Low(u)=Min {Low(u), DFN(v) } DFN(v),(u,v)為指向棧中節點的後向邊
繼續回到節點1,最後訪問節點2。訪問邊(2,4),4還在棧中,所以LOW[2]=DFN[4]=5。返回1後,發現DFN[1]=LOW[1],把棧中節點全部取出,組成一個連通分量{1,3,4,2}。
至此,演算法結束。求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。
從節點1開始DFS,把遍歷到的節點加入棧中。搜尋到節點u=6時,DFN[6]=LOW[6],找到了一個強連通分量。退棧到u=v為止,{6}為一個強連通分量。
初始化時Low[u]=DFN[u]=++index
返回節點5,發現DFN[5]=LOW[5],退棧後{5}為一個強連通分量。
返回節點3,繼續搜尋到節點4,把4加入堆疊。發現節點4向節點1有後向邊,節點1還在棧中,所以LOW[4]=1。節點6已經出棧,(4,6)是橫叉邊,返回3,(3,4)為樹枝邊,所以LOW[3]=LOW[4]=1。
Low(u)=Min {Low(u), DFN(v) } DFN(v),(u,v)為指向棧中節點的後向邊
繼續回到節點1,最後訪問節點2。訪問邊(2,4),4還在棧中,所以LOW[2]=DFN[4]=5。返回1後,發現DFN[1]=LOW[1],把棧中節點全部取出,組成一個連通分量{1,3,4,2}。
至此,演算法結束。求出了圖中全部的三個強連通分量{1,3,4,2},{5},{6}。