作者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/cn.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