アルゴリズム設計マニュアル(S.S. スキーナ)を読み返していて細かい誤植があった。
場所は日本語版 アルゴリズム設計マニュアル 上(S.S. スキーナ) p.196, l.1 でサンプルコード内の条件分岐。
誤植な気がしたけど自信が持てなかったので調べたり実装したのでメモを残す。
問題: 関節点
無向グラフ \(
G(V,E)\) において\(
v /in V\)となる頂点\(
v\)で\(
G-v\)の連結成分数が\(
G\)より大きくなるものを切断点(cut vertex)や関節点(articulation point)と呼ぶ。
アルゴリズム: DFS
著書ではDFSで解いていた。同じくDFSで求められるLowLinkというノード\(
v\)の属性を計算すると綺麗に解ける。
無向グラフはDFSを用いて各辺を木辺(tree edge)と逆辺(back edge)に分類できる。
このように作られる木を深さ優先探索木(DFS tree)と呼ぶ。
(逆辺は閉路があることに対応する)
関節点は次の3つのいずれかに該当する。
| 関節点の候補 |
定義 |
| 子を2つ以上もつDFS treeの根 |
DFS treeが2以上の子ノードを持つ場合にルートノードは関節点 |
| ブリッジの切断点 |
\(
v\)の子孫から最大1つの逆辺で戻れる点が\(
v\)である時の\(
v\)とその親(\(
parent(v)\))は関節点 |
| 親の切断点 |
要定義 \(
v\)の子孫から最大1つの逆辺で戻れる点が\(
v\)の親である時その親(\(
parent(v)\))は関節点 |
本でみつけた誤植はブリッジの切断点を判定するコードの中にあった。
ブリッジの切断点の親を関節点として登録するコードはルートノードの場合は関節点となるルートノードの条件(子を2つ持つ)を満たすか確認する必要がある。
そうでなければ、ブリッジの端点から伸びるエッジがないため連結成分が増えない。
この検証はDFS treeのルートノードの検証で行う。
そのため関節点の列挙だけを目的にする場合、ブリッジの親側の端点がルートノードの場合は除外して構わない。
寄り道: Lowlink
ブリッジの切断点と親の切断点は
Lowlinkを用いた判定では判定基準が2つに減るため、少しコードが単純化されるように思えた。
まず2つの値を定義する。
| 値 |
定義 |
| \(
ord(v)\) |
DFS tree構築時のアクセス順序(訪問時刻) |
| \(
low(v)\) |
\(
v\)から高々1回の逆辺でたどり着けるノード(\(
u\))の最小訪問時刻(\(
\min(ord(u))\)) |
他のブログとかだと関数じゃなくて下付きで記載しているところが多かった。
| 関節点の候補 |
定義 |
| 子を2つ以上もつDFS treeの根 |
次数(degree,valency)2以上のDFS treeのルートノード |
| ブリッジの切断点 |
ルートノードではない次を満たすノード\(
u\)、ある\(
u\)の子ノード\(
v\)が存在し\(
ord(u) \le low(v)\) |
候補が少ないので書くのが楽だ。基準に不等号が入りブリッジの切断点の基準が広い。
実装(Go)
それぞれ実装してみる。基礎となるグラフは隣接リストで表現する。
汚いコードになった。久しぶりにプログラムを書いたうえ一つ目は書き捨てなのに著書に似せて無名関数を使うように書いてしまった。
仕方ない。
著書に近いDFS
著書と近づけるために無名関数を渡す形で実装した。
c.lateが著書のprocess_vertex_late(int v)に対応してる。
this… とコメントしてるところが著書で漏れている条件。
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
|
c.late = func(c *context, u int) {
isRoot := c.parent[u] < 1
if isRoot {
if treeOutDegree[u] > 1 {
articulations[u] = struct{}{}
}
} else {
if reachable[u] == c.parent[u] {
// parent
if c.parent[c.parent[u]] > 0 { // parent isn't root
articulations[c.parent[u]] = struct{}{}
}
} else if reachable[u] == u {
// bridge
// this conditional branch is required!!
if c.parent[c.parent[u]] > 0 { // parent isn't root
articulations[c.parent[u]] = struct{}{}
}
if treeOutDegree[u] > 0 { // u have children
articulations[u] = struct{}{}
}
}
}
uTime := c.entryTime[reachable[u]]
pTime := c.entryTime[reachable[c.parent[u]]]
if uTime < pTime {
reachable[c.parent[u]] = reachable[u]
}
}
|
Lowlinkを明示的に意識したDFS
lowlink 版はこんな感じになった。
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
package main
import (
"fmt"
)
func main() {
g := loadGraph()
for a := range findArticulation(g) {
fmt.Printf("articulation: %d\n", a)
}
}
type none struct{}
var mark none = struct{}{}
func findArticulation(g *graph) (articulations map[int]none) {
// write code as dfs
s := newDfsState(g)
s.findArticulation(0, 1, 0)
return s.articulations
}
type dfsState struct {
// lowlink
ord map[int]int
low map[int]int
// result
articulations map[int]none
// standard dfs
g *graph
discovered map[int]none
finished map[int]none
parent map[int]int
childNum map[int]int
}
func newDfsState(g *graph) *dfsState {
return &dfsState{
g: g,
ord: make(map[int]int),
low: make(map[int]int),
discovered: make(map[int]none),
finished: make(map[int]none),
parent: make(map[int]int),
childNum: make(map[int]int),
articulations: make(map[int]none),
}
}
func (s *dfsState) findArticulation(p, u int, ord int) int {
ord++
s.parent[u] = p
s.discovered[u] = mark
s.ord[u] = ord
s.low[u] = ord
for _, v := range s.g.edges[u] {
if v == p {
continue
}
switch s.getEdgeType(u, v) {
case tree:
s.childNum[u]++
ord = s.findArticulation(u, v, ord)
default:
// back
if s.ord[v] < s.low[u] {
s.low[u] = s.ord[v]
}
}
}
// late phase
// set parent's low
uLow := s.low[u]
pLow := s.low[s.parent[u]]
if uLow < pLow {
s.low[s.parent[u]] = uLow
}
// judge articulation
if isRoot := s.parent[u] < 1; isRoot {
if s.childNum[u] > 1 {
s.articulations[u] = mark
}
} else if s.low[u] >= s.ord[u] && s.childNum[u] > 1 {
s.articulations[u] = mark
}
s.finished[u] = mark
return ord + 1
}
type edgeType int
const (
tree edgeType = 0 + iota
back
)
func (s dfsState) getEdgeType(u, v int) edgeType {
if _, ok := s.discovered[v]; !ok {
return tree
}
return back
}
func loadGraph() *graph {
var n, m int
fmt.Scan(&n, &m)
g := newGraph(n)
var u, v int
for i := 0; i < m; i++ {
fmt.Scan(&u, &v)
g.addEdge(u, v)
}
return g
}
type graph struct {
num int
edges map[int][]int
}
func newGraph(num int) *graph {
return &graph{
num: num,
edges: make(map[int][]int, num),
}
}
func (g *graph) addEdge(u, v int) {
g.edges[u] = append(g.edges[u], v)
g.edges[v] = append(g.edges[v], u)
}
|
