[알고리즘] 위상정렬(Topological Sort) 알아보기 : 자바(Java)

방향을 거스르지 않으면서 순서대로 방문하는 것을 위상정렬이라고 한다.

유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것!

순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘이다.

유향 그래프의 구조에 따라 여러개의 종류가 나올 수 있다.

 

사이클이 존재하면 안된다

=> 위상 정렬이 불가능하다? 사이클이 존재한다

 

BFS 사용하기

1. 진입 차수가 0인 노드를 모두 큐에 넣는다.

=> 진입 차수가 0 : 해당 정점을 가리키는 정점이 없다. 즉 순서의 시작이 되는 놈이다.

2. 큐에서 진입 차수가 0인 노드를 꺼내 자신과 인접한 노드의 간선을 제거한다.

=> 인접한 노드의 진입 차수를 1씩 감소시킨다.

3. 간선 제거 후 진입 차수가 0이 된 노드가 있다면 큐에 넣는다.

4. 큐가 공백이 될 때 까지 반복한다.

 

차수 : 정점에 연결된 간선 수

진출차수 : 해당 정점에서 타 정점으로 나가는 간선 수

진입차수 : 타 정점에서 해당 정점으로 들어오는 간선 수

 

큐에 들어가는 놈들은 진입 차수가 0인 정점들이다.

:: 나를 바라보는 놈들이 더이상 없다면 큐에 들어간다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 위상정렬_큐 {
	
	static int N, M;
	static class Node{
		int vertex;
		Node link;
		// Node 안에 Node를 파라미터로 갖는다
		public Node(int vertex, Node link) {
			super();
			this.vertex = vertex;
			this.link = link;
		}
	}
	static Node[] adjlist; // 인접리스트
	static int[] inDegree; // 진입차수
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 인접리스트를 노트 클래스로 구현해보자
		adjlist = new Node[N + 1];
		inDegree = new int[N + 1];
		int from, to;
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			// 이와 같은 방식으로 from이 to와 연결되게 한다.
			adjlist[from] = new Node(to, adjlist[from]);
			// 진입차수 증가시키기
			inDegree[to]++;
		}
		ArrayList<Integer> list = topologySort();
		if(list.size() == N) {
			for(Integer vertex : list) {
				System.out.print(vertex + " ");
			}
			System.out.println();
		} else {
			System.out.println("cycle");
		}
	}
	
	static ArrayList<Integer> topologySort(){
		// 반환할 어레이리스트
		// 만일 사이클이 형성되지 않는 간선들이라면 큐를 다 뽑았을 때 N개라는 보장을 할 수 없다.
		// 그러니 N크기의 배열이 아닌 어레이리스트를 사용하자.
		ArrayList<Integer> orderList = new ArrayList<>();
		// 진입차수가 0이 된 노드들을 집어넣어줄 큐
		Queue<Integer> queue = new ArrayDeque<Integer>();
		for(int i = 1; i <= N; i++) {
			// 진입차수가 0인 애들 일단 큐에 넣기
			if(inDegree[i] == 0) queue.offer(i);
		}
		// 큐가 텅텅 빌 때 까지 반복하자
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			// 일단 뽑았다면 뽑은거니 반환할 어레이리스트에 집어넣고
			orderList.add(cur);
			
			// 현재 뽑힌 정점의 간선을 탐색하자
			// Node라는게 어쩄든 int랑 Node를 파라미터로 갖는 애니까 
			// tmp.link 하면 Node가 나오는거고
			for(Node tmp = adjlist[cur]; tmp != null; tmp = tmp.link) {
				if(--inDegree[tmp.vertex]==0) {
					queue.offer(tmp.vertex);
				}
			}
		}
		return orderList;
	}
}