search

ZoranPandovski / al-go-rithms

:musical_note: Algorithms written in different programming languages - https://zoranpandovski.github.io/al-go-rithms/
Creative Commons Zero v1.0 Universal
1.33k stars 1.95k forks source link

C++ template for finding bridges and articulation points in a graph #3445

Closed the-good-boy closed 1 year ago

the-good-boy commented 1 year ago

Bridges We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all bridges in the given graph. screenshot-62-5893

The implementation needs to distinguish three cases: when we go down the edge in DFS tree, when we find a back edge to an ancestor of the vertex and when we return to a parent of the vertex.

To implement this, we need a depth first search function which accepts the parent vertex of the current node.

Articulation Points We are given an undirected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph. 1*TJLX4DRXYUdsfIM7u_NhBg

The implementation needs to distinguish three cases: when we go down the edge in DFS tree, when we find a back edge to an ancestor of the vertex and when we return to a parent of the vertex.

To implement this, we need a depth first search function which accepts the parent vertex of the current node.