[알고리즘] Chap.3 Decomposition of graphs

2006년 나온 알고리즘 책(S. Dasgupta et al.)을 공부하면서 개인적으로 정리한 노트입니다. 관련된 백준 문제를 풀어서 포스팅을 (언젠가) 올리면, 포스팅으로 대체할 생각입니다.

 

Chap.3은 이미 누군가 정리해둔 포스팅이 있습니다. 참고하면 좋을 것 같습니다.

Chap.3 정리: 또쟁 컴퓨터 공장
DFS 정리: victolee

 

3.1 Why graphs?

  - vertex(node, 정점), edge(간선)으로 이루어짐

  - Undirected/Directed, Cycle/Acyclic

  - Adjacency matrix

 

3.2 Deph-first search in undirected graphs

  - 깊이 우선 탐색!

    - 인접한 노드 중 하나를 깊게 탐색 -> 더 이상 탐색 못 하면 그 다음 인접한 노드 탐색 -> ...

      - stack 사용

    - 탐색을 못 한다? -> Back tracking 사용해서 이전 노드(부모 노드)로 돌아가서 인접 노드 찾음

 

  - Previsit/Postvisit ordering

    - Pre: 처음 노드를 탐색한 시점에 numbering

    - Post: 더 이상 뻗어나가지 못해 부모 노드로 돌아갈 때(back tracking) numbering 

 

3.3 Depth-first search in directed graphs

  - Forward/Back/Cross/Tree edge

    - Tree edge: DFS에서 탐색하는데 사용한 edge

    - Back edge: 자식 노드 -> 부모 노드를 잇는 edge, 존재하면 cycle 형성

    - Foward edge: 부모 노드 -> 자식 노드를 잇는 edge, 탐색 순서에 따라 tree edge가 될 수도 있음

    - Cross edge: 위 3가지 외 edge, 다른 tree를 잇는 edge 또는 자식 노드 -> 자식 노드를 잇는 edge

      - pre,post number 순서로도 Tree/Foward, Back, Cross edge 구분 가능

 

  - DAGs(Directed Acyclic Graphs)

    - Direct edge + Acyclic graph => 방향성이 있고, cycle이 없는 그래프

    - 특정 노드에서 출발해서 다시 자신으로 돌아오는 경로가 없음

    - 줄 세우기 가능(linearization)!

      - 시작 노드인 source와 끝 노드인 sink가 항상 최소 1개 이상 존재

    - 몇 가지 성질

      - Cycle이 없으므로, DFS 시 back edge가 없음

      - 모든 edge는 낮은 post number의 노드로 향함

 

  - 그럼 DAG를 어떻게 정렬할 수 있을까?

    - DFS를 수행하면서 source를 제거하고, 또 DFS를 수행하면서 source를 제거하고... 반복

      - O(V^2)

    - Topological sort

      - DFS에서 기록한 pre/post number를 통해 post 내림차순으로 정렬

      - DFS의 시간복잡도인 O(V+E) -> Linear time에 가능!

      - DAGs에서의 최단 거리를 찾는데 사용 가능

 

3.4 Strongly connected components(SCC)

  - 백준 2150번

  - SCC 내 node 임의의 A, B가 있다면, A -> B로 가는 path가 항상 존재함

  - 다른 SCC끼리는 cycle이 존재하지 않음(SCC X -> SCC Y edge가 존재하면, SCC Y -> SCC X edge는 존재하지 않음)

  - 이런 여러 SCC로 graph decomposition 가능

 

  - 그럼 어떻게 SCC 찾음?

    - Kosaraju's Algorithm

      - 좋은 예시

      - 1. DFS에서 구한 post number 기준 topological sort 수행

        - Post number 기준(먼저 탐색이 끝난 node부터 삽입)으로 node를 담은 stack 생성

        - Topological sort 결과 순서대로, source가 top에 위치하는 stack이 생김

      - 2. 모든 edge들의 방향을 바꾼, 역방향 그래프 생성

      - 3. stack의 top(기존 source)부터(pop) 역방향 그래프에서 DFS 수행

        - 이미 다른 SCC에 들어간 노드는 탐색하지 않음

        - DFS 끝날 때마다 하나의 SCC 생성

        - DFS 끝나면 다시 stack에서 pop 후 DFS 수행, 이미 SCC에 포함된 노드는 skip

      - 4. 완성!

      - 시간 복잡도 O(V+E)

 

    - Tarjan's Algorithm(책에는 없음)

      - 좋은 예시

      - 역방향 그래프 사용하지 않고, DFS 수행

      - SCC의 부모 노드를 찾을 때까지 DFS 및 stack에 저장, 부모 노드를 찾으면 그 때까지 pop하고 SCC로 저장

      - 시간 복잡도 O(V+E)