#6. Bridges (Cut Edges)

  1. What is Bridge?

    • Bridges are the edges in a graph, whose removal increases the number of connected components

  2. Why do we want find bridges?

    • Bridges are often hint at weak points, bottle necks or vulnerabilities in a graph
  3. How to find bridges?

    • If (v, w) is an edge in the graph, the edge is a bridge iff id(v) < lowlink(w)

Python Find Bridges

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Problem: find bridges in an undirected graph
def find_bridges(graph):
"""
:type graph: Dict[int, Set[int]]
:rtype: List[tuple(int, int)]
"""
if not graph:
raise Exception("invalid graph")
nodes = set()
lowlink = {}
visited = set()
for v in graph.keys():
for w in graph[v]:
nodes.add(v)
nodes.add(w)
lowlink
bridges = []
n = len(nodes)
for i in range(n):
if i not in visited:
dfs(i, -1, graph, lowlink, visited, bridges)
return bridges
def dfs(v, parent, graph, lowlink, visited, bridges):
"""
:type v: int
:type parent: int
:type graph: Dict[int, Set[int]]
:type lowlink: Dict[int]
:type bridges: List[tuple(int, int)]
"""
visited.add(v)
lowlink[v] = v
for adj in graph[v]:
if adj != parent:
if adj not in visited:
dfs(adj, v, graph, lowlink, visited, bridges)
lowlink[v] = min(lowlink[v], lowlink[adj])
else:
lowlink[v] = min(lowlink[v], adj)
if v < lowlink[adj]:
bridges.add((v, adj))

Comments

01/03/2020