본문 바로가기

컴퓨터/파이썬 공부정리

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

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)
    

'컴퓨터 > 파이썬 공부정리' 카테고리의 다른 글

[Python] Prim 알고리즘 구현  (0) 2021.05.31
[Python] Kruskcal 알고리즘 구현  (0) 2021.05.31
[Python] avl 트리 구현  (0) 2021.05.12
[Python] 이진 트리 map 구현  (0) 2021.05.12
[Python] 이진 트리 구현  (0) 2021.05.12