[16, 17일차] 08 그래프 : 08-3 위상 정렬, 08-4 다익스트라

함께 푼 문제

[백준 / 그래프] 1766 : 문제집 (python)

 

[백준 / 그래프] 1446 : 지름길 (python)

 

위상 정렬

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

• 시간복잡도 O(V + E)
• 항상 유일한 값으로 정렬되지 않음
• 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없음

위상 정렬 알고리즘

위상 정렬을 하기 위해 우선 진입차수 값을 계산하는 리스트 D를 만들어준다.

진입차수는 외부에서 들어오는 간선의 수 즉, 자신을 가리키는 에지의 수를 의미한다.

 

진입 차수 리스트 D에서 진입 차수가 0인 노드를 선택하고, 선택된 노드를 정렬 리스트에 저장한다. 그리고 인접 리스트 A에서 선택된 노드와 연결된 노드들의 진입 차수를 1씩 뺀다.

위 그림에서는 1번 노드를 선택하여 정렬 리스트에 저장하고, 연결된 2, 3번 노드의 진입 차수를 1씩 뺀다.

D[2] --, D[3] --   ->   D[2] = 0, D[3] = 0

위상 정렬 리스트 저장 과정

이를 반복하여 위상 정렬 리스트에 저장한다.

항상 유일한 값으로 정렬되지 않는 이유는 D[2] = 0, D[3] = 0 인 상황에서 2번 노드를 먼저 선택해도 되고, 3번 노드를 먼저 선택해도 되기 때문이다.

 

위 그래프에서 위상 정렬 리스트의 결과는 [1, 2, 3, 4, 5]가 된다.

 

다익스트라

그래프에서 최단 거리를 구하는 알고리즘

• 출발 노드와 모든 노드 간의 최단 거리를 탐색
• 에지는 모두 양수
• 시간 복잡도 O(ElogV)
• 다익스트라 알고리즘을 통해 완성된 최단 거리 리스트 D는 모든 노드 간의 최단 거리를 표현 (출발 노드에만 국한되지 않음)

다익스트라 알고리즘 단계

1. 인접 리스트로 그래프 구현하기

인접 리스트 A

2. 최단 거리 리스트 초기화하기

최단 거리 리스트 D

 출발점을 기준으로 최단 거리 리스트 D를 초기화한다. 자기 자신은 0으로 초기화하고 나머지는 거리를 모르기 때문에 가장 큰 값(보통 sys.maxsize)으로 초기화한다.

 

3. 값이 가장 작은 노드 고르기

 최단 거리 리스트 D에서 현재 값이 가장 작은 노드를 고른다. 처음에는 출발점(1)을 고른다.

 

4. 최단 거리 리스트 업데이트하기

 Min(선택 노드의 최단 거리 리스트의 값 + 에지 가중치, 연결 노드의 최단 거리 리스트의 값) 으로 업데이트 한다.

 위 그래프에서 1번 노드를 선택했을 때 연결된 노드는 2, 3이다.

 선택 노드(1)의 최단 거리 리스트 D 값은 0이고, 에지 가중치는 8이고, 연결 노드(2)의 최단 거리 리스트 D의 값은 무한대이다. (연결 노드가 3인 경우도 마찬가지) 따라서 Min(0+8, 무한대)와 Min(0+3, 무한대) 를 하면 각각 8, 3이 되므로 최단 거리 리스트 D는 업데이트 된다.

 

5. 과정 3~4를 반복해 최단 거리 리스트 완성하기

 과정 4에서 선택 노드가 될 때마다 다시 선택되지 않도록 방문 리스트를 만들어 처리하고, 모든 노드가 선택될 때까지 반복하면 최단 거리 리스트 D가 완성된다.