Graph Traversal
Breadth-First Search
- Pseudocode
bfs(G, s):
visited = set()
Q = queue()
Q.enqueue(s)
while not Q.is_empty():
cur = Q.dequeue()
for v in G.adj(cur):
if v is not in visited:
Q.enqueue(v)
visited.add(v)
- Analysis
- queueing은
번 수행됨.- 각 enqueue, dequeue는
- 따라서
- 각 enqueue, dequeue는
- 각 vertex 방문 시 adjacent list 탐색
- adjacency list의 length는
- 따라서 scanning은
- adjacency list의 length는
- 전체 time complexity는
- adjacency matrix를 쓰면
- queueing은
Shortest Path
- BFS는 unweighted graph에서 shortest path를 찾는데 쓸 수 있음.
Depth-first Search
dfs(G):
visited = set()
for v in G.V:
if v not in visited:
dfs_visit(G, v, visited)
dfs_visit(G, v, visited):
visited.add(v)
for u in G.adj(v):
if u not in visited:
dfs_visit(G, u, visited)
- Analysis
dfs_visit
는 vertex당 한 번만 call됨.- 모든 adjenct vertex는 adjacency list에서
로 explore됨. - 따라서 DFS의 time complexity는
Python Code
Topological Sort
- DAG
에서 linear order에 따라 graph를 sort - DFS를 post-order로 탐색하면 됨.
- 헷갈렸던 부분: track을 pre-order로 구한 후 prepend하면 동치인지?
- 동치 아님
- 반례: 1→2, 1→3, 3→2
- 헷갈렸던 부분: track을 pre-order로 구한 후 prepend하면 동치인지?
- Time complexity:
Python Code
Strongly Connected Components
- strongly connected component는 directed graph에서 두 vertex
가 양방향의 path 가 모두 존재하는 경우를 의미함.
Finding SCC
을 활용함. 와 은 같은 scc component를 가짐. and are reachable from each other in iff they are reachable from each other in .
scc(G):
call dfs(G) to compute finishing time u.f
compute G.T
call dfs(G.T)
consider the vertices in order of decreasing u.f
get trees from dfs(G.T)
finishing time을 구하라는 것은 post-order traversal하라는 것
- 즉 위상정렬 후 tree의 말단부터 scc 수행
- 말단부터 하는 것은 transposed graph의 root이기 때문
- 이미 root이므로 dfs traversal하면 모든 scc를 찾을 수 있음.
- 다만 이는 scc(G)와 scc(G.T)가 identical함을 증명해야 함.
Notation
를 discovery time, 를 finishing time이라고 하자.- discovery time은 pre-order traversal, finishing time은 post-order traversal
라고 하자. 라고 하자.
White-path theorem
- DFS forest에서
는 의 descendant iff time 에서 unvisited vertex로 구성된 path 가 존재
- DFS forest에서
Lemma 22.13
의 두 distinct scc 에 대해 와 가 있을 때, 가 존재하면 는 존재할 수 없다.- Proof
가 를 contain하면, G는 와 도 contain한다. 따라서 가 distinct하다는 전제에 모순된다. - 당연한 Lemma다.
Lemma 22.14
가 DG 의 distinct scc라고 하자. , 인 edge 가 존재하면 이다.- 직관적으로 생각하면, C→C’일 때, C’가 먼저 탐색이 끝나지 않으면 C와 C’는 distinct scc가 될 수 없다. C가 먼저 탐색할 경우 C’까지 넘어오기 때문이다.
- Proof
- $d(C)
에서, 의 모든 vertex는 unvisited 이므로, 임의의 vertex 에 대해 time에 가 존재한다.- White-path theorem에 의해
가 존재하고, 의 모든 vertices는 의 descendent가 된다.
- $d(C)
인 경우, 를 의 first discovered vertex라고 하자.- time
에 의 모든 vertex는 unvisited고, 는 에 white path를 가진다. 에 도 white이다. 가 존재하므로 에 대해 는 존재할 수 없다.- 따라서 임의의 vertex
에 대해 이고, 이다.
- time
- Corollary 22.15
가 distinct scc라고 하자. 인 이 존재하면 이다.
- Theorem 22.16
- SCC procedure는
의 scc를 correctly compute한다.- induction으로 증명한다.
- finishing order로
의 DFS tree를 만들었을 때, 처음 개의 tree가 scc라고 하자. 은 trivial하다. th DFS tree가 scc일 때, th tree가 생성되었다고 하자.- 이 tree의 root는
라고 하고, 는 scc 의 element라고 하자. - 방문되지 않은 임의의
에 대해 이다. 의 나머지 모든 vertices는 white이다.- white theorem에 의해서
는 의 descendant이다. - Colloarary 22.15에 의해서
의 를 연결하지 않는 임의의 edge는 이미 visit되었다. - 따라서,
를 제외한 scc는 의 DFS 중 의 descendant이다. - 따라서,
의 로부터의 모든 vertices는 정확히 하나의 scc를 이룬다.
- SCC procedure는
Python code
Minimum Spanning Tree
- minimum spanning tree는 undirected weighted graph
에서 모든 vertex를 포함하는 tree 중 total weight 가 minimize되는 것을 말한다. - 주로 Kruskal’s algorithm과 Prim’s algorithm이 쓰인다.
- 각각 binary heap으로
로 만들 수 있고, Fibonacci heap을 쓰면 로 만들 수 있다. - 둘 다 greedy algorithm 계열이다.
Generic MST
- MST를 만들기 위해서, subset of edges
는 다음 조건을 만족시키며 edge를 선택하면 된다.- Prior to each iteration,
is a subset of some MST. - edge
가 있을 때, 도 subset of some MST여야 한다.- 이러한 edge를 safe edge라고 한다.
- Prior to each iteration,
- Teminologies
- cut
of an undirected graph 는 의 partition이다.- 전체 vertex의 subset을 구분하는 경계를 말한다.
- cut
Kruskal’s Algorithm
- union-find algorithm을 활용한다.
- 전체 graph에서 redundant하지 않은 edge 중 가장 싼 edge부터 greedy하게 고르는 방식이다.
- 동시에 여러 개의 tree를 만들고 마지막에 합친다.
kruskal(G, w):
mst = set()
for v in G.V:
make_set(v)
sort G.E by w
for (u,v) in G.E:
if find_set(u) != find_set(v):
mst.add((u,v))
union(u,v)
return mst
- Time Complexity
- make_set은
에 수행된다. - sorting the edges
번 의 find-set과 union operation 수행한다.- 따라서
이다.
- make_set은
Python Code
boj 1717 union-find boj 1197 mst
Prim’s Algorithm
- 하나의 tree를 중심으로 redundant하지 않은 edge 중 가장 싼 edge부터 greedy하게 고르는 방식이다.
- 하나의 tree를 확장한다.
- priority queue를 가지고 동작한다.
prim(G, w, r):
for u in G.V:
u.key = inf
u.π = null
Q = G.V
while Q:
u = extract_min(Q)
for v in G.adj(u):
if v in Q and w(u,v) < v.key:
v.π = u
v.key = w(u,v)
pseudocode가 좀 난해하게 적혀있는데, priority queue에는 edge를 넣는게 맞다. 코드 참조.
- Procedure
- priority queue를 가지고 방문하기 가장 저렴한 노드를 방문하고 mst에 edge를 추가한다.
- 방문한 node에 대해서 adjacent한 vertex들의 방문 비용을 update하고 priority queue에 넣는다.
- priority queue가 empty할 때까지 반복한다.
- Time Complexity
- binary min-heap으로 구현했을 때
번 loop함- min extraction은
임.- 따라서
- 따라서
for
loop는 번 iterate함.- 따라서
- 따라서
- 전체 time은
- Fibonacci heap
- binary min-heap으로 구현했을 때
Python code
Refereces
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.