가중치 그래프 알고리즘

MST | 최소 비용 신장 트리 알고리즘

모든 노드를 탐색하는데 필요한 최소 가중치 값을 구하는 알고리즘

철수는 이번 여행에서 계획한 관강지를 꼭 모두 갈 예정이다 하지만 돈이 많이없어서 오래 여행지에서 머물 여유가 없다 가장 최단 시간으로 관장지를 모두 둘러보는 방법을 구해라

※ 최대 숙소 + 관광지수 -1 만큼의 관광을 할 수 있다.

숙소 = 관광 시작노드, 관광지 = 나머지 노드

※ 여행지 정보에 따른 가장 짧은 관광 계획이어야 한다.

가중치 최소합을 리턴

※ 맘에드는 관광지가 있을 수 있지만 어쩔 수 업는 상황이 아니면 한번 관광한 관광지를 반복해서 관광하는 루트는 짜면 안된다.

사이클 포함 X

1. 간선의 가중치의 합이 최소여야 한다.
2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
3. 사이클이 포함되어서는 안된다.

위의 세가지 조건을 만족하면서 모든 노드를 탐색하는 알고리즘이다.

Kruskal 알고리즘 (DP)

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.
2. 가장 낮은 가중치의 간선 부터 정렬된 순서대로 탐색한다.
3. 간선을 탐색했을때 해당 간선을 포함하는 노드들의 집합이 정답 집합과 서로 겹치는지 확인한다. (사이클이 형성 되는지 확인)
4. 3번 조건까지 통과 했으면 해당 간선을 정답 집합에 추가한다.
5. 전부 탐색을 마쳤다면 정답 조합을 리턴한다.

Prim 알고리즘 (dfs)

1. 임의의 노드를 하나 선택한다.
2. 가중치가 가장 낮은 간선을 통해 다음 노드로 향한다.
3. 2번을 계속 반복 하면서 사이클이 생기는 경우엔 다시 원래 노드로 돌아와 사이클이 생기는 간선을 제외하고 다른 가중치가 가장 낮은 간선을 탐색한다.
4. 2, 3번을 반복하다가 해당 노드에서 다른 노드로 가는 모든 간선이 사이클을 일으킨다면 이전에 탐색했던 간선을 다시 이전 노드로 돌아와 사이클이 일으키는 노드로 향하는 간선을 제외하고 다른 가중치가 가장 낮은 간선을 탐색한다.
5. 전부 탐색을 마쳤다면 간선 조합을 리턴한다.

다익스트라 (bfs + priorityQueue)

1. 그래프의 간선 정보를 기반으로 현재 노드에서 뻗어나갈 수 있는 간선들의 가중치 정보를 최소 가중치 경로를 저장할 배열(이하 경로 배열)에 저장한다.

2. 경로 배열에 저장된 가중치 중 가장 적은 가중치를 가진 간선을 선택해서 이어진 노드로 이동한다.

3. 해당 노드에서 다시 각 노드로 가는 가중치와 시작 노드에서 현재 노드까지 오는데 합산된 가중치를 더해서 현재 경로 배열에 저장된 값과 비교한다.

4. 3번 설명에 대한 예시

   간선과 가중치 정보가 A- > C, (5) A → B, (3) B → C (1)과 같은 상황이라고 가정했을 때 현재 상황이 A노드로 시작해 B노드에 와 있는 상황이라고 해보자,

   이 때 경로 배열에 저장된 값은 A = 0, B = 3, C = 5 일 것 이다. 여기서 B 노드가 C 노드를 바라봤다.

   B → C (1) B에서 C로 갈때 필요한 가중치 1과 A에서 B로 올 때 쌓인 가중치 3을 더했을 때 총 4가 나온다 A에서 C로 바로가는 가중치 5보다 효율적이다. 이 때 경로 배열의 값 5를 4로 갱신한다.

   더 많은 노드를 거치더라도 더 적은 가중치를 가지는 경로로 갱신한다는 의미이다.

5. 위의 2~3번을 반복한다.