JAVA 위상 정렬(Topoligical Sort) 알고리즘

위상 정렬 (Topoligical Sort)

DAG에 속해 있는 알고리즘 

- 어떤 일을 하는 순서를 찾는 알고리즘 이다.
- 1-> 2 이런 식의 그래프가 있다고 하면,
- 2를 하기 전에 1을 먼저 해야 하는 알고리즘이다.
- BFS와 비슷한 알고리즘

위의 그림을 예로 들겠다.

A에서 D로 가고 싶다. 하지만 D를 가르키는 간선이 두개가 있다.(정점 A와 C에서 나온 간선) 위상 정렬은 이 두개의 간선을 먼저 탐색을 해야지 D를 검색 할 수 있는 것이다.


어디에 쓰일 수 있을까?

기본적으로 선행과목을 예시로 들 수 있다. 가령 과목 D를 듣고 싶다. 과목 D를 듣기 위해선 우선 적으로 A와 B 그리고 C과목 까지 들어야 D과목을 들을 수 있다.


위상정렬 기본적인 자바 코드

Queue<Integer> q = new LinkedList<Integer>();
  for (int i = 1; i &lt;= n; i++) {
   if (inDegree[i] == 0) {
    q.add(i);
   }
  }
  for (int k = 0; k &lt; n; k++) {
   int x = q.remove();
   System.out.print(x + " ");
   for (int y : a[x]) {
    inDegree[y] -= 1;
    if (inDegree[y] == 0) {
     q.add(y);
    }
   }
  }