[Python] 위상 정렬

Algorithm

유향 그래프의 정점을 정렬

정점을 오른쪽 방향으로 쭉 나열했을 때, 오른쪽에 있는 정점에서 왼쪽의 정점으로 이동하는 간선은 하나도 없도록 만듦

위상정렬 전

위상정렬 후

위상정렬 조건: 그래프가 DAG(Directed Acyclic Graph)의 형태를 띄어야함. -> 방향이 있고 싸이클이 없는 그래프

 

적용

그래프에서 반드시 자신보다 선행되어야 할 일을 다 끝내야만 작업에 들어갈 수 있는 조건이 주어지는 경우

Ex) 줄 세우기를 하는데, 키가 작은 사람은 키가 큰 사람보다 무조건 앞에 서야함

 

Queue로 구현하기

1. 들어오는 간선이 없는 (indegree가 0인) 정점을 모두 큐에 넣는다.

2. 정점의 개수만큼 이를 반복한다.

   2-1. 큐의 front를 pop해서 그 정점에서 나가는 간선을 모두 삭제한다.

   2-2. 삭제하면서 indegree가 0이 되면 이 정점들도 큐에 넣는다.

3. 큐에서 빼는 정점 순서가 위상정렬의 결과이다.

   고려해야하는 부분

   반복문을 V번 돌기 전에 큐가 빈다는 의미는 위상정렬이 불가능하다는 것이다. -> 싸이클이 존재한다는 것

   싸이클에 속하는 정점은 indegree가 0일 수가 없음

Code

def TopologicalSort():
    queue = deque()
    # 초기작업: 들어오는 간선이 없는 정점을 queue에 넣기
    for i in range(N):
        if indegree[i] == 0:
            queue.append(i)

    # 위상정렬
    for i in range(N):
        # 도중에 queue가 비면 위상정렬 불가능
        if not queue:
            return False

        curr = queue.popleft()
        # 위상정렬 결과 리스트에 append
        result.append(curr)
        # 인접한 정점을 순회하면서 indegree를 1씩 감소시킴. 0이되면 큐에 넣음
        for Next in adj[curr]:
       	    indegree[Next] -= 1
            if(indegree[Next] == 0):
                queue.append(Next)

    return True