[理工] 演算法 DFS找strong connected component mogahuang PTT批踢踢實業坊

作者: mogahuang (mogahuang) 2016-11-13 18:34:41

各位大大安安
請問利用兩次DFS 找 scc 在第二步是用第一次v.f的大小選點，但要如何選才能切割出scc?
http://i.imgur.com/2nwLtDN.jpg

作者: windwaker112 (阿茄) 2016-11-14 16:14:00

作者: gigayaya (gigayaya) 2016-11-13 18:58:00

在srep.2走出一個cycle就是一個scc

作者: ken52011219 (呱) 2016-11-13 19:01:00

以G^T為例，G的u.f最大者為b(16)以它作為起點DFS可選擇做a(14) or f(4)因由大到小所以G^T選擇a我搞混了只剩a可以做所以選擇a應該看c 因c可選擇d(9) g(7)所以G^T DFS(c)選擇d做完一個CYCLE為一個強連通

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-11-13 19:14:00

一直覺得這個解法超妙的值得推一下XD

作者: mogahuang (mogahuang) 2016-11-13 19:27:00

Gigi大可是在原本的圖他不是也可以走一個cycle嗎？？我懂了，是用第一次的結束時間在第二次的圖上跑，因為單向會造成不連通，所以在做DFS時如果是scc的話會回到起點這樣嗎？？

作者: ken52011219 (呱) 2016-11-13 19:47:00

可以看成類似第一個DFS是找出單方向為connect的點第二次DFS找出另外一個方向的connect且為第一個DFS找出的connect的基礎上

作者: gigayaya (gigayaya) 2016-11-13 19:48:00

Step2的圖是原本圖的反向挑的順序是圖1DFS結束時間從最大的開始挑

作者: aa06697 (todo se andarà) 2016-11-13 20:35:00

在原圖走不出相反圖的cycle

繼續閱讀