👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 개념

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다.

위상정렬에서는 항상 유일한 값으로 정렬되지 않습니다. 즉 정렬되는 정답이 하나가 아닙니다.
또한, 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상정렬을 적용할 수 없습니다.

2. 원리 이해하기

2-1. 진입 차수 배열 초기화(업데이트)

진입 차수란, 자기 자신을 가리키는 에지의 개수입니다.
가장 먼저 그래프 데이터가 주어지면, 인접 리스트형태로 구현 후, 진입 차수 배열을 초기화해줍니다.

아래 그림을 보면, ArrayList로 그래프를 표현했습니다. 그래프에는 사이클이 없는 상태입니다.

진입 차수 배열 D를 다음과 같이 없데이트 합니다.

2-2. 정렬하기

진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장합니다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺍니다.

위 그림을 예로 들어 설명하면,
진입 차수가 0인 노드 1을 선택하여 2,3의 진입차수를 1씩 빼 D[2], D[3]을 0으로 만듭니다.
이렇게 정렬이 될 때까지 진입차수가 0인 노드를 선택 후, 각 노드가 가리키는 노드의 진입 차수를 1씩 빼기를 반복합니다.

중간에 진입차수가 0이 되는 노드가 여러개가 생기는 상황이 발생하기도 합니다.

이때는 어떤 노드를 먼저 선택하느냐에 따라 정렬 결과가 달라집니다.

맨 처음에 이야기한 정답이 하나가 아니라는 의미가 이것 때문입니다.

위상 배열 결과는 다음과 같습니다.