1

由于我是图形新手,我没有得到可以清楚地解释如何在图形中找到关节点的算法。请任何人解释一下?提前谢谢

4

2 回答 2

0

一个简单的算法:

对于每个节点 N 所以: 1. 把它拿走 2. 计算连接组件的数量。通过dfs或bfs。如果这仍然是一个,继续循环。如果是两个,你已经找到了一个关节点。标记并继续循环。

这将在二次时间中运行。不确定是否有更好的算法。


编辑:我在这个网站上找到了一些 java 源代码:http : //algs4.cs.princeton.edu/41undirected/Biconnected.java.html

于 2013-04-09T21:01:50.880 回答
0

参考这个解释。我希望你会发现它很有用。

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

于 2013-12-12T14:13:14.407 回答