Graph Traversal

  • 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은 $V$번 수행됨.
      • 각 enqueue, dequeue는 $O(1)$
      • 따라서 $O(V)$
    • 각 vertex 방문 시 adjacent list 탐색
      • adjacency list의 length는 $Θ(E)$
      • 따라서 scanning은 $O(E)$
    • 전체 time complexity는 $O(V+E)$
    • adjacency matrix를 쓰면 $O(V^2)$

Shortest Path

  • BFS는 unweighted graph에서 shortest path를 찾는데 쓸 수 있음.

 

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에서 $Θ(E)$로 explore됨.
    • 따라서 DFS의 time complexity는 $Θ(V+E)$

Python Code

BOJ 1260번 풀이

 

Topological Sort

  • DAG $G = (V,E)$에서 linear order에 따라 graph를 sort
  • DFS를 post-order로 탐색하면 됨.
    • 헷갈렸던 부분: track을 pre-order로 구한 후 prepend하면 동치인지?
      • 동치 아님
      • 반례: 1→2, 1→3, 3→2
  • Time complexity: $Θ(V + E)$

Python Code

BOJ 2252

 

Strongly Connected Components

  • strongly connected component는 directed graph에서 두 vertex $u, v$가 양방향의 path $p(u,v), p(v,u)$가 모두 존재하는 경우를 의미함.

Finding SCC

  • $G^\top$을 활용함.
  • $G$와 $G^\top$은 같은 scc component를 가짐.
    • $u$ and $v$ are reachable from each other in $G$ iff they are reachable from each other in $G^\top$.
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

    • $u.d$를 discovery time, $u.f$를 finishing time이라고 하자.
      • discovery time은 pre-order traversal, finishing time은 post-order traversal
    • $d(U)=\min _{u\in U} \{u.d\}$라고 하자.
    • $f(U) = \max_{u\in U} \{u.f\}$라고 하자.

  • White-path theorem

    • DFS forest에서 $v$는 $u$의 descendant iff time $u.d$에서 unvisited vertex로 구성된 path $p(u,v)$가 존재

  • Lemma 22.13

    • $G$의 두 distinct scc $C, C'$에 대해 $u,v\in G$와 $u', v' \in G$가 있을 때, $p(u,u')$가 존재하면 $p(v,v')$는 존재할 수 없다.
    • Proof $G$가 $p(v',v)$를 contain하면, G는 $p(u,u'), p(u',v')$와 $p(v',v), p(v,u)$도 contain한다. 따라서 $C, C'$가 distinct하다는 전제에 모순된다. $\blacksquare$
    • 당연한 Lemma다.

  • Lemma 22.14

    • $C,C'$가 DG $G=(V,E)$의 distinct scc라고 하자. $u\in C$, $v \in C'$인 edge $(u,v)\in E$가 존재하면 $f(C) > f(C')$이다.
    • 직관적으로 생각하면, C→C’일 때, C’가 먼저 탐색이 끝나지 않으면 C와 C’는 distinct scc가 될 수 없다. C가 먼저 탐색할 경우 C’까지 넘어오기 때문이다.
    • Proof
      • $d(C)
      • $x.d$에서, $C,C'$의 모든 vertex는 unvisited
      • $(u,v)\in E$이므로, 임의의 vertex $w\in C'$에 대해 $x.d$ time에 $p(x,w)=p(x,u)+(u,v)+p(v,w)$가 존재한다.
      • White-path theorem에 의해 $p(x,w)$가 존재하고, $C, C'$의 모든 vertices는 $x$의 descendent가 된다.
    • $d(C) > d(C')$인 경우, $y$를 $C'$의 first discovered vertex라고 하자.
      • time $y.d$에 $C'$의 모든 vertex는 unvisited고, $y$는 $\forall z \in C'.V$에 white path를 가진다.
      • $y.d$에 $\forall w \in C.V$도 white이다.
      • $(u,v)$가 존재하므로 $w \in C$에 대해 $(y, a)$는 존재할 수 없다.
      • 따라서 임의의 vertex $w \in C$에 대해 $w.f > y.f$이고, $f(C)>f(C')$이다. $\blacksquare$
  • Corollary 22.15
    • $C, C'$가 distinct scc라고 하자. $u\in C, v \in C'$인 $(u,v)\in E^\top$이 존재하면 $f(C) < f(C')$이다.
  • Theorem 22.16
    • SCC procedure는 $G$의 scc를 correctly compute한다.
      • induction으로 증명한다.
      • finishing order로 $G^\top$의 DFS tree를 만들었을 때, 처음 $k$개의 tree가 scc라고 하자.
        • $k=0$은 trivial하다.
        • $k$th DFS tree가 scc일 때, $k+1$th tree가 생성되었다고 하자.
        • 이 tree의 root는 $u$라고 하고, $u$는 scc $C$의 element라고 하자.
        • 방문되지 않은 임의의 $C'$에 대해 $u.f = f(C) > f(C')$이다.
        • $C$의 나머지 모든 vertices는 white이다.
        • white theorem에 의해서 $C$는 $u$의 descendant이다.
        • Colloarary 22.15에 의해서 $G^T$의 $C$를 연결하지 않는 임의의 edge는 이미 visit되었다.
        • 따라서, $C$를 제외한 scc는 $G^\top$의 DFS 중 $u$의 descendant이다.
        • 따라서, $G^\top$의 $u$로부터의 모든 vertices는 정확히 하나의 scc를 이룬다. $\blacksquare$

Python code

boj 2150

 

 

Minimum Spanning Tree

  • minimum spanning tree는 undirected weighted graph $G=(V,E)$에서 모든 vertex를 포함하는 tree 중 total weight $w(T)=\sum_{(u,v)\in T} w(u,v)$가 minimize되는 것을 말한다.
  • 주로 Kruskal’s algorithm과 Prim’s algorithm이 쓰인다.
  • 각각 binary heap으로 $O(E\lg V)$로 만들 수 있고, Fibonacci heap을 쓰면 $O(E + V\lg V)$로 만들 수 있다.
  • 둘 다 greedy algorithm 계열이다.

 

Generic MST

  • MST를 만들기 위해서, subset of edges $A$는 다음 조건을 만족시키며 edge를 선택하면 된다.
    • Prior to each iteration, $A$ is a subset of some MST.
    • edge $(u,v)$가 있을 때, $A\cup\{(u,v)\}$도 subset of some MST여야 한다.
      • 이러한 edge를 safe edge라고 한다.
  • Teminologies
    • cut $(S, V-S)$ of an undirected graph $G=(V,E)$는 $V$의 partition이다.
      • 전체 vertex의 subset을 구분하는 경계를 말한다.

 

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은 $O(V)$에 수행된다.
    • sorting the edges $O(E\lg E)$
    • $|V|$번 $O(E)$의 find-set과 union operation 수행한다.
    • 따라서 $O((V+E)α(V))= O(Eα(V)) = O(E\lg V) = O(E\lg E)$이다.

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으로 구현했을 때
      • $|V|$번 loop함
      • min extraction은 $O(\lg V)$임.
        • 따라서 $O(V\lg V)$
      • for loop는 $|E|$번 iterate함.
        • 따라서 $O(E\lg V)$
      • 전체 time은 $O((V+E)\lg V)=O(E\lg V)$
    • Fibonacci heap
      • $O(E + V\lg V)$

Python code

boj 1922

Refereces

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009.