第一遍dfs是對(duì)原圖進(jìn)行，求出每個(gè)結(jié)點(diǎn)的后序遍歷順序，也叫時(shí)間戳，注意保存方式，應(yīng)該是保存每個(gè)時(shí)間點(diǎn)的訪問(wèn)的結(jié)點(diǎn)，而不是保存每個(gè)結(jié)點(diǎn)的訪問(wèn)時(shí)間；
第二遍dfs是對(duì)逆圖進(jìn)行，根據(jù)第一遍dfs的結(jié)果，首先在逆圖上從時(shí)間戳最大的結(jié)點(diǎn)開始dfs，可以得到第一個(gè)強(qiáng)連通分量，將遍歷過(guò)的結(jié)點(diǎn)標(biāo)記，然后從下一個(gè)時(shí)間戳最大的且尚未標(biāo)記的結(jié)點(diǎn)開始dfs，可以得到第二個(gè)強(qiáng)連通分量，以此類推，直到所有結(jié)點(diǎn)都確定其所在的強(qiáng)連通分量，此時(shí)算法結(jié)束。

首先分析由此算法得到的第一個(gè)強(qiáng)連通分量的正確性，易知時(shí)間戳最大的是有向圖的根結(jié)點(diǎn)：
1、從根結(jié)點(diǎn)出發(fā)，可以到達(dá)所有結(jié)點(diǎn)；
2、第二遍dfs是在逆圖上進(jìn)行的，所以第二遍dfs得到的是所有能到達(dá)根結(jié)點(diǎn)的結(jié)點(diǎn)。
由以上2點(diǎn)和強(qiáng)連通分量的定義可知，第二遍dfs得到的確實(shí)是根結(jié)點(diǎn)所在的強(qiáng)連通分量。

然后考慮將第一個(gè)強(qiáng)連通分量所包含的結(jié)點(diǎn)從原圖中去掉（標(biāo)記），則得到一個(gè)有向圖的森林（可能含有多個(gè)根結(jié)點(diǎn)），時(shí)間戳最大的結(jié)點(diǎn)是森林中的某個(gè)根結(jié)點(diǎn)，問(wèn)題轉(zhuǎn)化為以上討論過(guò)的形式，在此不再重復(fù)。

以上所說(shuō)的“從根結(jié)點(diǎn)出發(fā)，可以到達(dá)所有結(jié)點(diǎn)”其實(shí)是有問(wèn)題的……
另一種稍微嚴(yán)謹(jǐn)?shù)姆治?#xff1a;
首先證明一個(gè)結(jié)論：若從時(shí)間戳較小的結(jié)點(diǎn)a出發(fā)可以到達(dá)時(shí)間戳較大的結(jié)點(diǎn)b，那么從結(jié)點(diǎn)b出發(fā)一定可以到達(dá)結(jié)點(diǎn)a

反證法：假設(shè)a的后序遍歷時(shí)間戳<b的時(shí)間戳，從a可達(dá)b，但從b不可達(dá)a，則該圖至少有2個(gè)強(qiáng)連通分量，第一遍dfs存在2中情況：
情況1：a所在的強(qiáng)連通分量在第一遍dfs時(shí)先于b所在的強(qiáng)連通分量，由于a可達(dá)b，所以b的后序遍歷時(shí)間戳將小于a的時(shí)間戳，與條件矛盾；
情況2：b所在的強(qiáng)連通分量在第一遍dfs時(shí)先于a所在的強(qiáng)連通分量，由于b不可達(dá)a，所以b的后序遍歷時(shí)間戳將小于a的時(shí)間戳，與條件矛盾。

終上所述，結(jié)論得證。

有了以上結(jié)論，第二遍dfs就好理解了，第二遍dfs是從當(dāng)前時(shí)間戳最大的結(jié)點(diǎn)開始的，且是對(duì)逆圖進(jìn)行dfs，所以找到的都是時(shí)間戳小于當(dāng)前結(jié)點(diǎn)的且在原圖上能到達(dá)當(dāng)前結(jié)點(diǎn)的所有結(jié)點(diǎn)，根據(jù)以上結(jié)論，所以當(dāng)前結(jié)點(diǎn)能到達(dá)所有這些找到的結(jié)點(diǎn)，所以就找到了當(dāng)前結(jié)點(diǎn)所在的強(qiáng)連通分量所含的結(jié)點(diǎn)。

轉(zhuǎn)載于:https://www.cnblogs.com/algorithms/archive/2012/07/05/2577596.html

總結(jié)

以上是生活随笔為你收集整理的对用2遍dfs求有向图强连通分量的理解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。