MATLAB Answers

Finding bridge of not isolated vertices

조회 수: 4(최근 30일)
Lukas Marcinkevicius
Lukas Marcinkevicius 2020년 12월 2일
편집: Christine Tobler 2020년 12월 2일
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.


Christine Tobler
Christine Tobler 2020년 12월 2일
편집: Christine Tobler 2020년 12월 2일
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by