作者jb679123 (straw man)
看板Prob_Solve
標題[問題] DFS recursive algorithm
時間Tue Dec 30 01:02:29 2014
http://ppt.cc/wxbW
附圖是用遞迴方式完成的DFS演算法
如果我們要根據演算法回傳的
d[u],f[u],pi[u],d[v],f[v],pi[v]
去判斷(u,v)是否為tree back forward 或cross edge
且要在O(1)的時間內
請問一下該怎麼判斷?
目前只想到是用color和d(u) d(v)去判斷
但題目要求要f[x]還有pi[x]
不知道這兩個要怎麼用進去
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.103.109
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1419872555.A.43D.html
1F：推 fenzhang: DFS生成樹沒有cross edge。 12/30 02:44
2F：→ fenzhang: tree edge一定有某端是另一端父親。 12/30 02:44
3F：→ scwg: 樓上在 undirected graph 裡是對的, directed graph DPS 12/30 06:28
4F：→ scwg: 是可能有 cross edge 的. 原 po: 你的作法是什麼? 複雜度是? 12/30 06:29
5F：→ scwg: 用 color 判斷有點奇怪, 因為 DFS 跑完每個點應該都是黑色.. 12/30 06:30
題目應該是問有向圖，沒有限定是DFS SPANNING TREE
我的想法是:
在u--->v的情況下 如果
u是gray v是white :tree edge
gray gray :back
gray black :若d[u]<d[v]則是forward 反之則是cross
※ 編輯: jb679123 (140.123.103.109), 12/30/2014 09:45:27
6F：→ scwg: 這個判斷應該是對的, 可惜 u.color == gray 只有 DFS 到一半 12/30 13:40
7F：→ scwg: 的時候會成立. 想想看 u.d 和 u.f 存了什麼? 怎麼用他們重建 12/30 13:41
8F：→ scwg: 「u.color == gray」成立的「時間」? 12/30 13:41
恩恩 這也是目前卡住的地方ORZ
※ 編輯: jb679123 (140.123.103.109), 12/30/2014 15:15:53
9F：→ aaaaajack: 現在回好像有點遲XD 總之需要考慮各種edge的特性 01/05 23:01
10F：→ aaaaajack: forward跟back edge滿足一個是另一個的ancestor 01/05 23:02
11F：→ aaaaajack: d跟f可以幫助你判斷這件事 01/05 23:02
12F：→ aaaaajack: 然後pi幫助你判斷他是不是tree edge 01/05 23:02
感謝a大的補充XDD
※ 編輯: jb679123 (140.123.214.127), 01/10/2015 16:03:42