위상정렬

순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘

사이클이 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것

 

진입 차수 : 특정 노드로 들어오는 간선의 개수

진출 차수 : 특정 노드에서 나가는 간선의 개수

진입 차수가 있다는 것은 선행 조건이 있다는 뜻이므로 진입 차수가 더 중요!

 

위상 정렬 방법(Queue 사용)

1. 진입 차수가 0인 모든 노드들 Queue에 삽입
2. Queue가 공백상태가 될 때까지 반복 수행
   1. Queue에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
      (연결된 노드의 진입 차수를 감소시킨다.)
   2. 새롭게 진입 차수가 0이 된 노드를 Queue에 삽입한다.

Queue에서 꺼내지는 순서(Queue 들어온 순서)가 위상 정렬을 수행한 결과이다.

package 알고리즘;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class 위상정렬4 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		for (int Tc = 1; Tc <=10; Tc++) {
			int V=sc.nextInt();
			int E=sc.nextInt();
			
			List<Integer>[] list=new ArrayList[V+1];
			//V+1로 하는 이유 : 숫자가 1부터 그 숫자까지이기 때문에 그 수에 맞게 입력해주기 위해

			//인접 리스트로 받기 위해 선언
			for (int i = 0; i < V+1; i++) {
				list[i]=new ArrayList<>();
			}
			
			//받는 정점의 수를 저장해줄 배열 선언
			int[] arr=new int[V+1];
			
			//큐에서 poll한 값들을 다 저장해줄 정답 리스트 선언
			List<Integer> ans=new ArrayList<>();
			
			//인접 리스트로 입력 받은 값들의 그래프 만들어줌.
			//arr[ed]++를 하면서 받는 정점들의 수를 하나씩 더해줌
			for (int i = 0; i < E; i++) {
				int st=sc.nextInt();
				int ed=sc.nextInt();
				list[st].add(ed);
				arr[ed]++;
			}
			
			//큐 선언
			//큐 용도 : arr값이 0이 되면 큐에 add를 해주고 바로 poll하면서 그거에 연결되어 있는 값들을 찾아줄 것이다.
			Queue<Integer> q=new LinkedList<>();
			
			//arr 배열에 1부터 V까지 돌면서 0인 값들을 먼저 큐에 더해준다.
			for (int i = 1; i < V+1; i++) {
				if (arr[i]==0) {
					q.add(i);
				}
			}
			
			//큐가 비어있을 때까지 반복문을 돌려준다.	
			//일단 위에서 큐에 더해준 값들을 하나씩 빼면서 그 빼진 값과 연결된 값을 찾는다.
			//연결된 값들을 arr에서 하나씩 빼주고 뺐을 때 그 값이 0이 되면 큐에 바로 넣어준다.
			//그리고 큐에 넣어진 값들을 다시 하나 빼고 정답 리스트에 넣고 위에 과정을 반복
			while (!q.isEmpty()) {
				//바로 큐에서 값을 빼고 현재 값에 넣어주고				
				int curr=q.poll();
				//바로 정답 리스트에 넣어준다.
				ans.add(curr);
				
				//그 현재값에 연결되어 있는 수만큼 반복을해준다.
				for (int i = 0; i < list[curr].size(); i++) {
					//임시 값에 첫번째 현재값과 연결되어 있는 값을 저장
					int temp=list[curr].get(i);
					//끝 값들이 얼마나 있는지 저장되어 있는 배열에 방금 저장한 임시값을 빼준다.
					arr[temp]--;
					//아직 그 값이 0이 아니라면 반복문 계속 수행
					//그 값이 0이 되면 큐에 그 임시값을 바로 더해준다.
					if (arr[temp]==0) {
						q.add(temp);
					}
				}
			}
			
			//출력
			System.out.print("#"+Tc+" ");
			for (int i = 0; i <ans.size(); i++) {
				if (ans.get(i)!=0) {
					System.out.print(ans.get(i)+" ");
				}
			}
			System.out.println();
		}//테케 10번 반복
	}
}

위상 정렬 방법(Stack 사용)

1. 진입 차수가 0인 모든 노드에서 DFS 탐색 수행
2. DFS 수행
   1. 해당 노드를 방문 표시
   2. 인접하면서 방문하지 않은 노드가 있다면 DFS 재귀 호출
   3. 함수 리턴하기 전 Stack에 현재 노드 저장
3. Stack이 공백 상태가 될 때까지 pop

Stack에서 꺼내지는 순서를 뒤집으면 위상 정렬을 수행한 결과이다.

위상 정렬 특징

• 모든 정점을 방문하기 전에 Queue가 공백 상태가 되면 사이클이 존재하는 것이다.
  (사이클이 존재하면 진입 차수가ㅏ 0이 될 수 없음)
• 그래프의 유형은 DAG
• 여러 해답이 존재할 수 있다.
  (진입 차수가 0인 값이 동시에 생성이 된다면 작성한 코드 방법에 따라 답이 달라진다.)
• 시간 복잡도 O(V+E)