找到一個圖的周長

嘿，我需要輸出一個給定圖的周長表示爲一個鄰接矩陣。任何人都可以給我一些提示，我可以如何使用鄰接矩陣或鄰接列表來獲得一個周長圖表？由於找到一個圖的周長

例子：

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

來源

2012-10-15 Rennos

「圖的周長是圖中包含的最短週期的長度」[1]（http://en.wikipedia.org/wiki/Girth_（graph_theory）） –

我知道這一點。問題是如何使用矩陣或列表來獲得最短週期。 – Rennos

該算法將找到最短週期的長短：

- 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's algorithm的是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-15 06:32:30

它更便宜（O（V^3））之前的算法，如果你從各個點上運行的Dijkstra並且每輪取距離該給定源的最大距離。然後採取這些元素的最大值，那就是周長。

來源

2013-02-07 18:04:08

在基於BFS的http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf上有一個算法，其複雜度爲O（VE）。這是針對無向圖（例如，您的示例相鄰矩陣是對稱的）。另見https://github.com/jaspervdj/Genus/blob/master/src/genus/FindGirth.java。

來源

2013-08-28 21:41:09

在Sage

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-24 12:59:26

的曲線圖的周長是包含在圖即具有儘可能少的總和一個週期最短的週期的長度（可以是負的，如果圖形具有負週期）。查找周長的最簡單方法是在給定圖形上（V < = 400）運行Floyd Warshall算法（在O（V^3）時間內），並存儲每個二維數組之間的距離。之後，對每個可能的頂點（在O（V）時間）迭代dist [i] [i]，檢查是否存在以頂點i開始並以頂點i結束的循環，然後取最小值從dist [i] [i]獲得的可能值。

來源

2016-12-31 17:12:34

找到一個圖的周長

回答

相關問題