Finding bridge of not isolated vertices

I need to create a cycle that goes through the array of graph edges and finds all non isolated bridges( its vertices have to be not isolated) in between two connected components.

Any suggestions or examples would be great. Thanks in advance.

Answer 1

[Christine Tobler]

There is no functionality for MATLAB's graph class that would compute the bridges / cut edges.

If performance is not a main concern, you could go by definition: For each edge, try removing that edge and check shortestpath to see if there is still a connection between those nodes. If no, that edge is a bridge. You'd need to look at rmedge and shortestpath functions for this. An alternative to calling shortestpath would be to call conncomp and check if the number of connected components has increased - this might be slightly more expensive.

One more thing you could do to limit the amount of edges that are candidates for being a bridge is to call biconncomp. The second output contains the articulation points (or cut vertices), and according to Wikipedia, "The two endpoints of a bridge are articulation vertices unless they have a degree of 1, although it may also be possible for a non-bridge edge to have two articulation vertices as endpoints." So if the two endpoints of an edge aren't articulation points, we know ahead of time that this edge cannot be a bridge.