위상정렬

태그: graph, sort, topological_sorting
상태: In progress
최종 편집 일시: 2023년 4월 20일 오후 6:56

구현법 1. 재귀와 스택

내가 1005 ACM Craft문제를 풀었을 때 구현한 방식이 이 방법이다. DFS와 상당히 흡사한 방식의 코드라서 마음에 들었다. 차이점이라면, 스택을 사용한다는 것과, push의 타이밍이 DFS와는 다르게 최후에 이루어진다는 점이다. DAG(Directed Acyclic Graph) 연결리스트를 이미 구현해 놓았다고 가정한 상태에서 설명 시작한다.

1. 임의의 모든 버텍스에 대하여 위상정렬을 수행한다.

   for i in vertices {
       if (!visited[i]) {
           topological_sort(i);
       }
   }
   

2. 버텍스로부터 나가는 다른 노드들을 한 번씩 순회하면서 방문하지 않은 노드들에 대하여만 재귀호출을 수행한다.

   for node in nodes {
       if (!visited[node]) {
           visited[node] = true;
           topological_sort(node);
       }
   }
   

3. 스택에 본인을 push하고 함수를 빠져나간다.

   visited[i] = true;
   stack.push(i);
   

구현법 2. 큐와 in-degree

• input variables
  • edges: 간선의 정보를 담고 있는 배열, 예를 들어 A→B라면 (A, B) 이런 식으로 담겨있다.
• inner variables
  • queue: 내부적으로 사용하는 큐, in-degree가 0인 놈들만 집어넣는다.
  • list: 버텍스들에 대한 정보를 담고있다. 인접리스트로 방향성을 갖고 있다는거 유의. A→B라면 ls[A] 의 원소 중에 B가 있다.
• out variables
  • result_queue: 위상정렬 결과를 저장할 자료구조, 그냥 queue와 헷갈리지 않도록 주의

말로 쓰는 수도코드

1. edges로부터 list를 생성한다.
2. list의 모든 버텍스 간의 in-degree(들어오는 연결의 수)를 계산한다.
3. in-degree가 0인 버텍스들을 queue에 넣는다.
4. queue가 빌 때까지 다음을 반복한다.
   1. queue에서 원소를 하나 뺀다 ⇒ node
   2. node가 향하는 다른 정점들의 in-degree를 1씩 뺀다
   3. 만약 해당 정점의 in-degree가 0이라면 queue에 넣는다.
   4. result_queue에 node를 삽입한다.
5. cycle 테스트를 수행한다. 만약 in-degree가 0이 아닌 원소가 있다면 이 저시기는 cycle이 있는 것이다.
6. result_queue 를 리턴한다.

관련 문제

2637 장난감 조립 {boj}
1948 임계경로 {boj} {위상정렬}