#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)

Java 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
class Solution {
public List<List<Integer>> findBridges(int n, List<List<Integer>> edges) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) graph.put(i, new HashSet<>());
for (List<Integer> edge : edges) {
graph.get(edge.get(0)).add(edge.get(1));
graph.get(edge.get(1)).add(edge.get(0));
}
List<List<Integer>> res = new ArrayList<>();
boolean[] visited = new boolean[n];
int[] lowlink = new int[n];
int[] id = new int[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, -1, 0, graph, id, lowlink, visited, res);
}
}
return res;
}
private void dfs(int v, int parent, int i, Map<Integer, Set<Integer>> graph, int[] id, int[] lowlink, boolean[] visited, List<List<Integer>> res) {
lowlink[v] = i;
id[v] = i;
visited[v] = true;
for (int adj : graph.get(v)) {
if (adj != parent) {
if (!visited[adj]) {
dfs(adj, v, i + 1, graph, id, lowlink, visited, res);
lowlink[v] = Math.min(lowlink[v], lowlink[adj]);
if (id[v] < lowlink[adj]) {
res.add(Arrays.asList(v, adj));
}
} else {
lowlink[v] = Math.min(lowlink[v], id[adj]);
}
}
}
}
}

Comments

01/03/2020