Re: [jgrapht-users] Count Bridges

[Rikless <eri...@gm...>]

Hi,

finding the bridges in a graph is quite simple:

- variable a = finding the number of connected sets in the initial graph
- clone the graph

for all edges
 remove edge in the clone
 variable b = finding the number of connected sets in the modifed cloned
graph
 if the number of connected sets is b == a+1
  this edge is a bridge

Time complexity for this algorithm is O(V+E) for the connectivity inspector
and the loop aboce in O(E).
If V <<< E, the total time complexity is : O(E²).

Hope it help,
Regards,

Éric
-- 
View this message in context: http://jgrapht-users.107614.n3.nabble.com/Count-Bridges-tp1309515p1395252.html
Sent from the jgrapht-users mailing list archive at Nabble.com.