[그래프 위상정렬] Topological Sort : Java

 

 

그래프 위상정렬: Topological Sort

 

 

 

BFS&DFS를 계속 공부하다가 위상정렬도 요즘 핫(?)하다길래 따로 공부하는 중이다.

위상정렬은 그래프 정렬의 일종인데 이것이 가능하기 위해선 순환성을 가져서는 안된다. 즉 순환없는 방향성을 가진 계층적 정렬이 가능해야 위상정렬이 가능하다. 조건식으로 나타내면 다음과 같다.

 

1. 1 -> 2 -> 3 -> 4 와 같은 관계가 성립되어야 한다.
2. A -> B | B <- A 와  같은 사이클이 존재하면 성립하지 않는다.

 

 

Dag(Directed Acyclic Graph), i.e. there is no cycle existed in the graph

 

 

보통 위상정렬은 inDegree Integer 1차원 배열과 Queue를 이용해 구현할 수 있다.

위상정렬의 대표적인 문제인 CoureseSchedule 문제를 풀어보면 

 

 

 

문제

 

 

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return 
any of them. If it is impossible to finish all courses, return an empty array.

코스 0을 수강하기 위해 일부 코스에는 전제 조건이 있을 수 있다. 먼저 코스 1을 수강해야하며, [0,1] 총 과정 수와 전제 조건 쌍이 주어지면 모든 과정을 마칠 수 있는가(순서를 구하는 문제인데 일단 불린 값으로 여부를 판단해 보았다.)

Input

 

int course = 4;
int [][] nums ={{1,0}{2,1}{3,2}};

 

Output

 

True

 

---

 

 

풀이

 

 

DFS를 이용한 방법과 inDegree를 이용한 방법이 있는데 inDegree 방식으로 풀어보았다. inDegree Integer 배열을 통해서 각 노드별 진입차수를 inDegree 배열로 기록해주고 진입차수가 0인 노드를 큐에 저장한다. 큐에서 노드를 하나씩 poll하면서 연결된 노드들의 진입차수를 -1로 수정해준다. 진입차수가 0이 된 노드는 다시 큐에 offer 해주며 반복한다. 이러한 과정을 반복했을 때 inDegree 배열의 모든 진입차수가 0이된다면 True, 남아있다면 False가 반환되게 된다.

 

시간복잡도: O(V+E) = 정점의 갯수+ 간선의 갯수

 

package com.company;
import java.util.*;
import java.io.*;

public class Solution {
    // 위상정렬(Topological Sort)
    public static void main(String[] args) {
        int course = 4;
        int [][] nums ={
                {1,0},
                {2,1},
                {3,2}
        };
        int [][] nums2={
                {1,0},
                {0,1}
        };
        System.out.println(solve(course,nums)+"\n"+solve(course,nums2));
    }
    private static boolean solve(int courseNumber, int[][] nums)
    {
        //error check
        if(courseNumber <=0)return false;

        //ds : inDegree 배열
        Queue<Integer> queue = new LinkedList<>();
        int [] inDegree = new int[courseNumber];

        //1-1 inDegree 완성
        int numsLength = nums.length;
        for(int i=0;i<numsLength;i++)
        {
            inDegree[nums[i][1]]++;
        }

        // 바깥에서 하는게 메모리적으로 빠르다
        int inDegreeLength = inDegree.length;
        //1-2 inDegree에서 0인값을 큐에 push  == > 3
        for(int i=0;i<inDegreeLength;i++)
        {
            if(inDegree[i]==0)
            {
                queue.offer(i);
            }
        }
        //
        while(!queue.isEmpty())
        {
            int firstZeroVal = queue.poll(); //3

            for(int i=0;i<numsLength;i++)
            {
                if(firstZeroVal == nums[i][0]) //2,0
                {
                    inDegree[nums[i][1]]--;
                    if(inDegree[nums[i][1]]==0)
                    {
                        queue.offer(nums[i][1]); //2
                    }
                }
            }
        }
        //4
        for(int i=0;i<inDegreeLength;i++)
        {
            if(inDegree[i]!=0)
            {
                return false;
            }
        }
        return true;
    }

}