위상정렬 알고리즘

위상정렬

• 위상정렬은 순서가 중요한 작업이 있을때 그 순서를 결정하는 알고리즘이다.
• 가장 대표적인 예시는 선후수 과목 체제이다.
• 예를들어 고급프로그래밍을 수강하려면 반드시 기초 프로그래밍을 배워야 수강해야 한다는 학칙이 있을때 이런 시스템을 선후수 과목 체제라고 한다.
• 대마법사가 되기위해선 먼저 마법사로 전직해야 자격이 주어진다라고 이해하면 된다.

위상정렬의 특징

• 위상정렬은 사이클이 존재하지 않는 방향 그래프에서만 사용이 가능하다
• 사이클이 발생하면 순서적인 의미가 없어지기 때문이기도 하고 시작점 부터 선정을 할수가 없어지기 때문이다.
• 위상정렬은 사용하는 자료구조, 접근방법에 따라 답이 여러개일수 있다.
• 위상정렬알고리즘을 통해 구할 수 있는 답은 2가지이다.
• 위상정렬이 가능한지 여부 (사이클이 발생하는지 여부), 가능하다면 위상정렬의 결과이다.

위상정렬 알고리즘

• 위상정렬을 구현할 수 있는 방법은 크게 스택을 이용하는 방법, 큐를 이용하는 방법이 있다.
• 대부분은 큐를 이용하여 구현을 많이하는 편인데 직관적이기도 하고 구현이 편하기 때문이다.
• 위상정렬 알고리즘은 다음과 같은 전략에 의해 구현된다

1. 진입차수(해당 노드에 연결된 간선 수)가 0인 노드를 큐에 모두 집어넣는다
2. 큐에 있는 노드들을 하나씩 꺼내어 이 노드와 연결된 간선(진출차수)들을 제거한다
3. 위 과정에서 큐에서 꺼낸 노드와 연결된 다른 노드들의 진입차수를 감소시켜준다 이때 해당 노드들의 진입차수가 0이된다면 해당 노드들도 큐에 집어넣는다
4. 큐가 빌때까지 위 과정을 반복한다, 큐가 비었을때 만약 모든 노드들이 방문처리가 됐다면 위상정렬이 완성된것, 만약 큐에 들어가지 않은 노드(방문되지 않은 노드)가 있다면 사이클이 발생한 것이다.

실제 데이터를 가정하고 예시를 들어보자

C->A
A<- B
A-> D 라면

각 노드별 진입차수는 다음과 같다
A B C D
2 0 0 1

진입차수가 0인 B,C를 큐에 집어넣는다.
B를 큐에서 빼면서 B와 연결된 정점 A의 차수를 빼준다.
1 0 0 1

C를 큐에서 빼면서 C와 연결된 A의 차수를 빼준다
0 0 0 1

진입차수가 0이된 A를 큐에 넣는다

A를 빼면서 A가바라보는 선행정점인 D의 차수를 빼준다
0 0 0 0

D를 큐에 집어넣어 준다
D를 큐에서 뺀다
D에서 나가는 간선이 없다
탐색이 끝남.

모든 노드가 방문처리 되었음으로 이 리스트는 사이클이 발생하지 않았음으로
위상정렬이 완료되었다.

위상정렬 코드 By Queue(BFS) and JAVA

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

public class Main {
    static int N,M;
    static ArrayList<Integer>[] list;
    static int[] inDegree; // 진입차수 배열  
    static ArrayList<Integer> answer = new ArrayList<>(); 
    
    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());
      list = new ArrayList[N];
      inDegree = new int[N];

      for(int i=0; i<N; i++)
      {
        list[i] = new ArrayList<Integer>();
      }
      
      for(int i =0; i<M; i++)
      {
        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken())-1;
        int to = Integer.parseInt(st.nextToken())-1;
        list[from].add(to);
        ++inDegree[to];
      }
      
      
      ArrayList<Integer> orderList = topologySort();
      
      
//      System.out.println(Arrays.toString(inDegree));
      for(int i=0; i<orderList.size(); i++)
      {
        System.out.print(orderList.get(i)+" ");
      }
      
     
    }
    private static ArrayList<Integer> topologySort()
    {
      ArrayList<Integer> orderList = new ArrayList<>();
      Queue<Integer> queue = new ArrayDeque<>();
      
      for(int i=0; i<N; i++)
      {
        if(inDegree[i] ==0) queue.offer(i); // 차수가 0인 애들을 큐에 집어넣는다 
      }
      
      while(!queue.isEmpty()) // 만약 큐가 비어있지 않다면 
      {
        int current = queue.poll(); // 입차수가 0인 노드를 하나 꺼내옴 
        orderList.add(current+1); // 정답에 포함시킨다               

        //뽑은 노드와 연결된 리스트의 진입차수를 하나 빼준다 
        
       
       for(Object obj : list[current])
       {
         Integer next = (Integer) obj;
         inDegree[next] -=1;
         if(inDegree[next] == 0)
           queue.offer(next);
       }
      }
      return orderList;
    }
    

}