finding bridges Algorithm
The finding bridges algorithm is an essential graph theory method that is used to identify and locate bridge edges in a connected graph. These bridge edges are crucial elements in the graph, as their removal would result in the disconnection of the graph, breaking it into two or more disconnected components. The algorithm is highly useful in various applications, such as network analysis, transportation planning, and power grid management, to find critical connections whose failure could lead to significant disruptions.
The algorithm operates by performing a depth-first search (DFS) traversal of the graph while maintaining information about the discovery times and low-link values of the vertices. The discovery time is the order in which the vertices are visited during the DFS traversal, while the low-link value represents the lowest discovery time reachable from a vertex in the DFS tree. When an edge (u, v) is found such that the discovery time of vertex v is greater than the low-link value of vertex u, it indicates that the edge (u, v) is a bridge. By identifying and marking all such bridge edges, the algorithm effectively highlights critical connections in the graph, enabling efficient planning and management of network resources to prevent or mitigate the impact of failures or disruptions.
# Finding Bridges in Undirected Graph
def computeBridges(graph):
id = 0
n = len(graph) # No of vertices in graph
low = [0] * n
visited = [False] * n
def dfs(at, parent, bridges, id):
visited[at] = True
low[at] = id
id += 1
for to in graph[at]:
if to == parent:
pass
elif not visited[to]:
dfs(to, at, bridges, id)
low[at] = min(low[at], low[to])
if at < low[to]:
bridges.append([at, to])
else:
# This edge is a back edge and cannot be a bridge
low[at] = min(low[at], to)
bridges = []
for i in range(n):
if not visited[i]:
dfs(i, -1, bridges, id)
print(bridges)
graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1, 3, 5],
3: [2, 4],
4: [3],
5: [2, 6, 8],
6: [5, 7],
7: [6, 8],
8: [5, 7],
}
computeBridges(graph)
