PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] DFS recursive algorithm

看板Prob_Solve (計算數學 Problem Solving)作者 (straw man)時間10年前 (2014/12/30 01:02), 10年前編輯推噓1(1推 0噓 11→)
留言12則, 3人參與, 最新討論串1/1
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://www.ptt.cc/bbs/Prob_Solve/M.1419872555.A.43D.html
推
12/30 02:44, , 1F
DFS生成樹沒有cross edge。
12/30 02:44, 1F
→
12/30 02:44, , 2F
tree edge一定有某端是另一端父親。
12/30 02:44, 2F
→
12/30 06:28, , 3F
樓上在 undirected graph 裡是對的, directed graph DPS
12/30 06:28, 3F
→
12/30 06:29, , 4F
是可能有 cross edge 的. 原 po: 你的作法是什麼? 複雜度是?
12/30 06:29, 4F
→
12/30 06:30, , 5F
用 color 判斷有點奇怪, 因為 DFS 跑完每個點應該都是黑色..
12/30 06:30, 5F
題目應該是問有向圖，沒有限定是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
→
12/30 13:40, , 6F
這個判斷應該是對的, 可惜 u.color == gray 只有 DFS 到一半
12/30 13:40, 6F
→
12/30 13:41, , 7F
的時候會成立. 想想看 u.d 和 u.f 存了什麼? 怎麼用他們重建
12/30 13:41, 7F
→
12/30 13:41, , 8F
「u.color == gray」成立的「時間」?
12/30 13:41, 8F
恩恩 這也是目前卡住的地方ORZ ※ 編輯: jb679123 (140.123.103.109), 12/30/2014 15:15:53
→
01/05 23:01, , 9F
現在回好像有點遲XD 總之需要考慮各種edge的特性
01/05 23:01, 9F
→
01/05 23:02, , 10F
forward跟back edge滿足一個是另一個的ancestor
01/05 23:02, 10F
→
01/05 23:02, , 11F
d跟f可以幫助你判斷這件事
01/05 23:02, 11F
→
01/05 23:02, , 12F
然後pi幫助你判斷他是不是tree edge
01/05 23:02, 12F
感謝a大的補充XDD ※ 編輯: jb679123 (140.123.214.127), 01/10/2015 16:03:42
‣ 更多 jb679123 的文章
文章代碼(AID): #1KeOahGz (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 jb679123 的文章
文章代碼(AID): #1KeOahGz (Prob_Solve)