컴퓨터/파이썬 공부정리

[Python] 위상 정렬(topological sort) 구현

스커 2021. 5. 31. 20:40
def topological_sort_AM(vertex, graph):
    n = len(graph)
    inDeg = [0] * n         # 정점의 진입차수 저장

    for i in range(n):
        for j in range(n):
            if graph[i][j] > 0:
                inDeg[i] += 1

    vlist = []              # 진입 차수가 0인 정점 리스트틀 만듬
    for i in range(n):
        if inDeg[i] == 0:
            vlist.append(i)

    while len(vlist) > 0:
        v = vlist.pop()
        print(vertex[v], end=' ')

        for u in range(n):
            if v != u and graph[v][u]:
                inDeg[u] -= 1   # 연결된 정점의 진입 차수 감소
                if inDeg[u] == 0:
                    vlist.append(u)