I need to output the girth of a given graph represented as an adjacency matrix.Could anyone give me some hints how i can use an adjacency matrix or an adjacency list to obtain the girth of a graph?
Example:
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
This algorithm will find the length of the shortest cycle:
- 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.
The time complexity is of the Dijkstra's algorithm is O(v^2), so this algorithm is O(v^4).
If your graph is sparse, you can convert to a neighbor-list representation and then run the previous algorithm in O(v^2+e*(e+v*log(v)))=O(v^2+e^2+v*e*log(v))