找到图的周长

Question

嘿伙计们,我需要输出一个给定图形的周长,表示为邻接矩阵.有人可以给我一些提示,我可以使用邻接矩阵或邻接列表来获得图形的周长吗？谢谢

例:

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

Answer 1

在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.

Answer 2

该算法将找到最短循环的长度：

- 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))