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

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

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

初始化時(shí)，low[u]=DFN[u]=index

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

返回節(jié)點(diǎn)3，繼續(xù)搜索節(jié)點(diǎn)4，并將4添加到堆棧中。發(fā)現(xiàn)節(jié)點(diǎn)4相對(duì)于節(jié)點(diǎn)1有一個(gè)后緣，而節(jié)點(diǎn)1仍然在堆棧中，所以低[4]=1。節(jié)點(diǎn)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é)點(diǎn)的背面

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

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

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

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

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