알고리즘 - 위상정렬

위상정렬

---

Topological Sorting

• 싸이클이 없는 유향 그래프의 순서를 위배하지 않도록 나열한 것이다.

• 모든 정점을 일렬로 나열하되 정점x 에서 정점y 로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다.

• 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다. 

 

 

위상정렬 알고리즘

• 진입 간선이 없는 정점을 하나 선택한다.
• 해당 정점의 진출간선과 해당 정점을 모두 제거한다.
• 구현 with JAVA

public String topologicalSort(ArrayList<Integer>[] list, int[] indegree) {
    Queue<Integer> q = new LinkedList<>();
    for(int i = 0; i < indegree.length; i++) {
        if(indegree[i] == 0) q.add(i); //진입 간선의 수가 0인 노드를 큐에 넣어준다.
    }
    
    String str = ""; //위상 정렬 순서를 담을 문자열
    while(!q.isEmpty()) {
        int node = q.poll();
        str += node;
 
        for(int i = 0; i < list[node].size(); i++) {
            int linkedNode = list[node].get(i); //현재 노드와 연결된 노드 정보를 삭제해 줄 것이다.
            indegree[linkedNode]--; //진입 차수 감소
            if(indegree[linkedNode] == 0) q.add(linkedNode); //진입 간선의 수가 0이되면 q에 넣어준다.
        }
    }
    return str;
}

 

관련문제

www.acmicpc.net/problem/2252

2252번: 줄 세우기

www.acmicpc.net/problem/3665

3665번: 최종 순위

reference