1- # Finding Bridges in Undirected Graph
2- def computeBridges (graph ):
1+ """
2+ An edge is a bridge if, after removing it count of connected components in graph will
3+ be increased by one. Bridges represent vulnerabilities in a connected network and are
4+ useful for designing reliable networks. For example, in a wired computer network, an
5+ articulation point indicates the critical computers and a bridge indicates the critical
6+ wires or connections.
7+
8+ For more details, refer this article:
9+ https://www.geeksforgeeks.org/bridge-in-a-graph/
10+ """
11+
12+
13+ def __get_demo_graph (index ):
14+ return [
15+ {
16+ 0 : [1 , 2 ],
17+ 1 : [0 , 2 ],
18+ 2 : [0 , 1 , 3 , 5 ],
19+ 3 : [2 , 4 ],
20+ 4 : [3 ],
21+ 5 : [2 , 6 , 8 ],
22+ 6 : [5 , 7 ],
23+ 7 : [6 , 8 ],
24+ 8 : [5 , 7 ],
25+ },
26+ {
27+ 0 : [6 ],
28+ 1 : [9 ],
29+ 2 : [4 , 5 ],
30+ 3 : [4 ],
31+ 4 : [2 , 3 ],
32+ 5 : [2 ],
33+ 6 : [0 , 7 ],
34+ 7 : [6 ],
35+ 8 : [],
36+ 9 : [1 ],
37+ },
38+ {
39+ 0 : [4 ],
40+ 1 : [6 ],
41+ 2 : [],
42+ 3 : [5 , 6 , 7 ],
43+ 4 : [0 , 6 ],
44+ 5 : [3 , 8 , 9 ],
45+ 6 : [1 , 3 , 4 , 7 ],
46+ 7 : [3 , 6 , 8 , 9 ],
47+ 8 : [5 , 7 ],
48+ 9 : [5 , 7 ],
49+ },
50+ {
51+ 0 : [1 , 3 ],
52+ 1 : [0 , 2 , 4 ],
53+ 2 : [1 , 3 , 4 ],
54+ 3 : [0 , 2 , 4 ],
55+ 4 : [1 , 2 , 3 ],
56+ },
57+ ][index ]
58+
59+
60+ def compute_bridges (graph : dict [int , list [int ]]) -> list [tuple [int , int ]]:
61+ """
62+ Return the list of undirected graph bridges [(a1, b1), ..., (ak, bk)]; ai <= bi
63+ >>> compute_bridges(__get_demo_graph(0))
64+ [(3, 4), (2, 3), (2, 5)]
65+ >>> compute_bridges(__get_demo_graph(1))
66+ [(6, 7), (0, 6), (1, 9), (3, 4), (2, 4), (2, 5)]
67+ >>> compute_bridges(__get_demo_graph(2))
68+ [(1, 6), (4, 6), (0, 4)]
69+ >>> compute_bridges(__get_demo_graph(3))
70+ []
71+ >>> compute_bridges({})
72+ []
73+ """
74+
375 id = 0
476 n = len (graph ) # No of vertices in graph
577 low = [0 ] * n
@@ -15,28 +87,14 @@ def dfs(at, parent, bridges, id):
1587 elif not visited [to ]:
1688 dfs (to , at , bridges , id )
1789 low [at ] = min (low [at ], low [to ])
18- if at < low [to ]:
19- bridges .append ([ at , to ] )
90+ if id <= low [to ]:
91+ bridges .append (( at , to ) if at < to else ( to , at ) )
2092 else :
2193 # This edge is a back edge and cannot be a bridge
22- low [at ] = min (low [at ], to )
94+ low [at ] = min (low [at ], low [ to ] )
2395
2496 bridges = []
2597 for i in range (n ):
2698 if not visited [i ]:
2799 dfs (i , - 1 , bridges , id )
28- print (bridges )
29-
30-
31- graph = {
32- 0 : [1 , 2 ],
33- 1 : [0 , 2 ],
34- 2 : [0 , 1 , 3 , 5 ],
35- 3 : [2 , 4 ],
36- 4 : [3 ],
37- 5 : [2 , 6 , 8 ],
38- 6 : [5 , 7 ],
39- 7 : [6 , 8 ],
40- 8 : [5 , 7 ],
41- }
42- computeBridges (graph )
100+ return bridges
0 commit comments