컴퓨터/파이썬 공부정리
[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)