[Python] 위상정렬

위상 정렬은 기본적으로 N번 만큼만 수행한다. N개의 원소의 순서를 알아내는 것이기 때문이다.

이를 이용해 알아낼 수 있는 정보들이 있다.

첫번째: 사이클 발생

첫번째로 N번 만큼 수행할 동안 큐안에 0개의 원소가 들어있다면 사이클이 발생했다는 것이다. 그 이유는 위상 정렬을 할 때 indegree를 감소시키는데 이 값이 0일때만 큐 안에 들어간다. 하지만 사이클이 있어 한번 더 진입을 하게되면 큐 안에 값이 들어갈 수 없기 때문이다.

두번째: 순서 불분명

두번째로 큐 안에 2개 이상의 원소가 들어가있다면 순서가 확실하지 않아 여러 순서가 발생할 수 있는 것이다. indegree 값이 0인 값이 여러개가 존재하게 되면 큐 안에 2개 이상의 원소가 들어가게 되는데 이는 동시에 들어간 노드의 순서가 불분명하다는 말이 된다.

q = deque()
for i in range(1,N+1):
    if degree[i] == 0:
        q.append(i)
    
for i in range(N): 
    if len(q) == 0: # 사이클 존재
        print("사이클 존재")
        break
    if len(q) >= 2: # 순서 불분명
        print('순서 불분명')
        break
    now = q.popleft()
    for j in range(1,N+1):
        if graph[now][j]:
            degree[j] -= 1
            if degree[j] == 0:
                q.append(j)