如何求出圖中的強連通分支數(shù)？從節(jié)點1啟動DFS并將遍歷的節(jié)點添加到堆棧中。當(dāng)u=6，DFN[6]=low[6]時，發(fā)現(xiàn)一個強連通分量。在u=V之前，{6}是強連通分量。初始化時，low[u]=DFN[

如何求出圖中的強連通分支數(shù)？

從節(jié)點1啟動DFS并將遍歷的節(jié)點添加到堆棧中。當(dāng)u=6，DFN[6]=low[6]時，發(fā)現(xiàn)一個強連通分量。在u=V之前，{6}是強連通分量。

初始化時，low[u]=DFN[u]=index

返回節(jié)點5，發(fā)現(xiàn)DFN[5]=low[5]，且{5}是反堆棧后的強連通組件。

返回節(jié)點3，繼續(xù)搜索節(jié)點4，并將4添加到堆棧中。發(fā)現(xiàn)節(jié)點4相對于節(jié)點1有一個后緣，而節(jié)點1仍然在堆棧中，所以低[4]=1。節(jié)點6已經(jīng)出棧，（4,6）是交叉邊，返回3，（3,4）是分支邊，所以low[3]=low[4]=1。

Low（U）=min{Low（U），DFN（V）}DFN（V），（U，V）是指向堆棧中節(jié)點的背面

繼續(xù)返回節(jié)點1，最后訪問節(jié)點2。訪問側(cè)（2，4），4仍然在堆棧中，所以低[2]=DFN[4]=5。返回1后，發(fā)現(xiàn)DFN[1]=low[1]，堆棧中的所有節(jié)點都被取出，形成一個連通組件{1，3，4，2}。

到目前為止，算法已經(jīng)結(jié)束。得到了圖中三個強連通分量{1,3,4,2}，{5}，{6}。

離散數(shù)學(xué)中連通分量怎么求？

作為遍歷圖的一個應(yīng)用實例，我們將討論如何找到圖的連通分量。

連接的組件是無向圖中極性連接的子圖。求圖的連通分量的目的是確定圖中的一個頂點是否能到達另一個頂點，即圖中任意兩個頂點之間是否存在路徑。這個問題的答案可以直接從圖中看出。然而，一旦圖形存儲在計算機中，答案就不清楚了。對于連通圖，可以通過從任意頂點遍歷圖來訪問圖的所有頂點，即連通圖中任意兩個頂點之間存在一條路徑。對于非連通圖，從頂點遍歷圖只能訪問包含該頂點的連通組件中的所有頂點，而不能訪問其他連通組件中的頂點。也就是說，在連通分量中的任意一對頂點之間都有一條路徑，但是如果和在圖的不同連通分量中，那么圖中就沒有路徑，也就是說，它是不可達的。因此，只要解出圖的所有連通分量，就可以知道圖中任意兩個頂點之間是否存在路徑。