위상정렬 알고리즘

위상 정렬(Topological Sort)이란

어떤 일을 하는 순서를 찾는 알고리즘이다.

즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것

위상 정렬(Topological Sort)의 특징

하나의 방향 그래프에는 여러 위상 정렬이 가능하다.

위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다.

위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이

러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.

간선 (i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 한다.

위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법

 

진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택

진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다.

초기에 간선의 수가 0인 모든 정점을 큐에 삽입

선택된 정점과 여기에 부속된 모든 간선을 삭제

선택된 정점을 큐에서 삭제

선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소

위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료

 

위상 정렬 알고리즘 수행 시간

 

for루프 는 매번 n번 반복된다. 매 반복 때마다 1개의 정점이 선택되고 해당 정점에 연결된 진출 간선이 모두 제거된다.

각 간선은 단 한 번씩만 취급된다. 그러므로 총 수행 시간은 Θ(V+E) 이다.

 

<TopologicalSorting>

import java.util.ArrayList;
import java.util.Arrays;

public class TopologicalSorting {
    private String[] vertices = new String[]{"냄비에 물붓기", "점화", "라면봉지 뜯기", "라면 넣기", "수프 넣기", "계란 풀어넣기"};;
    private int[][] adjMatrix = new int[][]{
            {0, 1, 0, 0, 0, 0}, // 냄비 물붓기의 진출 간선
            {0, 0, 0, 1, 1, 1}, // 점화의 진출 간선
            {0, 0, 0, 1, 1, 0},
            {0, 0, 0, 0, 0, 1},
            {0, 0, 0, 0, 0, 1},
            {0, 0, 0, 0, 0, 0},
    };

    void sort1() {
        System.out.println("---- 위상정렬 알고리즘 1 결과 ----");
        ArrayList<String> A = new ArrayList<>();
        int[][] b = adjMatrix.clone();
        boolean[] isVisited = new boolean[vertices.length];
        Arrays.fill(isVisited, false);

        for(int k=0; k<6; k++) {
            // 진입 간선이 없는 정점 u를 선택
            String u = null;
            int[] edge = null;
            for (int i = 0; i < vertices.length; i++) {
                if (isVisited[i]) continue;  // 방문한 정점은 패스
                String x = vertices[i];     // 정점 x
                boolean existIncomingEdge = false;   // 진입 간선의 존재 여부
                for (int j = 0; j < vertices.length; j++) {
                    if (b[j][i] != 0) {
                        existIncomingEdge = true;
                        break;
                    }
                }

                // 진입 간선이 없으면 u에 x를 대입하고 반복문 나오기
                if (!existIncomingEdge) {
                    u = x;
                    edge = adjMatrix[i];
                    isVisited[i] = true;
                    break;
                }
            }

            // 진입 간선이 없는 정점 u를 A에 삽입
            A.add(u);
            // 정점 u의 진출 간선을 모두 제거
            Arrays.fill(edge, 0);
            System.out.println(u);
        }
        System.out.println();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("---- 위상정렬 알고리즘 1 그래프 ----\n");
        for (int i = 0; i < vertices.length; i++) {
            int[] edge = adjMatrix[i];
            builder.append(String.format("%s -> ", vertices[i]));
            for (int j = 0; j < edge.length-1; j++) {
                if (edge[j] != 0) builder.append(String.format("%s -> ", vertices[j]));
            }
            if (edge[edge.length-1] != 0) builder.append(String.format("%s ", vertices[edge.length-1]));
            builder.append("\n");
        }
        return builder.toString();
    }
}

<main>

package 그래프;

public class main {

	public static void main(String[] args) {

        TopologicalSorting ts = new TopologicalSorting();
        System.out.println(ts);
        ts.sort1();	
	}
}

 

결과