[理工] 演算法 DFS找strong connected component

看板Grad-ProbAsk作者 (mogahuang)時間7年前 (2016/11/13 18:34), 編輯推噓3(3推 0噓 15→)
留言18則, 6人參與, 最新討論串1/1
各位大大安安 請問利用兩次DFS 找 scc 在第二步是用第一次v.f的大小選點，但要如何選才能切割出scc? http://i.imgur.com/2nwLtDN.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.83.181 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479033283.A.09C.html
→
11/13 18:58, , 1F
在srep.2走出一個cycle就是一個scc
11/13 18:58, 1F
→
11/13 19:01, , 2F
以G^T為例，G的u.f最大者為b(16)以它作為起點
11/13 19:01, 2F
→
11/13 19:02, , 3F
DFS可選擇做a(14) or f(4)因 由大到小所以G^T選擇a
11/13 19:02, 3F
→
11/13 19:04, , 4F
我搞混了 只剩a可以做所以選擇a
11/13 19:04, 4F
→
11/13 19:06, , 5F
應該看c 因c可選擇d(9) g(7)所以G^T DFS(c)選擇d
11/13 19:06, 5F
→
11/13 19:07, , 6F
做完一個CYCLE為一個強連通
11/13 19:07, 6F
推
11/13 19:14, , 7F
一直覺得這個解法超妙的 值得推一下XD
11/13 19:14, 7F
→
11/13 19:27, , 8F
Gigi大 可是在原本的圖他不是也可以走一個cycle嗎？？
11/13 19:27, 8F
→
11/13 19:31, , 9F
我懂了，是用第一次的結束時間在第二次的圖上跑，因為
11/13 19:31, 9F
→
11/13 19:31, , 10F
單向會造成不連通，所以在做DFS時如果是scc的話會回到
11/13 19:31, 10F
→
11/13 19:31, , 11F
起點這樣嗎？？
11/13 19:31, 11F
→
11/13 19:47, , 12F
可以看成類似第一個DFS是找出單方向為connect的點
11/13 19:47, 12F
→
11/13 19:47, , 13F
第二次DFS找出 另外一個方向的connect
11/13 19:47, 13F
→
11/13 19:48, , 14F
且為第一個DFS找出的connect的基礎上
11/13 19:48, 14F
→
11/13 19:48, , 15F
Step2的圖是原本圖的反向 挑的順序是圖1DFS結束時間從
11/13 19:48, 15F
→
11/13 19:48, , 16F
最大的開始挑
11/13 19:48, 16F
推
11/13 20:35, , 17F
在原圖走不出相反圖的cycle
11/13 20:35, 17F
推
11/14 16:14, , 18F
11/14 16:14, 18F
‣ 更多 mogahuang 的文章
文章代碼(AID): #1OA4732S (Grad-ProbAsk)