사용자 도구

사이트 도구


ps:위상_정렬

위상 정렬 (Topological Sorting)

  • 위상정렬 결과를 구하는 알고리즘은 Kahn's algorithm과 DFS를 이용하는 방법이 있다. 인접리스트로 그래프가 주어질때, 수행시간은 둘 다 O(|V|+|E|)이다.
    • 종만북에서는 Kahn's algorithm은 가볍게 언급만 하고 DFS 방법만 설명한다. 바킹독의 실전 알고리즘 강좌에서는 Kahn's algorithm을 설명한다
    • 여러 가지의 가능한 정렬 결과들 중, 특정한 순서를 만족하는 결과를 얻으려면 Kahn's algorithm 을 써야 한다.
    • 결과를 generator 형태로 얻으려면 Kahn's algorithm 을 써야 한다.
      • DFS에서는 위상정렬의 결과를 역순으로 구한 뒤에 reverse를 해서 최종 결과를 얻는 방식이라서 불가능하다.
    • DFS를 이용하는 방법을 구현할 때, 재귀 버전의 DFS을 사용한다면 간단하게 구현할수 있지만, 비재귀 버전의 DFS라면 좀 더 테크닉이 필요하다. 아래에 언급하는 python graphlib의 _find_cycle() 함수 구현을 참고하자.
  • 방향그래프에서 사이클을 찾는 문제도 위상 정렬 알고리즘에 기반하여 해결할 수 있다.
    • Kahn's algorithm을 돌리다가, 모든 노드를 포함하는 위상정렬 결과가 만들어지기 전에 indegree가 0인 노드가 남아있지 않게 되면, 사이클이 있는 것이다
    • DFS에서는 탐색중인 노드들과, 탐색이 완료된 노드들을 따로 저장하면서 탐색하는 방식으로, 사이클이 발견되면 바로 찾을 수 있다.
    • 사이클의 존재 여부뿐 아니라, 그 사이클에 어떤 노드가 포함되었는지 정보까지 알기 위해서는 DFS 방식을 써야 한다
  • Python 3.9에서는 TopologicalSorter 클래스를 포함하는 graphlib 모듈이 추가되었다.
    • 위상정렬 결과를 리턴해주고, 사이클이 있는 경우에는 그 사이클의 정보를 포함하는 예외를 발생시킨다.
    • 그러나, 아직 대부분의 PS사이트에서는 python 3.8을 사용하고 있기 때문에 사용이 가능해지려면 좀 기다려야 할 듯..
    • PS 사이트에서 못 쓰더라도, 소스코드가 순수 파이썬으로 작성되어 있어서 참고할만 하다. 위상정렬 코드는 패러럴 컴퓨팅까지 고려해서 좀 복잡하게 구현되어있으나, 비재귀 DFS에 기반한 사이클 디텍션은 따로 함수로 빠져있고, 구현도 심플해서 그대로 조금 변형해서 갖다 쓰는것도 가능할 듯.

코드

from typing import AbstractSet, List, Sequence


def topological_sort(graph: Sequence[AbstractSet[int]]) -> List[int]:
    """Returns a list of nodes in topologically sorted order."""
    indegrees = [0] * len(graph)
    for successors in graph:
        for v in successors:
            indegrees[v] += 1

    stack = [u for u, indegree in enumerate(indegrees) if indegree == 0]
    result = []
    while stack:
        u = stack.pop()
        result.append(u)
        for v in graph[u]:
            indegrees[v] -= 1
            if indegrees[v] == 0:
                stack.append(v)

    if len(result) != len(graph):
        raise ValueError('found a cycle')
    return result

관련 문제

토론

댓글을 입력하세요:
P I N R Q
 
ps/위상_정렬.txt · 마지막으로 수정됨: 2020/11/25 17:04 저자 teferi