[알고리즘] 위상 정렬 ( Topological Sort )

 

◇  설명

   □  정의

      사이클이 없는 유향 그래프( DAG : Directed Acyclic Graph ) G = (V, E) 에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 함
     ( 간선 (i, j)가 존재한다면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 함 )

   □  특징

      -  일반적으로 답이 유일하지는 않다

   □  과정

      1.  인접 리스트를 이용하여 한 정점에 대해 진출 간선( outgoing edge )으로 인접한 정점의 번호를 저장

      #1  각 정점의 진입 차수( in-degree = 간선의 개수 )를 저장한 배열을 이용하는 방법 ( + 진입 차수가 0인 정점들을 담은 자료구조 )

           2.  배열 생성 후 각 정점의 번호를 인덱스로 하여 진입 차수 카운트
           3.  우선순위 큐 생성 후 진입 차수가 0인 정점 번호를 넣음
              ( 당장 제거 가능한 정점이 여러 개일 경우 정점 번호가 더 작은 것을 먼저 제거하기 위해 사용함. 
                TreeSet도 가능. 하지만 아무거나 먼저 제거해도 상관 없다면 리스트를 사용해도 됨 )
           4.  우선순위 큐에서 차례로 정점을 제거하면서 그 정점의 진출 간선으로 이어진 정점들의 진입 차수를
               하나씩 지움 ( 이 때 0이 되면 우선순위 큐에 넣음 )
             ( 원래 알고리즘은 정점 선택 후 그 정점과 진출 간선들을 제거하는 것이지만,
               인접 리스트에서 정점 번호를 인덱스로 했을 경우 제거하면 혼란이 생기므로 제거하지 않음.
               단 인접 리스트를 List<List<Integer>> 가 아닌  Map<Integer, List<Integer>> 로 생성했을 경우 제거 가능 )
             ( 이 과정 반복 )

      #2  DFS를 이용하는 방법 ( + 정점 방문 체크 배열, 선택된 정점들의 연결 리스트 )

           2.  정점 방문 여부 값을 담을 배열 생성 후, 방문하지 않은 정점에 대해 DFS 수행
              ( 당장 제거 가능한 정점이 여러 개일 경우 정점 번호가 더 작은 것을 먼저 제거하기 위해서는
                정점 번호가 큰 순서대로 DFS 수행 )
           3.  가장 깊은 곳까지 탐색 후 정점 선택 ( 이때 선택된 정점들을 연결 리스트의 앞부분에 삽입 )
           4.  백트래킹하며 정점 선택
           5. ( 2 ~ 4 반복 )

 

◇  코드 

( 입력받는 부분은 백준온라인저지 사이트의 2252번 줄 세우기 문제 ( https://www.acmicpc.net/problem/2252 ) )

  #1 

    *  List<List<Integer>>

import java.io.*;
import java.util.*;

public class TopologicalSort_list_arr { // 정점 번호는 [0, n)
	
	static List<List<Integer>> edge_out;
	static int[] degree_in, answer;

	static void topologicalSort(int n) {
		answer = new int[n];
		PriorityQueue<Integer> top = new PriorityQueue<>(); // TreeSet<Integer> top
		for (int i = 0; i < n; ++i)
			if (degree_in[i] == 0)
				top.add(i);
		int idx = 0, u;
		while (idx < n) {
			u = top.remove(); // u = top.pollFirst();
			answer[idx++] = u + 1;
			for (int v : edge_out.get(u)) {
				degree_in[v]--;
				if (degree_in[v] == 0)
					top.add(v);
				// edge_out.set(u, null);
			}
		}
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i, u, v;
		edge_out = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge_out.add(new ArrayList<>());
		degree_in = new int[n];
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			edge_out.get(u).add(v);
			degree_in[v]++;
		}
		br.close();

		topologicalSort(n);
		
		System.out.print( Arrays.toString(answer) );
	}

}

    *  Map<Integer, List<Integer>>

import java.io.*;
import java.util.*;

public class TopologicalSort_map_arr { // 정점 번호는 [0, n]

	static Map<Integer, List<Integer>> edge_out;
	static int[] degree_in, answer;

	static void topologicalSort(int n) {
		answer = new int[n];
		PriorityQueue<Integer> top = new PriorityQueue<>(); // TreeSet<Integer> top
		for (int i = 1; i <= n; ++i)
			if (degree_in[i] == 0)
				top.add(i);
		int idx = 0, u;
		while (idx < n) {
			u = top.remove(); // u = top.pollFirst();
			answer[idx++] = u;
			for (int v : edge_out.remove(u)) {
				degree_in[v]--;
				if (degree_in[v] == 0)
					top.add(v);
			}
		}
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i, u, v;
		edge_out = new HashMap<>();
		for (i = 1; i <= n; ++i)
			edge_out.put(i, new ArrayList<>());
		degree_in = new int[n + 1];
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			edge_out.get(u).add(v);
			degree_in[v]++;
		}
		br.close();

		topologicalSort(n);
		
		System.out.print( Arrays.toString(answer) );
	}

}

  #2 

    *  List<List<Integer>>

import java.io.*;
import java.util.*;

public class TopologicalSort_list_dfs { // 정점 번호는 [0, n)
	
	static List<List<Integer>> edge_out;
	static boolean visited[];
	static LinkedList<Integer> answer;
	
	static void dfs(int u) {
		visited[u] = true;
		for (int v : edge_out.get(u))
			if (!visited[v])
				dfs(v);
		// edge_out.set(u, null);
		answer.addFirst(u + 1);
	}
	
	static void topologicalSort(int n) {
		answer = new LinkedList<>();
		visited = new boolean[n + 1];
		for (int u = n - 1; u >= 0; --u)
			if (!visited[u])
				dfs(u);
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i;
		edge_out = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge_out.add(new ArrayList<>());
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			edge_out.get(Integer.parseInt(st.nextToken()) - 1).add(Integer.parseInt(st.nextToken()) - 1);
		}
		br.close();

		topologicalSort(n);
		
		System.out.print( answer );
	}

}

    *  Map<Integer, List<Integer>>

import java.io.*;
import java.util.*;

public class TopologicalSort_map_dfs { // 정점 번호는 [0, n]
	
	static TreeMap<Integer, TreeSet<Integer>> edge_out;
	static boolean visited[];
	static LinkedList<Integer> answer;
	
	static void dfs(int u) {
		visited[u] = true;
		for (int v : edge_out.remove(u))
			if (!visited[v])
				dfs(v);
		answer.addFirst(u);
	}
	
	static void topologicalSort(int n) {
		answer = new LinkedList<>();
		visited = new boolean[n + 1];
		for (int u = n; u > 0; --u)
			if (!visited[u])
				dfs(u);
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i;
		edge_out = new TreeMap<>();
		for (i = 1; i <= n; ++i)
			edge_out.put(i, new TreeSet<>());
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			edge_out.get(Integer.parseInt(st.nextToken())).add(Integer.parseInt(st.nextToken()));
		}
		br.close();
		
		topologicalSort(n);
		
		System.out.print( answer );
	}

}