[理工] 資結 articulation point

看板Grad-ProbAsk作者 (卡布里多)時間5年前 (2019/01/12 18:03), 5年前編輯推噓3(3推 0噓 12→)
留言15則, 5人參與, 5年前最新討論串1/1
https://i.imgur.com/eKgrP4E.jpg
之前上課老師舉的例子 其中一個步驟是要在DFS spanning tree中找出Back edge 想請問一下該怎麼找 為何頂點0和頂點3 頂點5到頂點3 頂點8和頂點3之間沒有Back edge 麻煩各位解惑一下 感謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.115.114 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1547287383.A.D46.html ※ 編輯: Capelito (218.173.115.114), 01/12/2019 18:13:37
推
01/12 18:19, 5年前 , 1F
至少給個原圖吧== 在無向圖除了樹邊剩下的都是back edge
01/12 18:19, 1F
→
01/12 18:39, 5年前 , 2F
01/12 18:39, 2F
→
01/12 18:40, 5年前 , 3F
抱歉 因為查了之前別人問的還有看其他人的筆記發現他們
01/12 18:40, 3F
→
01/12 18:41, 5年前 , 4F
都只有附上DFS spanning tree
01/12 18:41, 4F
推
01/12 18:42, 5年前 , 5F
無向圖你任選一點開始跑DFS，沒走到的邊就是back edge
01/12 18:42, 5F
→
01/12 18:57, 5年前 , 6F
真的耶 謝謝樓上
01/12 18:57, 6F
→
01/12 18:57, 5年前 , 7F
想再問一下 都是如何直接畫出上面那樣的spanning tree呢
01/12 18:57, 7F
→
01/12 18:58, 5年前 , 8F
本來都是畫這種 https://i.imgur.com/Gvn8zPA.jpg
01/12 18:58, 8F
推
01/12 19:07, 5年前 , 9F
你畫的跟他畫的是同構 所以一樣
01/12 19:07, 9F
→
01/12 19:28, 5年前 , 10F
但是後面要求low值用我畫的那種好像不太好找
01/12 19:28, 10F
→
01/12 19:29, 5年前 , 11F
是要慢慢調整成上面的樣子嗎 還是有其他方法
01/12 19:29, 11F
→
01/12 19:30, 5年前 , 12F
因為我看別人都直接畫出來
01/12 19:30, 12F
→
01/12 19:40, 5年前 , 13F
你跑DFS的起點就是root,接著往下畫，這樣畫的原因
01/12 19:40, 13F
→
01/12 19:40, 5年前 , 14F
是畫出back edge後看low比較好看
01/12 19:40, 14F
→
01/12 23:47, 5年前 , 15F
謝謝各位的回覆
01/12 23:47, 15F
‣ 更多 Capelito 的文章
文章代碼(AID): #1SERjNr6 (Grad-ProbAsk)