[理工] 资结 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

谢谢各位的回复

继续阅读