Topological Sort

위상정렬

위상정렬이란?

• 비순환 방향 그래프 ( Directed Acyclic Graph ) 에서, 정점들을 선형으로 정렬하는 방법
  • 정렬 방법 : 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서대로 정렬
• 같은 비순환 방향 그래프에서도 여러 개의 위상 순서가 나타날 수 있음

구현 방법

• BFS ( Breath First Search )

  • 알고리즘 순서

    • 모든 정점에 대해 in_degree 배열을 설정 ( 이 정점으로 향하는 간선의 개수 )
    • in_degree가 0인 정점들을 queue에 추가 ( 순서의 시작점이 될 것 )
    • queue가 비게 될 때까지 반복
      • 가장 앞의 원소 a를 꺼내 순서 배열에 기록
      • a에서 갈 수 있는 간선을 통해서 도달할 수 있는 정점들 중 visit되지 않은 정점들의 in_degree를 1 낮춤
        • in_degree가 0이 되는 정점이 있다면 그 정점을 queue에 추가

  • 소스코드

    void topologicalSort() {
        for (int i = 1; i <= n; ++i) {
                
            // 시작지점 찾기
            if (deg[i] == 0) {
                queue[rear++] = i;
                visit[i] = true;
                order[len++] = i;
            }
        }
        
        // 추가진행 탐색
        while (front < rear) {
            int a = queue[front++]; // 현재 정점
                
            // 추가 진행 여부 탐색
            for (int i = 1; i <= n; ++i) {
                if (!visit[i] && matrix[a][i]) {
                    if (--deg[i] == 0) {
                        queue[rear++] = i;
                        visit[i] = true;
                        order[len++] = i;
                    }
                }
            }
        }
        return;
    }
    

• DFS ( Depth First Search )

  • 알고리즘 순서

    • 방문하지 않은 모든 정점에 대해 DFS 수행
      • 하나의 정점에서 시작하며, visit 표시를 하면서 간선을 따라 다음 정점을 따라감
      • 더 이상 진행할 수 있는 간선이 없다면 list에 그 정점을 추가 ( 가장 마지막 순서가 될 것 )
      • 역추적을 통해 이전 정점들을 방문하며, 방문하지 않은 간선이 더 있는지 파악
        • 방문 가능한 간선이 있다면 추가진행
        • 방문 가능한 간선이 없다면 현재 정점도 list에 기록
    • 모든 정점을 방문할 때까지 반복

  • 소스코드

    void topologicalSort() {
        for (int i = 1; i <= n; ++i) {
            if (!visit[i]) { // 추가탐색 진행
                DFS(i);
            }
        }
        return;
    }
        
    void DFS(int x) {
        visit[x] = true;
        for (int i = 1; i <= n; ++i) { // 추가탐색 진행
            if (matrix[x][i] && !visit[i]) {
                DFS(i);
            }
        }
            
        order_stack[top++] = x; // 최종 정점 입력
        return;
    }
    

시간 복잡도

• 그래프를 만드는 방법이 2가지 존재
  • 인접 리스트를 사용하는 경우 $O(V+E)$
  • 인접 행렬을 사용하는 경우 $O(V^2)$