アルゴリズムイントロダクション第20章「基本的なグラフアルゴリズム」

 これはアルゴリズムイントロダクション第4版 第20章「基本的なグラフアルゴリズム」をやる。

私にとって既知の説明が多いので、サラッとやる。
20.1：グラフの表現
20.2：幅優先探索
20.3：深さ優先探索
20.4：トポロジカルソート
20.5：強連結成分

 前提集合論とグラフ理論の標準的な記法を用いる。

G = (V, E)：グラフ

V：頂点集合

E：辺集合

v∈V：頂点

(v, u)∈E：辺
Θ(|V|)の意味でΘ(V)を用いる。

binomialsheep

 20.1 グラフの表現隣接リスト表現と隣接行列表現がある。

隣接リストは、グラフが疎（sparse）な時にコンパクトに表現できる。

　- 使用メモリΘ(V+E)

隣接行列は、グラフが密（dense）な時や、2つの指定された頂点間に辺があるか否かを高速に判断する櫃業がある時に使う。
↑

隣接行列は、有向グラフにおいて逆向きの辺の列挙や存在確認が容易な点も便利。隣接リスト表現の場合は逆向きに辺を持つグラフも別途作るとかが必要。

競プロ的には、隣接リスト表現で連結リストの代わりにsetを用いた表現を使って、2頂点の辺の有無を高速に判定できるようにすることもある（練習問題20.1-8）

 練習問題20.1-1出次数は、リストの長さがO(1)で取得できるデータ構造であれば、Θ(V)。
for(int v = 0; v < graph.size(); v++) {
    out_degree[v] = graph[v].size();
}
入次数は、全辺を一度走査する必要がある。配列の初期化と合わせてΘ(V+E)。

 練習問題20.1-2

 隣接リストadj[1] = [2,3]

adj[2] = [1,4,5]

adj[3] = [1,6,7]

adj[4] = [2]

adj[5] = [2]

adj[6] = [3]

adj[7] = [3]

 隣接行列[[0,1,1,0,0,0,0]

, [1,0,0,1,1,0,0]

, [1,0,0,0,0,1,1]

, [0,1,0,0,0,0,0]

, [0,1,0,0,0,0,0]

, [0,0,1,0,0,0,0]

, [0,0,1,0,0,0,0]]

 練習問題20.1-3隣接リストの場合は、辺を走査して逆側に付ければよい。Θ(V+E)

隣接行列表現の場合は、隣接行列を走査する必要があるので、Θ(V^2)。

 練習問題20.1-4adj[v]の重複削除が本質。seen配列の初期化は使ったところだけ戻せばいい。

実用的にはソートしてeraseでもハッシュ表でもいいが。
const int N = graph.size());
vector<int> new_graph(N);
// Θ(V)で初期化
vector<bool> seen(N);
for(int v = 0; v < N; v++) {
    // 各頂点のリストを走査。合計でΘ(V+E)
    for(int u : graph[v]) {
        if(!seen[u]) {
            seen[u] = true;
            new_graph[v].push_back(u);
        }
    }
    // 使ったところだけ削除。合計でΘ(V+E)
    for(int u : new_graph[v]) {
        seen[u] = 0;
    }
}

 練習問題20.1-5
 隣接リスト各辺から二重ループする。

ただし同じ辺に戻らないようにだけ気を付ける。

計算量はΘ(VE)で、完全グラフの場合はΘ(V^3)。
計算量を証明する。

頂点vの出次数をd_vとして、\Sigma_v {d_v}^2の上界を評価できればいい。

\Sigma_v {d_v}^2≦max(d_v)\Sigma_v {d_v}で、max(d_v)=Vなので、Θ(VE)。

 隣接行列正方行列乗算。

単純にはΘ(V^3)だが、Strassenのアルゴリズムなどで改善可能。

→つまり、疎グラフでは隣接リストの方が高速だが、完全グラフの場合は隣接行列の方が高速。

 練習問題20.1-6補題１：共通シンクは、自身以外の全ての頂点から矢印が向いている（定義より）

補題２：共通シンクは1つしかない（∵2つあったらシンクの出次数が0にならない）

補題３：共通シンクがある時、それ以外の頂点は出次数が1以上（補題１より）

補題４：有向辺(v, u)がある時、頂点vは共通シンクではない

補題５：有向辺(v, u)がない時、頂点uは共通シンクではない
補題4、5より、共通シンク候補の2頂点間の辺の有無を調べるたびに共通シンク候補を1つずつ減らせる。

Θ(V)回掛けて共通シンク候補を1つまで減らし、あとはその1つの候補に対して愚直にΘ(V)掛けて入次数と出次数をチェックすればよい。
// 
const int N = graph.size();
int v = 0;
for(int u = 1; u < N; u++ {
    if(graph[v][u] == 1) {
        // vは共通シンクの可能性がない。uは共通シンクの可能性がある。
        v = u;
    } else {
        // vは共通シンクの可能性がある。uは共通シンクの可能性がない
    }
}

 練習問題20.1-7TODO：グラフラプラシアン
https://qiita.com/silva0215/items/0d1d25ef51b6865a6e15

 練習問題20.1-8負荷率をαとして期待探索時間はO(1+α)。

この方法を仮に隣接ハッシュ表表現と呼ぶ。

ハッシュ表の代わりに二分探索木を用いるものは隣接二分探索木表表現と呼ぶ

 辺（v, u）の存在確認隣接行列：Θ(1)
隣接ハッシュ表：Θ(1+α)
隣接二分探索木：Θ(log d_v)
隣接リスト：Θ(d_v)

 頂点vから出る辺の列挙隣接リスト：Θ(d_v)
隣接ハッシュ表：Θ(d_v)
隣接二分探索木：Θ(d_v)
隣接行列：Θ(V)

 頂点vに入る辺の列挙隣接行列：Θ(V)
隣接リスト：Θ(V+E)
隣接ハッシュ表：Θ(V+E)
隣接二分探索木：Θ(V+E)
※実際は、もし頂点vに入る辺の列挙が欲しいなら、もう1個逆向きの辺を張ったグラフを管理すればよいので、「頂点vから出る辺の列挙」になる。

 使用メモリ隣接リスト：Θ(V+E)
隣接二分探索木：Θ(V+E)
隣接ハッシュ表：Θ(V（ハッシュテーブル用に確保するメモリ量）)
隣接行列：Θ(V^2)

 その他隣接二分探索木の場合は、昇順など動的に順序を保った保持ができる
隣接リストの場合は、格納準での保持はできる
隣接ハッシュ表、隣接行列の場合は順序は保持できない（必要なら別途保持できるが）

binomialsheep

 20.2 幅優先探索幅優先探索（breadth-first search、BFS）

幅優先木：始点を根として、頂点uから到達可能な未訪問頂点vを発見した時に、辺(u,uvを木に加える操作を繰り返してできる木。uをvの先行頂点（predecessor）、親（parent）と呼ぶ。
BFSの実行時間はΘ(V+E)。

 練習問題20.2-1
 練習問題20.2-2
 練習問題20.2-3訪問済みか未訪問かのbool値（1ビット）でいい。

が、そもそも距離d[v]がINFでない場合はd[v]≦d[u]+1なので、更新不要。したがって距離配列だけあればよい。

 練習問題20.2-4各頂点からの辺列挙にΘ(V)掛かり、Θ(V^2)

 練習問題20.2-5始点からの最短距離は探索順によらない。

一方で、BFS木については同距離の頂点a, bがあり、辺(a,c)∈E, (b,c)の場合が順序依存。

 練習問題20.2-6

こんな感じのグラフを頂点aからBFSした場合、以下の木は得られない。aのあとにbを探索する場合、cを探索する場合を考えればよい。

 練習問題20.2-7ライバル関係があるところに辺を張ったグラフを構築して、二分グラフ判定。

BFSでもDFSでもいいが、各頂点を白黒に塗りながら探索して、矛盾が生じたらNo。

 練習問題20.2-8木の直径（diameter）を求める有名問題。

任意の頂点vから最遠点aをBFSで求め、次に頂点aから最遠点bをBFSで求めた時の、頂点a, bの距離が直径。

実行時間は2回のBFSなのでΘ(V+E)。

binomialsheep

 20.3 深さ優先探索教科書の説明の中で、「DFSは複数の始点から探索を繰り返すことがあるので、先行点部分グラフは森になる」とあるが、単に単一始点か複数始点かの差で、BFSとDFSの差ではないように思う。
DFSの事項時間はΘ(V+E)。

 括弧列DFSでは、発見時刻と終了時刻が括弧構造を持つ。

つまり、ある頂点uの発見を左括弧"(u"、終了を右括弧u)"とすると、正しい括弧列になる。
正しい括弧列なので、以下のいずれかになる
頂点vの区間と頂点uの区間は重なりがなく、u, vはどちらも子孫でない
頂点vの区間が頂点uの区間を完全に含み、uはvの子孫
頂点uの区間が頂点vの区間を完全に含み、vはuの子孫

 応用①：オイラーツアーhttps://maspypy.com/euler-tour-のお勉強
つまり、部分木は配列の区間で表せる。

配列の区間になると何が嬉しいかと言うと、（遅延）セグ木を用いることで、木に対する様々な操作を高速に行うことができる。

 応用②：数え上げなど括弧列と対応付けて、括弧列について知られた事実を用いることができる。
https://x.com/maspy_stars/status/1252056537259839489
https://x.com/catupper/status/994764430280835072
https://qiita.com/Nauclhlt/items/b700cf31f524214a0735

 辺の分類木辺（tree edge）：DFS木を構成する辺
後退辺（back edge）：祖先方向に向かう辺
前進辺（forward edge）：子孫方向に向かう辺で、木辺でないもの
横断辺（cross edge）：上記3つ以外

 練習問題20.3-1有向グラフの場合



i\backslashj

WHITE
GRAY
BLACK


WHITE
無し
無し
無し

GRAY
有り（木辺）
有り（後退辺）
有り（前進辺／横断辺）

BLACK
無し
無し
無し

無向グラフの場合



i\backslashj

WHITE
GRAY
BLACK


WHITE
無し
無し
無し

GRAY
有り（木辺）
有り（後退辺）
有り（後退辺）

BLACK
無し
無し
無し

有向グラフの場合、上図のように、A→B→Cを探索したあとに、A→Cという前進辺が現れることがある。無向グラフの場合はこれはC→Aで発見されているはずなので、後退辺になる。

（無向辺は、2つの有向辺ではなく、1つの辺として扱い、2回目に現れていた際は無視するらしい）

 練習問題20.3-2
q→s→v→w→t→x→z→y→r→u


頂点 u

d(u)
f(u)


q
1
20

s
2
7

v
3
4

w
5
6

t
8
19

x
9
12

z
10
11

y
13
18

r
14
17

u
15
16


 練習問題20.3-3(u (v (y (x x) y) v) u) (w (z z) w)

 練習問題20.3-4訪問済み頂点に訪れなければいいだけなので、よい。

 練習問題20.3-5trivial

 練習問題20.3-6trivial

 練習問題20.3-7
A→B、B→C、A→Dの順でDFSが進んだ場合が反例。

BからDに経路があり、B.d<D.dだが、DはBの子孫ではない。

 練習問題20.3-820.3-7のグラフで、A→D、A→B、B→CでDFSが進んだ場合が反例。

 練習問題20.3-9trivial

 練習問題20.3-10辺(u, x)、(y, u)があるとする。

xが既にDFSで探索済みで、yが未探索の状態で、uが始点となる場合が反例。

 練習問題20.3-11オイラー路の構築は、Hierholzer's Algorithmなど。

アイディアだけ示す。

まず、（準）オイラーグラフであるか判定し、始点と終点を決め打つ。

始点から辺を1回しか使わないようにDFSすると、必ず終点に到達する。終点から始点までのパスを復元し、まだ辺を使い切っていないところがあればそこを始点かつ終点とするDFSをしてそのパスを差し込む。これを繰り返すと得られる。

証明や具体例は以下など。

https://kokiymgch.hatenablog.com/entry/2017/12/07/193238
小銭の比喩は、辺を通ったか配列のビットで管理する代わりに小銭を辺に置けばよい。

 練習問題20.3-12trivial

 練習問題20.3-13始点uからDFSして、木辺以外が見つかったら、木辺以外の行き先がvとして、(u, v)に2通りの方法で行くことができる。逆に見つからなければ任意の頂点vについてuｋらvへ至る単純路は高々1つしかない。

これを全始点でやることで、計算量はΘ(V(V+E))。
密なグラフの場合、高速化できる。

まず、DAGかΘ(V+E)で判定する。DAGでなければ単結合でない。

次に、DAG順でDFSして、ある頂点に到達した時に木辺以外がないかチェックする。各頂点でΘ(V)で、合計でΘ(V^2)。
https://citeseerx.ist.psu.edu/document?doi=6b169c07f5588b8d3c3f335c71b8ef33d1b8772d
https://www.researchgate.net/publication/2688378_Determining_Single_Connectivity_in_Directed_Graphs

$i$ $\backslash$ $j$	WHITE	GRAY	BLACK
WHITE	無し	無し	無し
GRAY	有り（木辺）	有り（後退辺）	有り（前進辺／横断辺）
BLACK	無し	無し	無し

$i$ $\backslash$ $j$	WHITE	GRAY	BLACK
WHITE	無し	無し	無し
GRAY	有り（木辺）	有り（後退辺）	有り（後退辺）
BLACK	無し	無し	無し

頂点 $u$	$d(u)$	$f(u)$
$q$	1	20
$s$	2	7
$v$	3	4
$w$	5	6
$t$	8	19
$x$	9	12
$z$	10	11
$y$	13	18
$r$	14	17
$u$	15	16

binomialsheep

 20.4 トポロジカルソートDAG（Directed Acyclic Graph. 有効非巡回グラフ）を扱う。

DAGであるG=(V, E)のトポロジカルソートは、頂点集合上の線形順序のうち、Gが辺(u, v)を含むなら、uがvより先に現れるようなものである。
DPとか、プロジェクト管理とか、いろいろ応用がある。

 ジャッジAOJ GRL_4_B

アルゴ式 トポロジカルソート(D)

アルゴ式 トポロジカルソート(B)

 おまけ：トポロジカル感https://x.com/ngtkana/status/1691140585778987008
https://chatgpt.com/share/68814a37-1114-800e-8934-de7f7acecd02

 練習問題20.4-1

頂点
m
q
t
r
u
y
v
w
z
x
n
o
s
p


d(u)
1
2
3
6
7
9
10
11
12
18
20
21
22
24

f(u)
20
5
4
17
8
16
15
14
13
19
25
24
23
25

終了順（トポロジカルソートの逆順）：t, q, u, z, w, v, y, r, x, m, s, o, n, p

 練習問題20.4-2DAG上のDP。

頂点pから頂点vへの単純路を数えたい場合、頂点pから配るDPで「頂点uに到達する単純路の個数」を足していけばよい。
トポロジカルソートにΘ(V+E)、DPは見る頂点数がΘ(V)で遷移が合計でΘ(E)なので、合計でΘ(V+E)。

 練習問題20.4-3無向グラフなので、サイクルを持たないなら森であり、連結成分ごとに辺の数は頂点数-1本しかない。

全始点DFSをして、後退辺を見つけたらサイクルありと判定して探索を終了する。

後退辺がない場合は頂点数-1で探索が終わるので、Θ(V)。

 練習問題20.4-4偽。

反例：A→B→C→Aというグラフを考える。

20.4-1のアルゴリズムでは(C, B, A)を返すが、これは後退辺が2本ある。

一方で(A, B, C)という後退辺が1本の順序が存在する。

 練習問題20.4-5次数が0の頂点をキューに挿入する
キューから取り出した頂点をトポロジカル順に加え、頂点から伸びている辺を削除する（伸びている先の頂点の入次数を更新し、0になった頂点があればキューに加える）
アルゴ式 トポロジカルソート(B)は出次数を見ているので逆順だが、やっていることは同じ。

頂点	m	q	t	r	u	y	v	w	z	x	n	o	s	p
d(u)	1	2	3	6	7	9	10	11	12	18	20	21	22	24
f(u)	20	5	4	17	8	16	15	14	13	19	25	24	23	25

binomialsheep

 20.5 強連結成分SCC（Strongly Connected Component）。
https://manabitimes.jp/math/1250

 練習問題20.5-1どこまででも減らせる（0個にはならない、増えることはない、変えないことはできる）

A→B→C→……Z

のような26個の強連結成分からなるグラフがあった場合、Z→Aとすれば1個になるし、Z→Bとすれば2個になる。

 練習問題20.5-2
 練習問題20.5-3
 練習問題20.5-4
 練習問題20.5-5
 練習問題20.5-6
 練習問題20.5-7SCC分解して、その代表頂点のDAGを取る。

DAG上でこの順で隣接する全ての頂点対(u, v)について、辺(u, v)があればよい。
あればよいのは明らか。

ない場合、DAG順なのでvからu方向に戻ることができない。
SCC分解、トポソがΘ(V+E)、隣接する頂点だけ見ればいいのでΘ(V)で、全体としてΘ(V+E)。

 余談：半連結は弱連結とは異なる定義らしい半連結（semiconnected）：任意の頂点対(u, v)で一方向は経路が存在する

弱連結（weakly connected）：辺の向きを無視した時に連結
半連結ならば弱連結だが、逆は成り立たない。

例えば頂点集合{A,B,C}、辺集合{(A, B), (C, B)}。

 練習問題20.5-8

binomialsheep

 章末問題
 20-1 幅優先探索による辺の分類
 20-2 関節点，橋，および2 連結成分関節点（articulation point）：削除するとグラフが非連結になる頂点

端（bridge）：削除するとグラフが非連結になる辺
いわゆるlowlink。
http://algo-logic.info/bridge-lowlink/

 20-3 オイラー巡回路https://kokiymgch.hatenablog.com/entry/2017/12/07/193238

 20-4 到達可能性SCC分解して縮約したDAG上で後ろからDPする。

時間計算量はΘ(V+E)。

 20-5 平面的グラフの頂点への挿入とクエリ―頂点vがinsertされた時刻time[v]
頂点vの隣接点のうち最新に挿入されたものneigh[v]
を管理する。newest_neighborは明らかにO(1)。

insertは辺の分だけ愚直にかかるが、|E|<3|V|なのでならしO(1)。

頂点 $u$	$d(u)$	$f(u)$
$q$	1	20
$s$	2	7
$v$	3	4
$w$	5	6
$t$	8	19
$x$	9	12
$z$	10	11
$y$	13	18
$r$	14	17
$u$	15	16

頂点 $u$	$d(u)$	$f(u)$
$q$	1	20
$s$	2	7
$v$	3	4
$w$	5	6
$t$	8	19
$x$	9	12
$z$	10	11
$y$	13	18
$r$	14	17
$u$	15	16

頂点 $u$	$d(u)$	$f(u)$
$q$	1	20
$s$	2	7
$v$	3	4
$w$	5	6
$t$	8	19
$x$	9	12
$z$	10	11
$y$	13	18
$r$	14	17
$u$	15	16