[理工] 資結 articulation point Capelito PTT批踢踢實業坊

作者: Capelito (卡布里多) 2019-01-12 18:03:01

https://i.imgur.com/eKgrP4E.jpg
之前上課老師舉的例子
其中一個步驟是要在DFS spanning tree中找出Back edge
想請問一下該怎麼找
為何頂點0和頂點3 頂點5到頂點3 頂點8和頂點3之間沒有Back edge
麻煩各位解惑一下
感謝

作者: z3588191 2019-01-12 18:19:00

至少給個原圖吧== 在無向圖除了樹邊剩下的都是back edge

作者: Capelito (卡布里多) 2019-01-12 18:39:00

https://i.imgur.com/W16IMV1.jpg抱歉因為查了之前別人問的還有看其他人的筆記發現他們都只有附上DFS spanning tree

作者: bmpss92196 (bmpss92196) 2019-01-12 18:42:00

無向圖你任選一點開始跑DFS，沒走到的邊就是back edge

作者: Capelito (卡布里多) 2019-01-12 18:57:00

真的耶謝謝樓上想再問一下都是如何直接畫出上面那樣的spanning tree呢本來都是畫這種 https://i.imgur.com/Gvn8zPA.jpg

作者: meokay (我可以) 2019-01-12 19:07:00

你畫的跟他畫的是同構所以一樣

作者: Capelito (卡布里多) 2019-01-12 19:28:00

但是後面要求low值用我畫的那種好像不太好找是要慢慢調整成上面的樣子嗎還是有其他方法因為我看別人都直接畫出來

作者: ncdonalds123 (benben) 2019-01-12 19:40:00

你跑DFS的起點就是root,接著往下畫，這樣畫的原因是畫出back edge後看low比較好看

作者: Capelito (卡布里多) 2019-01-12 23:47:00

謝謝各位的回覆

繼續閱讀