[10분 테코톡] 💞 소롱의 최단 경로 & 최소 신장 트리

1. 그래프

정의

정점(vertex)와 간선(edge)으로 이루어진 자료구조

종류

a. 무방향 그래프

• 두 정점을 연결하는 간선에 방향이 없는 그래프

b. 방향 그래프

• 두 정점을 연결하는 간선에 방향이 존재하는 그래프. 간선의 방향으로만 이동 가능

c. 가중치 그래프

• 두 점을 이동할 때 비용이 드는 그래프

d. 사이클이 없는 방향 그래프

• 방향 그래프에서 사이클이 없는 그래프

e. 트리 (사이클이 없는 무향 그래프)

---

2. 최단 경로

경로란?

간선들을 순서대로 나열한 것

최단 경로란?

시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로

최단 경로 종류

a. 단일 출발 최단 경로

단일 노드 v에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 최단 경로

b. 단일 도착 최단 경로

모든 노드들로부터 출발하여 그래프 내의 한 단일 노드 v로 도착하는 최단 경로

c. 단일 쌍 최단 경로

주어진 꼭지점 u와 v에 대해 u에서 v까지의 최단 경로

d. 전체 쌍 최단 경로

그래프 내 모든 노드 쌍들 사이의 최단 경로

다익스트라 알고리즘

양의 가중치를 가진 최단 경로 탐색에 사용되는 알고리즘

아이디어

최단 경로의 부분 경로는 최단 경로이다 -> DP 알고리즘을 사용한다고 할 수 있음
그때그때 최소 가중치를 찾아야 된다는 점에서 그리디 알고리즘이라고 볼 수 있음

설명

거리

정점	가중치
0	0
1	5
2	7
3	3
4	-

거리

정점	가중치
0	0
1	5
2	5
3	3
4	-

거리

정점	가중치
0	0
1	5
2	5
3	3
4	9

거리

정점	가중치
0	0
1	5
2	5
3	3
4	8

3. 최소 신장 트리

무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

신장 트리란?

n개의 정점을 포함하는 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리

크루스칼 알고리즘

가중치가 적은 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘

• 희소 그래프일 때 더 효율적

크루스칼 알고리즘 동작 과정

1. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)로 정렬을 수행
2. 정렬된 간선 정보를 하나씩 확인하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인
3. 만약 사이클이 발생하지 않으면 최소 신장 트리에 포함시키고 사이클이 발생하면 최소 신장 트리에 포함시키지 않음
4. 1번 ~ 3번의 과정을 모든 간선에 대해 반복 수행

노드들 간의 사이클이 발생하는지의 여부는 노드들의 부모노드가 같은지 아닌지로 판단할 수 있다. 만약 노드들의 부모 노드가 같다면 사이클이 발생하고, 같지 않다면 사이클이 발생하지 않음을 의미한다.