[ 알고리즘 ] 최소 신장 트리, 최단 거리 알고리즘

최소 신장 트리

신장 트리 : 그래프의 모든 정점을 포함하는 트리

최소 신장 트리 : 가중치가 있는 그래프에서 간선의 가중치 총합이 가장 작은 신장 트리

 

 

프림 알고리즘(Prim algorithm) - 정점 기준

그리디 알고리즘으로, 임의의 정점을 시작점으로 트리를 확장하면서 최소 신장 트리를 생성하는 방식이다.

 

💡 프림 알고리즘 과정

1. 시작점부터 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.
2. 시작점과 연결한 노드에서 뻗어 나가는 간선 중 가장 작은 가중치를 가진 노드로 연결한다.
3. 반복한다.

 

 

크루스칼 알고리즘(Kruskal algorithm) - 간선 기준

그리디 알고리즘으로, 간선을 오름차순으로 정렬한 뒤 가중치가 낮은 간선을 선택하면서 최소 신장 트리를 생성한다.

 

💡 크루스칼 알고리즘 과정

1. 간선의 가중치를 오름차순으로 정렬한다.(시작노드, 끝노드, 가중치)
2. 사이클이 생성되지 않는 선에서 작은 값부터 연결한다.
3. 사이클 생성유무나 노드 연결은 유니온-파인드 알고리즘을 사용한다.

 

 

유니온 파인드 알고리즘(union-find algorithm)

2개의 원소가 같은 집합에 속하는지 판단하는 알고리즘

 

💡 유니온 파인드 알고리즘 과정

1. 각 데이터의 대표 노드를 설정한다.(초기에는 자기 자신의 값)
2. 유니온 : 두 노드를 하나의 그래프로 합침
3. 파인드 : 특정 노드가 속한 그래프의 대표 노드를 찾음
4. 크루스칼에서는 두 정점이 다른 그래프에 속한다고 판별되면 두 정점을 연결하고, 같은 그래프면 연결하지않는다.

 

 

 

 

최단 거리 알고리즘

정점 간 최단 거리를 구하기 위한 알고리즘

 

 

다익스트라 알고리즘(Dijkstra algorithm)

간선의 가중치가 음수가 아닌 경우 특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘

 

💡 다익스트라 알고리즘 작동 방식

1. 각 정점에 대한 비용을 시작 : 0, 나머지 : INF인 배열을 생성한다.
   
   
2. 시작 정점에서 방문 가능한 정점에 대한 비용을 갱신한다.
   
   
3. 반복하는데 만약,
   A노드에서 B노드로 가는 비용이 5,
   시작에서 A까지 가는 비용이 3,
   시작에서 B까지 가는 비용이 10 -> B의 비용이 10으로 설정되어있음
   이럴 경우, Math.min((S->A) + (A->B), 비용배열[B])를 계산해서 값을 갱신한다.
   
   
4. 이런식으로 모든 정점을 방문했다면 알고리즘 수행을 종료한다.

 

 

벨만-포드 알고리즘(Bellman-Ford algorithm) - 간선 기준

특정 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘으로, 가중치가 음수인 경우에도 적용가능하다.

하지만 음의 사이클이 있다면 최소 비용이 무한하게 줄어들어 알고리즘 사용이 불가하다.

• 전체 간선을 n-1번 순회하며 최단 거리를 갱신한다.(특정 노드에서 다른 노드를 잇는 간선은 최대 n-1)
• 만약 n번 순회했는데 갱신되는 값이 있다면 음의 사이클이 존재함을 의미한다.

 

💡 벨만-포드 알고리즘 과정

1. 다익스트라와 같이 각 정점에 대한 비용을 시작 : 0, 나머지 : INF인 배열을 생성한다.
2. S를 시작으로 간선 <S, A>, <S, B>, <A, E>, <E, C>, <C, A>, <B, D>를 탐색하면서 정점 ABCDE에 대해 최단 거리를 갱신한다.
3. 만약 정점이 N개일 경우 N-1번 반복하고, 그 값이 각 정점에 대한 최단거리이다.
4. 만약 N번째 반복에서 갱신되는 값이 있을 경우 해당 그래프는 음의 사이클이 존재한다.

 

 

알고리즘 요약

---

📖 정렬 알고리즘

종류	특징	평균 시간 복잡도
버블 정렬	· 인접한 두 수를 비교해 정렬	O(n2)
선택 정렬	· 정렬되지 않은 배열에서 최솟값을 선택해 정렬
삽입 정렬	· 정렬된 배열에 탐색 중인 요소 삽입
합병 정렬	· 분할 정복 기반 알고리즘 · 배열을 1 이하 크기로 분할한 후 합병 과정에서 정렬	O(n log n)
퀵 정렬	· 분할 정복 기반 알고리즘 · 피봇을 선택해 피봇보다 작은 수, 큰 수의 배열로 분할하며 정렬 · 피봇에 따라 시간 복잡도가 달라짐
힙 정렬	· 힙 기반 정렬 알고리즘 · 최대 힙 : 오름차순 정렬, 최소 힙 : 내림차순 정렬
기수 정렬	· 비교 기반이 아닌 정렬 알고리즘 · 낮은 자리수부터 높은 자릿수까지 정렬 · 0-9까지 큐를 생성 -> 메모리 소비 · 시간 복잡도 효율적임	O(dn) * d: 최댓값의 자릿수
계수 정렬	· 비교 기반이 아닌 정렬 알고리즘 · 데이터 범위를 인덱스로 갖는 배열을 생성해 각 인덱스에 해당하는 데이터의 개수를 세서 정렬 수행	O(n+k) * k: 데이터 범위

 

 

 

📖 최소 신장 트리 (MST)

간선의 가중치 총합이 가장 작은 신장 트리

종류	특징
프림 알고리즘	· 시작 정점을 정한 후 트리를 확장해 최소 신장 트리를 생성 · 방문 가능한 정점 중 비용이 적게 드는 정점을 선택해 트리 확장
크루스칼 알고리즘	· 여러 트리를 합쳐 하나의 최소 신장 트리를 생성 · 간선을 가중치에 따라 오름차순 정렬한 뒤 낮은 가중치부터 선택해서 연결 · 사이클 방지를 위해 유니온 파인드를 사용하여 같은 그래프인지 판별
* 유니온 파인드	· 두 개의 원소가 같은 집합에 속하는지 판별하는 알고리즘 · 유니온 : 두 노드를 연결 · 파인드 : 해당 노드가 속한 집합의 대표 노드를 찾음

 

 

 

📖 최단 거리 알고리즘

그래프의 특정 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘

종류	특징
다익스트라 알고리즘	· 간선의 가중치가 음수가 아닌 경우 최단 거리를 구하는 알고리즘 · 방문 가능한 정점 중 비용이 가장 적은 정점을 방문 · 방문한 정점과 연결된 다른 정점의 비용 갱신이 가능한 경우 갱신 수행
크루스칼 알고리즘	· 간선의 가중치가 음수인 경우까지 최단 거리를 구하는 알고리즘 · 음의 사이클이 있으면 알고리즘 적용못함 * 음의 사이클 -> N번째 순회에서 갱신되는 값이 있다면 음의 사이클이 존재한다는 의미