我需要输出表示为邻接矩阵的给定图的周长。谁能给我一些提示，我如何使用邻接矩阵或邻接列表来获得图的周长？
例子：
graph one:
0 1 0 0
1 0 0 1
0 0 0 0
0 1 0 0
graph two:
0 1 0 0 1
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
The result:
Girth of graph 1: infinity
Girth of graph 2: 5
问问题
9546 次
5 回答
7
http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf有一个基于 BFS 的算法，复杂度为 O(VE)。这适用于无向图（例如，您的示例邻接矩阵是对称的）。另请参阅https://github.com/jaspervdj/Genus/blob/master/src/genus/FindGirth.java。
于 2013-08-28T21:41:09.200 回答
4
该算法将找到最短循环的长度：
- set `girth` to infinity
- for each edge
-- remove the edge from the graph
-- measure the distance between the edge endpoints
-- if `girth` is longer than distance+1
--- set `girth` to distance+1
-- return the edge to the graph.
Dijkstra 算法的时间复杂度是，O(v^2)所以这个算法是O(v^4)。
如果您的图是稀疏的，您可以转换为邻居列表表示，然后在O(v^2+e*(e+v*log(v)))=中运行前面的算法O(v^2+e^2+v*e*log(v))
于 2012-10-15T06:32:30.883 回答
1
如果你从所有点运行 dijkstra 并且每一轮都取到与给定源的最大距离，它会更便宜（O（v^3））。然后取这些元素中的最大值，这就是周长。
于 2013-02-07T18:04:08.817 回答
1
在鼠尾草
sage: G1 = Matrix([[0,1,0,0],[1,0,0,1],[0,0,0,0],[0,1,0,0]])
sage: G2 = Matrix([[0,1,0,0,1],[1,0,1,0,0],[0,1,0,1,0],[0,0,1,0,1],[1,0,0,1,0]])
sage: G1 = Graph(G1)
sage: G2 = Graph(G2)
sage: G1.girth()
+Infinity
sage: G2.girth()
5
于 2015-09-24T12:59:26.613 回答
1
图的周长是图中包含的最短环的长度，即具有最小可能和的环（如果图有负环，则可以为负）。找到周长的最简单方法是在给定的图（V<= 400）上运行 Floyd Warshall 算法（在 O(V^3) 时间内）并将每对之间的距离存储在二维数组中。之后对每个可能的顶点（在 O(V) 时间内）迭代 dist[i][i]，检查是否存在从顶点 i 开始并在顶点 i 结束的循环，然后取所有顶点中的最小值从 dist[i][i] 获得的可能值。
于 2016-12-31T17:12:34.307 回答