위상정렬 Topological sort

위상정렬 Topological sort

일의 순서가 정해져 있을때 순서대로 정렬하는 것. (예: 수강신청시 선수과목, 스타크래프트 빌드 테크트리)

순서를 정해야하기 때문에 그래프에서 cycle이 존재하면 안된다. 또한 순서가 있기 때문에 방향이 있어야 한다.

DAG(Directed Acyclic Graph) 가 되어야 위상정렬을 할 수 있다.

즉, 방향이 있으며 사이클이 없는 그래프여야 한다.

위상정렬 구현 방법 (BFS 탐색)

1. 이 그래프가 사이클이 있는지 확인한다.

(보통의 경우 문제를 해결하는 경우에는 이 과정이 있다면 위상 정렬 자체를 시도하지 않을 것이지만) 

2. 현재 정점에 들어오는 간선이 없다면 BFS라면 큐에 담아준다.

3. 큐에서 front원소를 빼고 front에 연결되어있는 정점들 간의 간선을 모두 삭제해준다. 

이때 해당하는 다음 정점에 들어오는 간선이 없다면 큐에 담아준다.

이 과정을 정점의 개수만큼 반복한다.

4. 결국 이 과정을 반복하는 동안 큐에서 빠지는 front 순서대로가 위상 정렬의 결과이다.

출처: http://www.crocus.co.kr/716 [Crocus]

- Java 구현 소스 -

import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedList;

import java.util.Queue;

import java.util.StringTokenizer;

public class TopologicalSort {

static int Ts, V, E, edgecount[];

static String answer;

static ArrayList<Integer> graph[];

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

// System.setIn(new FileInputStream("sample_input.txt"));

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(br.readLine());

Ts = Integer.parseInt(st.nextToken());

for(int T=1;T<=Ts;T++){

// init

answer = "";

st = new StringTokenizer(br.readLine());

V = Integer.parseInt(st.nextToken());

E = Integer.parseInt(st.nextToken());

graph = new ArrayList[V+1];

edgecount = new int[V+1];

for(int i=1;i<=V;i++)

graph[i] = new ArrayList<Integer>();

// input

for(int i=1;i<=E;i++){

int s,e;

st = new StringTokenizer(br.readLine());

s = Integer.parseInt(st.nextToken());

e = Integer.parseInt(st.nextToken());

graph[s].add(e);

edgecount[e]++;

}

// Sort 같은레벨일경우 오름차순으로 정렬한다.

for(int i=1;i<=V;i++)

Collections.sort(graph[i]);

// set start point

ArrayList<Integer> root = new ArrayList<Integer>();

for(int i=1;i<=V;i++){

if(edgecount[i]==0)

root.add(i);

}

// call topological sort

ArrayList<Integer> result = topologicalSort(root);

// make output

for(int vertax:result)

answer += vertax+" ";

// print screen

System.out.println("#"+T+" "+answer);

}

}

// 위상정렬

static ArrayList<Integer> topologicalSort(ArrayList<Integer> root){

ArrayList<Integer> result = new ArrayList<Integer>();

Queue<Integer> que = new LinkedList<Integer>();

boolean visited[] = new boolean[V+1];

// set root

for(int vertax:root)

que.add(vertax);

while(!que.isEmpty()){

int vertax = que.poll();

result.add(vertax);

if(!visited[vertax]){

visited[vertax] = true;

for(int next:graph[vertax]){

edgecount[next]--; // 간선 차감

if(edgecount[next]==0) // 간선이 0인것은 다음 root 이므로 queue add

que.add(next);

}

}

}

return result;

}

}

/* input example

1

5 6

2 1

2 3

3 4

3 1

1 4

5 4

*/