怀疑求割点算法？？？？
算法基于以下原理：（1）如果根顶点的儿子数大于1，则根顶点是割点（2）如果一个点和这个点的子孙都不存在指向这个点祖先的后向边，则这个点为割点。实现时需要对每个结点记录一个low值，表示该结点的子孙能够到达的最小的深度，如果这个值小于或等于该点的深度，则该点为割点
例如我给一个图：
1 2 4(表示1与2，4有一条无向边，下同)
3 2 4
2 5
5 6 8
7 6 8
显然这个图中2 和5 是两个割点
深度优先搜索该图访问节点的顺序为1 2 3 4 5 6 7 8
并且1和4，5和8有回边
按照上面那个算法基本原理结果不是2 和5是割点阿 。。。。
谢谢各位了！！
9 个解决方案
#1
这段话楼主是在哪里看到的？好像翻译得不对，误人子弟！
1).The root of Gπ is an articulation point of G if and only if it has at least two children in Gπ.
2).Let v be a nonroot vertex of Gπ. Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v 。
1).根结点为割点，当且仅当它有两个或两个以上的子树。
2).其余结点v为割点，当且仅当 至少存在一个v的后代结点s，从s出发， 不可能通过s、s的子孙以及一条回边所组成的路径到达v的祖先。
1).The root of Gπ is an articulation point of G if and only if it has at least two children in Gπ.
2).Let v be a nonroot vertex of Gπ. Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v 。
1).根结点为割点，当且仅当它有两个或两个以上的子树。
2).其余结点v为割点，当且仅当 至少存在一个v的后代结点s，从s出发， 不可能通过s、s的子孙以及一条回边所组成的路径到达v的祖先。
#2
2,5,6为割点吧
#3
2和5是割点
#4
噢 。。。国内的教材翻译得好烂阿!!!!
#5
dlyme介意给个伪代码吗,谢谢啦
#6
这个网上好像比较多。这里就有一个：
http://hi.baidu.com/sophiaandphilem/blog/item/6651e8f807b5040fd8f9fd6b.html
http://hi.baidu.com/sophiaandphilem/blog/item/6651e8f807b5040fd8f9fd6b.html
#7
这个板块还有我一个关于汉密尔顿回路的问题,帮看看吧,先给你分了
#8
是那个Task Sequences问题吧？已经回复了。
另外，你的分给错了.
另外，你的分给错了.
#9
哦，不好意思啊 。。。。。
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。