순서가 정해져있는 작업을 차례로 수행해야 할 때, 그 순서를 정렬하는 알고리즘을 일컫는다.
위상정렬의 핵심은 조건(진입차수 및 간선배치)과 노드들의 선형정렬이다.
이 선형정렬을 구성하기 위한 필요한 조건은 두가지이다.
특히 첫번째 조건인 한가지 경로 도출에 대한 부분은 DAG, Directly Acycle Graph 즉 사이클이 존재하지 않는 graph인 점이다.
또한 기본적으로 명확한 시작점(진입차수가 0인 노드)이 존재해야 한다.
위상정렬은 Queue 자료구조를 활용하며, 결과적으로 graph가 위상정렬이 가능한지에 대한 여부와 정렬결과를 모두 알 수 있다.
알고리즘에서 진입차수정보를 기재하는 배열(inDegree), graph(인접노드들에 대한 정보)를 구성해준다.
node = 7
#진입차수정보
inDegree = [0, 1, 1, 1, 1, 2, 1]
graph = [
[2,5],
[3],
[4],
[6],
[6],
[7],
[0]
]
def topologySort():
result = []
queue = []
#진입차수가 0인 노드를 큐에 삽입
for i in range(0, len(inDegree)):
if inDegree[i] == 0:
queue.append(i)
#위상정렬의 완전한 수행을 위해 모든 node를 방문
for i in range(len(inDegree)):
#n개 방문 이전에 cycle이 Queue가 빈다면 사이클이 발생한 경우
if len(queue) == 0:
print("위상정렬이 불가능한 graph입니다.")
return
else:
nextNode = queue.pop(0)
result.append(nextNode+1)
if graph[nextNode] == 0:
result.append(nextNode + 1)
else:
for j in graph[nextNode]:
inDegree[j-1] = inDegree[j-1] - 1
if inDegree[j-1] == 0:
queue.append(j-1)
return result
print(topologySort())
위상정렬 관련자료
https://freedeveloper.tistory.com/390