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(V2)

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을 활용함.
  • GG은 같은 scc component를 가짐.
    • u and v are reachable from each other in G iff they are reachable from each other in G.
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)=minuU{u.d}라고 하자.
    • f(U)=maxuU{u.f}라고 하자.
  • White-path theorem

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

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

    • C,C가 DG G=(V,E)의 distinct scc라고 하자. uC, vC인 edge (u,v)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)E이므로, 임의의 vertex wC에 대해 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)인 경우, yC의 first discovered vertex라고 하자.
      • time y.dC의 모든 vertex는 unvisited고, yzC.V에 white path를 가진다.
      • y.dwC.V도 white이다.
      • (u,v)가 존재하므로 wC에 대해 (y,a)는 존재할 수 없다.
      • 따라서 임의의 vertex wC에 대해 w.f>y.f이고, f(C)>f(C)이다.
  • Corollary 22.15
    • C,C가 distinct scc라고 하자. uC,vC(u,v)E이 존재하면 f(C)<f(C)이다.
  • Theorem 22.16
    • SCC procedure는 G의 scc를 correctly compute한다.
      • induction으로 증명한다.
      • finishing order로 G의 DFS tree를 만들었을 때, 처음 k개의 tree가 scc라고 하자.
        • k=0은 trivial하다.
        • kth DFS tree가 scc일 때, k+1th tree가 생성되었다고 하자.
        • 이 tree의 root는 u라고 하고, u는 scc C의 element라고 하자.
        • 방문되지 않은 임의의 C에 대해 u.f=f(C)>f(C)이다.
        • C의 나머지 모든 vertices는 white이다.
        • white theorem에 의해서 Cu의 descendant이다.
        • Colloarary 22.15에 의해서 GTC를 연결하지 않는 임의의 edge는 이미 visit되었다.
        • 따라서, C를 제외한 scc는 G의 DFS 중 u의 descendant이다.
        • 따라서, Gu로부터의 모든 vertices는 정확히 하나의 scc를 이룬다.

Python code

boj 2150

 

 

Minimum Spanning Tree

  • minimum spanning tree는 undirected weighted graph G=(V,E)에서 모든 vertex를 포함하는 tree 중 total weight w(T)=(u,v)Tw(u,v)가 minimize되는 것을 말한다.
  • 주로 Kruskal’s algorithm과 Prim’s algorithm이 쓰인다.
  • 각각 binary heap으로 O(ElgV)로 만들 수 있고, Fibonacci heap을 쓰면 O(E+VlgV)로 만들 수 있다.
  • 둘 다 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{(u,v)}도 subset of some MST여야 한다.
      • 이러한 edge를 safe edge라고 한다.
  • Teminologies
    • cut (S,VS) 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(ElgE)
    • |V|O(E)의 find-set과 union operation 수행한다.
    • 따라서 O((V+E)α(V))=O(Eα(V))=O(ElgV)=O(ElgE)이다.

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(lgV)임.
        • 따라서 O(VlgV)
      • for loop는 |E|번 iterate함.
        • 따라서 O(ElgV)
      • 전체 time은 O((V+E)lgV)=O(ElgV)
    • Fibonacci heap
      • O(E+VlgV)

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.