위상정렬

1 개요

topological sorting, topological sort, toposort, topological ordering

위상 정렬

• 여러 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것
• 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것
• 다양한 규칙을 적용할 수 있음

2 예시

 

규칙	결과
왼쪽→오른쪽 정렬	7, 5, 3, 11, 8, 2, 9, 10
작은 숫자부터 정렬	3, 5, 7, 8, 11, 2, 9, 10
링크가 적은 것부터 정렬	5, 7, 3, 8, 11, 10, 9, 2
가장 큰 숫자로 연결된 것부터 정렬	7, 5, 11, 3, 10, 8, 9, 2
위→아래, 왼쪽→오른쪽 정렬	7, 5, 11, 2, 3, 8, 9, 10
임의로 정렬	3, 7, 8, 5, 11, 10, 2, 9

3 같이 보기

• 유향 그래프
• 위상 topology
• 정렬

4 참고

• 위키백과 "위상정렬"
• 영어 위키백과 "Topological_sorting"
• http://navercast.naver.com/contents.nhn?rid=2871&contents_id=91824