尋找強大的連接組件？

Question

要在有向圖G中查找強連通的組件，您需要先找到一個sink節點。爲了找到匯聚節點，DFS運行在G-let的反向圖上，稱之爲H.然後，具有最高的郵政編號（標記該節點的時間剩下）的節點將是H中的源節點，因此匯聚節點在G中，使我們能夠有效地識別G中的匯聚節點。爲什麼不簡單地使用G中具有最低後綴編號的節點，而不是做所有這些？如果源節點中圖形中郵政編號最高的頂點，是不是後面的郵政編號最小的節點是匯聚節點？爲什麼通過查找源節點而使事情複雜化？ 爲什麼不使用G中作爲最小發布數的頂點作爲sink節點？

Answer 1

它可能不是水槽。例如，對於DFS從s中的圖表

s->a 
^ | 
| v 
c<-b 
    | 
    v 
    d 

遍歷可能是

enter(s) 
enter(a) 
enter(b) 
enter(c) 
leave(c) 
enter(d) 
leave(d) 
leave(b) 
leave(a) 
leave(s) 

所以C具有最低的交數，但不是一個接收器。