#7. Articulation Points (Cut Vertex)

  1. What is Articulation Point?

    • Articulation points are the nodes in a graph, whose removal increases the number of connected components

  2. How to find articulation points?

    1. If an edge (v, w) is a bridge, then either v or w is an articulation point. But articulation points can exist without any bridges.
    2. If id(e.from) == lowlink(e.to), that means there is a cycle
    3. A cycle must be a connected component, and e.from is the starting node of the cycle, which indicates it’s an articulation point.
      • Except the starting node has no outgoing edges. Or only 1 outgoing edge, which is part of the cycle.
    4. So an articulation point must have 2 or more outgoing edges.

[Notes] The “outgoing” here is a logical outgoing, it does not mean the outgoing edge in directed graph, since the whole problem is on an undirected graph. It really means the edges connected to the node.

Python Find Articulation Points

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
52
53
54
55
56
57
# Problem: Find articulation points on a given graph
def articulation_points(graph):
"""
:type graph: Dict[int, Dict[int, int]]
:rtype: List[int], a list of articulation points in the graph
"""
res = []
if not graph:
return res
visited = set()
nodes = set()
lowlink = {}
candidates = set()
for v in graph.keys():
for w in graph[v].keys():
nodes.add(v)
nodes.add(w)
n = len(nodes)
for i in range(n):
if i not in visited:
dfs(i, -1, graph, lowlink, visited, candidates)
if i in candidates and i in graph and len(graph[i]) > 1:
res.append(i)
return res
def dfs(v, parent, graph, lowlink, visited, candidates):
"""
:type v: int
:type parent: parent
:type graph: Dict[int, Dict[int, int]]
:type lowlink: Dict[int, int]
:type visited: Set[int]
:type points: Set[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, candidates)
lowlink[v] = min(lowlink[v], lowlink[adj])
else:
lowlink[v] = min(lowlink[v], adj)
if v <= lowlink[adj]:
# when v < lowlink[adj], find a bridge
# when v == lowlink[adj], find a starting point of a cycle
candidates.add(v)

Comments

01/03/2020