Strongly Connected Component(강연결요소)

그래프

SCC(강연결요소)

• Strongly Connected Component
• A에서 B로 갈 수 있다면, B에서 A로도 갈 수 있는 성질
• 방향성이 존재하는 유향 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우

  증명 방법

  1. 그래프 G에서 한 정점 V를 선택
  2. V에서 DFS를 통해 모든 정점으로 갈 수 있는지 확인
  3. 그래프 G의 간선 방향을 거꾸로 돌려 그래프 G’ 생성
  4. 그래프 G’에서 한 정점 V’를 선택
  5. V’에서 DFS를 통해 모든 정점으로 갈 수 있는지 확인
• 시간 복잡도: O(V+E)

  강연결 성분

• 강연결성을 가지고 있는 서브 그래프들 (맥시멈 집합)

  코사라주 알고리즘

• 방향그래프, 역방향그래프, 스택 준비
  1. 방향그래프의 임의의 정점에서 DFS 수행
  2. DFS가 끝나는 순서대로 스택에 삽입 (return 하면서 삽입)
     • DFS 수행 후 방문하지 않은 정점이 있으면 해당 정점부터 다시 수행
  3. 스택의 top에서부터 pop하여 순서대로 역방향 그래프에서부터 DFS 수행
     • 이때 탐색되는 모든 정점을 SCC로 묶는다.
     • 스택이 비어있을 때까지 진행한다.
     • 스택의 top 정점이 이미 방문한 정점이면 pop만 한다.

코사라주 알고리즘

타잔 알고리즘

• 코드와 함께 보기
  1. 방문할 때마다 스택에 방문 정점을 저장 (코사라주는 끝나면서 저장하지만 타잔은 DFS 과정에서 저장)
  • DFS 수행 순서, 즉 아직 방문하지 않은 정점에 대하여 방문하는 순서에 따라 각 정점에 고유한 id값 부여
    1. 자신과 연결된 정점 중, 이미 방문하였으나 SCC로 묶여있지 않은 정점(부모 정점)으로 갈 수 있다면 자신의 ret 값을 부모 정점의 id 값으로 변경(작은 id값으로 변경)
    2. ret 값이 자신의 고유 id값이라면 스택에서 자신이 나올 때까지 pop
  • pop하는 과정에서의 모든 정점들은 자신과 SCC를 이룸 (SCC 배열에 같은 그룹으로 저장)

타잔 알고리즘

Transitive Closure

• A에서 B로 direct 하지 않지만 indirect 하게 갈 수 있는 경로를 찾는 알고리즘
• A -> C, C -> B 이면 A -> B
• 간접적으로 연결되어 있는 간선을 직접 갈 수 있는 간선으로 추가한 그래프

증명 방법

1. DFS를 모든 정점에 대하여 수행
   • 시간 복잡도: O(V(V+E))
   • E는 V의 제곱보다 작거나 같다. (그래프 정의)
   • 최악의 경우 V의 세제곱
2. Floyd-Warshall Algorithm
   • 동적 계획법: O(V(V(V)))
   • (i,j)에 길이 있거나 (i,k),(k,j) 길이 있으면 (i,j)는 연결되어 있음.
   • 수도코드

     for k from 1 to |V|
      for i from 1 to |V|
     for j from 1 to |V|
     D[i][j] := D[i][j] | (D[i][k] & D[k][j])
     

     결론

   • DFS와 Floyd-Warshall은 경우에 따라 속도가 다르므로 누가 더 빠르다고 말할 수 없다.
   • 주어진 간선이 많은 경우에는 Floyd-Warshall이 더 빠르다.