위상정렬

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 같이 보기

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

4 참고 자료

• https://en.wikipedia.org/wiki/Topological_sorting