알고리즘
위상정렬(topological sort)
윤듀2
2023. 10. 11. 18:46
위상 정렬
사이클이 없는 방향그래프에서 선후관계가 위배되지 않도록 나열하는 정렬이다.
위상 정렬를 잘 설명해 줄 수 있는 예로는 '선수과목 구조'가 있다.
자료구조은 알고리즘1 과 알고리즘2의 선수 과목이고, 알고리즘 1을 먼저 들어야 알고리즘 2를 들을 수 있다고 했을 때
자료구조 -> 알고리즘 1 -> 알고리즘2 순으로 들어야한다.
알고리즘2를 먼저 듣고 알고리즘 1을 듣는 것은 불가능하다.
이렇게 선후관계가 정해진 그래프 구조에서 선후관계에 따라 정렬하기 위해서 위상 정렬를 이용할 수 있다.
위상 정렬 알고리즘 수행 과정
indegree : 자신에게 들어오는 간선 수
1. 각 정점의 indegree를 저장한다.
2. indegree가 0인 정점을 큐에 저장
3. 큐에서 정점을 꺼내 꺼낸 정점에서 출발하는 정점들의 indegree 값 1씩 감소시킴
4. 감소시켜 정점의 indegree가 0이 되었으면 2로 돌아가고 큐가 빌때 까지 2,3을 반복한다.
java로 구현된 위상정렬 코드
public class Main {
static int v; // 정점 갯수
static int e; // 간선 갯수
static List<List<Integer>> graph = new ArrayList<>(); // graph
private static void topological_sort(List<List<Integer>> graph,int [] indegree){
Queue<Integer> q = new LinkedList<>(); // 간선이 0인 정점을 넣을 큐
Queue<Integer> result = new LinkedList<>(); // 위상 정렬 결과
for(int i =1; i<=v; i++){
if(indegree[i] == 0){
q.offer(i);
}
}
while(!q.isEmpty()){
int cur = q.poll();
result.offer(cur);
List<Integer> list = graph.get(cur); // cur정점에서 가리키는 정점들
for(int i = 0; i<list.size(); i++){
int index = list.get(i);
indegree[index]--;
if(indegree[index] == 0){ //새롭게 들어오는 간선이 없는 정점들 큐에 넣기
q.offer(index);
}
}
}
System.out.println(result);
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
v = sc.nextInt();
e = sc.nextInt();
int [] indegree = new int[v+1]; //각 정점에서 들어오는 간선의 수를 저장하는 간선 테이블
// graph 초기화
for(int i = 0; i<=v; i++){
graph.add(new ArrayList<Integer>());
}
// 간선 입력 받으면서 indegree 테이블 채우기
for(int i =0 ; i < e; i++){
// a -> b
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b);
indegree[b] +=1;
}
topological_sort(graph,indegree);
}
}
시간복잡도
O(v + e) 선형 시간에 실행됨