作者Capelito (卡布里多)
看板Grad-ProbAsk
標題[理工] 資結 articulation point
時間Sat Jan 12 18:03:01 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547287383.A.D46.html
※ 編輯: Capelito (218.173.115.114), 01/12/2019 18:13:37
1F：推 z3588191: 至少給個原圖吧== 在無向圖除了樹邊剩下的都是back edge 01/12 18:19
3F：→ Capelito: 抱歉 因為查了之前別人問的還有看其他人的筆記發現他們 01/12 18:40
4F：→ Capelito: 都只有附上DFS spanning tree 01/12 18:41
5F：推 bmpss92196: 無向圖你任選一點開始跑DFS，沒走到的邊就是back edge 01/12 18:42
6F：→ Capelito: 真的耶 謝謝樓上 01/12 18:57
7F：→ Capelito: 想再問一下 都是如何直接畫出上面那樣的spanning tree呢 01/12 18:57
9F：推 meokay: 你畫的跟他畫的是同構 所以一樣 01/12 19:07
10F：→ Capelito: 但是後面要求low值用我畫的那種好像不太好找 01/12 19:28
11F：→ Capelito: 是要慢慢調整成上面的樣子嗎 還是有其他方法 01/12 19:29
12F：→ Capelito: 因為我看別人都直接畫出來 01/12 19:30
13F：→ ncdonalds123: 你跑DFS的起點就是root,接著往下畫，這樣畫的原因 01/12 19:40
14F：→ ncdonalds123: 是畫出back edge後看low比較好看 01/12 19:40
15F：→ Capelito: 謝謝各位的回覆 01/12 23:47