[알고리즘] 위상정렬

Hyo Kyun Lee·2022년 1월 14일
0

알고리즘

목록 보기
18/45

18. 위상정렬

순서가 정해져있는 작업을 차례로 수행해야 할 때, 그 순서를 정렬하는 알고리즘을 일컫는다.

18-1. 위상정렬의 조건

위상정렬의 핵심은 조건(진입차수 및 간선배치)과 노드들의 선형정렬이다.

이 선형정렬을 구성하기 위한 필요한 조건은 두가지이다.

  • graph가 있을때 조건에 따른 한가지 경로를 도출할 수 있다.
  • 경로에 따라 여러가지 경로를 도출할 수 있다.

특히 첫번째 조건인 한가지 경로 도출에 대한 부분은 DAG, Directly Acycle Graph 즉 사이클이 존재하지 않는 graph인 점이다.
또한 기본적으로 명확한 시작점(진입차수가 0인 노드)이 존재해야 한다.

18-2. 위상정렬 구현 과정

위상정렬은 Queue 자료구조를 활용하며, 결과적으로 graph가 위상정렬이 가능한지에 대한 여부와 정렬결과를 모두 알 수 있다.

  • 진입차수가 0인 정점(출발점)을 Queue에 1차적으로 넣는다.
  • Queue에서 해당 노드(출발노드 혹은 인접노드)를 꺼내고, 방문노드에 대한 간선을 모두 제거하며 이로 인해 진입차수가 0이 된 노드를 Queue에 넣는다.
  • 위 과정을 반복하고, Queue에 넣어지는 노드가 없어질 때까지 반복한다.
  • 최종적으로 Queue에서 빼낸 노드들의 정렬이 위상정렬의 결과이다.

18-3. 알고리즘 구성

알고리즘에서 진입차수정보를 기재하는 배열(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())

18-4. 참조자료

위상정렬 관련자료
https://freedeveloper.tistory.com/390

0개의 댓글