크러스컬 : 엣지를 오름차순으로 정렬하고, 비용이 최소인 엣지부터 최종 부모가 같은 노드에 속한지를 검사하며 유효한 노드를 찾아나간다. > 엣지를 이용해서 노드의 최상위 부모를 찾음 > MST 도출
프림 : 임의의 노드를 하나 잡고 그 노드를 중심으로 엣지의 최솟값을 찾는다. > 노드 기준으로 연결된 엣지의 비용과 노드의 방문 여부를 검사 > MST 도출
Kruskal's Algorithm : 2020/09/14 - [개발자/Algorithm] - Kruskal's Algorithm
Prim.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Prim {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static LinkedList<Edge>[] graph; // Kruskal에서는 각 노드를 PriorityQueue<Edge>에 넣었다면, 여기서 graph는 해당 노드가 start인 모든 엣지를 넣는다. 즉, 3번 노드와 연결된 엣지가 5개면 3번 graph[3] start가 3인 엣지를 5개 가지고 있는 배열이 된다.
static boolean[] visit; // 노드의 방문 여부 (Kruskal에서는 int[] arr에 각 노드의 부모가 누구인지를 저장했다.)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
// 각 노드를 graph로 정의한다. 배열을 V+1개로 만들면 인덱스가 0 ~ V까지 배정되고, 0을 버리고 1 ~ V번 인덱스를 사용한다.
graph = new LinkedList[V+1];
// 각 노드의 방문 여부를 boolean 타입의 일차운 단순 배열로 만든다.
visit = new boolean[V+1];
// 1번 노드부터 V번 노드까지 LinkedList<Edge>[] 타입의 graph 변수에 넣는다. (1 ~ 6번 노드가 샘플로 주어진다.)
for (int i = 1; i <= V; i++) {
graph[i]= new LinkedList<>();
}
mst = new ArrayList<>();
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당. 엣지가 총 9개 주어졌으니 9번 돈다.)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 노드1에서 노드2로 가는 방향으로 저장.
graph[v1].add(new Edge(v1,v2,value));
// 노드2에서 노드1로 가는 방향으로 저장.
graph[v2].add(new Edge(v2,v1,value));
// 왜 양방향으로 저장할까?
// 노드를 기준으로 뻗어 나가는 엣지를 정의하고 그 중 비용이 작은 것을 택하는 것이기 때문에 각 노드에서 뻗어나가는 모든 엣지를 합하면 결국 양방향이 되고 전체 엣지의 2배가 된다.
}
// Kruskal에서 while(mst.size() < (V-1)) { }에 해당. 메인 메소드에 다 넣지 않고 빼놓은 것 뿐이다.
makeMst();
System.out.println(mst);
}
static void makeMst() {
// 1. 시작 노드는 아무거나 지정.
// 2. 선택한 노드에 연결된 엣지들을 PrioityQueue에 넣는다. (비용을 기준으로 오름차순 정렬됨.)
// 3. 비용이 최소인 Edge 객체를 poll()한다. 이 객체는 [start, end, value]를 갖고 있고, end를 visit 검사를 통해 방문 여부를 확인한다.
// 4. 2~3 반복. n-1개의 간선이 선택할때까지 or 모든 정점이 연결될때까지
// 노드를 기준으로 연결된 엣지를 담을 PriorityQueue를 하나 인스턴스화 한다. 그러면 해당 노드에 연결된 엣지들을 비용을 기준으로 오름차순 정렬한다.
PriorityQueue<Edge> pq = new PriorityQueue<>();
// nowV에 현재 방문중인 노드를 넣어주고, 더이상 방문중인 노드가 없다면 while문을 돌려주기 위해 temp로 사용할 변수로써 큐를 인스턴스화 한다.
// visit은 각 노드의 방문 여부를 true, false로 저장하는 boolean 타입의 배열로, temp처럼 사용되는게 아닌 전역변수이기 때문에 queue와는 쓰임새가 다르다.
Queue<Integer> queue = new LinkedList<>();
// 1번 노드에서 시작하겠다.
queue.add(1);
while(!queue.isEmpty()) {
// 현재 노드
int nowV = queue.poll();
// 현재 노드는 방문 했으니 true로 바꾼다.
visit[nowV] = true;
// LinkedList<Edge>[] graph에 모든 노드를 담고 시작했다. nowV에 해당하는 노드의 엣지를 하나씩 꺼낸다.
// 즉, 1번 노드에 엣지가 3개면 각 엣지로 for문을 3번 돌거고, 5번 노드에 엣지가 1개면 for문을 1번 돌고 그런 식이다.
// 그리고 이 엣지는 nowV라는 노드가 볼 때, start(자기 자신), end(연결된 노드), value(비용)을 가진 객체다.
// 따라서 이 for문은 주어진 노드에 연결된 엣지를 개수만큼 꺼내 위에서 선언한 pq에 넣어 비용을 기준으로 엣지를 오름차순 정렬시킨다.
// 이때 해당 노드의 모든 엣지를 무조건 가져올 수도 있찌만 이미 방문한 노드는 다시 계산할 필요가 없으니 if(!visit[edge.end]) { } 를 통해 방문된 노드와 연결된 엣지는 무시한다.
for (Edge edge : graph[nowV]) {
// Edge가 start -> end니까. start가 지금 들어온 nowV번 노드고, end가 start에서 뻗어 나간 엣지의 도착 방향의 노드다.
// 이미 방문된 노드의 엣지는 무시하기 위한 로직.
// *** 여기서 중요한 것은 방문한 노드가 end인 엣지를 추가하지 않았지만 그게 더 효율적일 수도 있다. 즉, 눈으로 볼 때는 그게 쉽게 보이지만
// 컴퓨터로 볼 때는 그렇지 않다. 그러면 어떻게 처리를 할까? 방문한 노드 방향의 엣지를 담지 않는 대신 해당 엣지는 이미 이전에 반대편 노드가 start로 들어왔을 때
// pq에 담겨있고, 그 pq를 매번 돌 때마다 초기화 하지 않기 때문에 유지가 된다. 즉,
if(!visit[edge.end]) {
pq.add(edge);
}
}
// nowV 노드의 엣지를 비용으로 정렬시킨 PriorityQueue가 모두 사라질 때까지 반복한다.
while(!pq.isEmpty()) {
// nowV 노드의 엣지중 비용이 작은 것부터 꺼낸다.
Edge edge = pq.poll();
// 해당 엣지의 end(nowV와 연결된 노드)가 방문하지 않았다면 if문으로 들어간다.
if(!visit[edge.end]) {
// 연결된 노드를 방문한 노드를 담는 queue에 담는다.
// 그냥 nowV = edge.end에 바로 넣어도 될 것 같지만, 더이상 추가할 mst가 없다면 큐가 비어있을거고, while(!queue.isEmpty())를 종료하기 위해서 큐를 사용한다.
queue.add(edge.end);
// 그리고 해당 노드는 방문 여부를 true로 바꾼다.
visit[edge.end] = true;
// 그리고 그 엣지를 mst에 넣는다.
mst.add(edge);
// mst를 찾았으면 해당 nowV의 다른 엣지(지금 찾은 엣지보다 비용이 더 큰 엣지)는 반복을 중단한다.
break;
}
}
}
}
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}
// source : https://velog.io/@dudrkdl777/Graph-최소신장트리-MSTPrim알고리즘
/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/
graph는 각 노드마다 연결된 엣지와 비용을 자기 자신을 start로 해서 LinkedList<Edge>에 담는다.
nowV가 2에 있을 때, pq에 edge.end가 방문한 노드인 경우 추가하지 않도록 하는 최적화 알고리즘 때문에 Edge [2, 4, 7]만 추가하게 된다. 사람 눈으로 볼 때는 당연히 3과 4를 잇는게 최선이라는 것을 바로 알 수 있지만 매번 돌 때마다 graph가 담겨있는 pq를 초기화 하면 이것을 계산할 수 없기 때문에 Edge [2, 4, 7]을 mst로 추가하게 된다.
그렇다면 어떻게 Edge [3, 4, 6]을 찾을까? 바로 pq를 초기화 하지 않고 담아두기 때문이다. 이 때 pq = { Edge [1, 2, 5], Edge [3, 4, 6], Edge [3, 5, 11] } 인 상태에서 nowV 2에서 pq에 Edge [2, 4, 7]을 추가하게 되므로,
다시 pq = { Edge [1, 2, 5], Edge [3, 4, 6], Edge [2, 4, 7], Edge [3, 5, 11] } 이 된다. 따라서 Edge [1, 2, 5]는 현재 nowV가 2에 오면서 visit = true로 바꾸었기 때문에 탈락이고, 그 다음 작은 비용인 Edge [3, 4, 6]이 조건을 만족하므로 mst에 추가되게 된다.
Prim2.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class Prim2 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static LinkedList<Edge>[] graph; // Kruskal에서는 각 노드를 PriorityQueue<Edge>에 넣었다면, 여기서 graph는 해당 노드가 start인 모든 엣지를 넣는다. 즉, 3번 노드와 연결된 엣지가 5개면 3번 graph[3] start가 3인 엣지를 5개 가지고 있는 배열이 된다.
static boolean[] visit; // 노드의 방문 여부 (Kruskal에서는 int[] arr에 각 노드의 부모가 누구인지를 저장했다.)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
// 각 노드를 graph로 정의한다. 배열을 V+1개로 만들면 인덱스가 0 ~ V까지 배정되고, 0을 버리고 1 ~ V번 인덱스를 사용한다.
graph = new LinkedList[V+1];
// 각 노드의 방문 여부를 boolean 타입의 일차운 단순 배열로 만든다.
visit = new boolean[V+1];
// 1번 노드부터 V번 노드까지 LinkedList<Edge>[] 타입의 graph 변수에 넣는다. (1 ~ 6번 노드가 샘플로 주어진다.)
for (int i = 1; i <= V; i++) {
graph[i]= new LinkedList<>();
}
mst = new ArrayList<>();
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당. 엣지가 총 9개 주어졌으니 9번 돈다.)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 노드1에서 노드2로 가는 방향으로 저장.
graph[v1].add(new Edge(v1,v2,value));
// 노드2에서 노드1로 가는 방향으로 저장.
graph[v2].add(new Edge(v2,v1,value));
// 왜 양방향으로 저장할까?
// 노드를 기준으로 뻗어 나가는 엣지를 정의하고 그 중 비용이 작은 것을 택하는 것이기 때문에 각 노드에서 뻗어나가는 모든 엣지를 합하면 결국 양방향이 되고 전체 엣지의 2배가 된다.
}
// Kruskal에서 while(mst.size() < (V-1)) { }에 해당. 메인 메소드에 다 넣지 않고 빼놓은 것 뿐이다.
makeMst();
System.out.println(mst);
}
static void makeMst() {
// 1. 시작 노드는 아무거나 지정.
// 2. 선택한 노드에 연결된 엣지들을 PrioityQueue에 넣는다. (비용을 기준으로 오름차순 정렬됨.)
// 3. 비용이 최소인 Edge 객체를 poll()한다. 이 객체는 [start, end, value]를 갖고 있고, end를 visit 검사를 통해 방문 여부를 확인한다.
// 4. 2~3 반복. n-1개의 간선이 선택할때까지 or 모든 정점이 연결될때까지
// 노드를 기준으로 연결된 엣지를 담을 PriorityQueue를 하나 인스턴스화 한다. 그러면 해당 노드에 연결된 엣지들을 비용을 기준으로 오름차순 정렬한다.
PriorityQueue<Edge> pq = new PriorityQueue<>();
// nowV에 현재 방문중인 노드를 넣어주고, 더이상 방문중인 노드가 없다면 while문을 돌려주기 위해 temp로 사용할 변수로써 큐를 인스턴스화 한다.
// visit은 각 노드의 방문 여부를 true, false로 저장하는 boolean 타입의 배열로, temp처럼 사용되는게 아닌 전역변수이기 때문에 queue와는 쓰임새가 다르다.
Queue<Integer> queue = new LinkedList<>();
// 1번 노드에서 시작하겠다.
queue.add(1);
while(!queue.isEmpty()) {
// 현재 노드
int nowV = queue.poll();
// 현재 노드는 방문 했으니 true로 바꾼다.
visit[nowV] = true;
// LinkedList<Edge>[] graph에 모든 노드를 담고 시작했다. nowV에 해당하는 노드의 엣지를 하나씩 꺼낸다.
// 즉, 1번 노드에 엣지가 3개면 각 엣지로 for문을 3번 돌거고, 5번 노드에 엣지가 1개면 for문을 1번 돌고 그런 식이다.
// 그리고 이 엣지는 nowV라는 노드가 볼 때, start(자기 자신), end(연결된 노드), value(비용)을 가진 객체다.
// 따라서 이 for문은 주어진 노드에 연결된 엣지를 개수만큼 꺼내 위에서 선언한 pq에 넣어 비용을 기준으로 엣지를 오름차순 정렬시킨다.
// 이때 해당 노드의 모든 엣지를 무조건 가져올 수도 있찌만 이미 방문한 노드는 다시 계산할 필요가 없으니 if(!visit[edge.end]) { } 를 통해 방문된 노드와 연결된 엣지는 무시한다.
for (Edge edge : graph[nowV]) {
// Edge가 start -> end니까. start가 지금 들어온 nowV번 노드고, end가 start에서 뻗어 나간 엣지의 도착 방향의 노드다.
// 이미 방문된 노드의 엣지는 무시하기 위한 로직.
// *** 여기서 중요한 것은 방문한 노드가 end인 엣지를 추가하지 않았지만 그게 더 효율적일 수도 있다. 즉, 눈으로 볼 때는 그게 쉽게 보이지만
// 컴퓨터로 볼 때는 그렇지 않다. 그러면 어떻게 처리를 할까? 방문한 노드 방향의 엣지를 담지 않는 대신 해당 엣지는 이미 이전에 반대편 노드가 start로 들어왔을 때
// pq에 담겨있고, 그 pq를 매번 돌 때마다 초기화 하지 않기 때문에 유지가 된다. 즉,
if(!visit[edge.end]) {
pq.add(edge);
}
}
// nowV 노드의 엣지를 비용으로 정렬시킨 PriorityQueue가 모두 사라질 때까지 반복한다.
while(!pq.isEmpty()) {
// nowV 노드의 엣지중 비용이 작은 것부터 꺼낸다.
Edge edge = pq.poll();
// 해당 엣지의 end(nowV와 연결된 노드)가 방문하지 않았다면 if문으로 들어간다.
if(!visit[edge.end]) {
// 연결된 노드를 방문한 노드를 담는 queue에 담는다.
// 그냥 nowV = edge.end에 바로 넣어도 될 것 같지만, 더이상 추가할 mst가 없다면 큐가 비어있을거고, while(!queue.isEmpty())를 종료하기 위해서 큐를 사용한다.
queue.add(edge.end);
// 그리고 그 엣지를 mst에 넣는다.
mst.add(edge);
// mst를 찾았으면 해당 nowV의 다른 엣지(지금 찾은 엣지보다 비용이 더 큰 엣지)는 반복을 중단한다.
break;
}
}
}
}
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}코드 중복으로는 지울만한게 별로 없다. 방문 중인 노드 nowV에서 최소의 엣지를 찾은 후 visit 함수를 호출하는 것 하나만 제거했다.(while문 시작하자마자 visit[nowV] = true; 가 있어서 중복되기 때문에)
Prim3.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Prim3 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static LinkedList<Edge>[] graph; // Kruskal에서는 각 노드를 PriorityQueue<Edge>에 넣었다면, 여기서 graph는 해당 노드가 start인 모든 엣지를 넣는다. 즉, 3번 노드와 연결된 엣지가 5개면 3번 graph[3] start가 3인 엣지를 5개 가지고 있는 배열이 된다.
static boolean[] visit; // 노드의 방문 여부 (Kruskal에서는 int[] arr에 각 노드의 부모가 누구인지를 저장했다.)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
// 각 노드를 graph로 정의한다. 배열을 V+1개로 만들면 인덱스가 0 ~ V까지 배정되고, 0을 버리고 1 ~ V번 인덱스를 사용한다.
graph = new LinkedList[V+1];
// 각 노드의 방문 여부를 boolean 타입의 일차운 단순 배열로 만든다.
visit = new boolean[V+1];
// 1번 노드부터 V번 노드까지 LinkedList<Edge>[] 타입의 graph 변수에 넣는다. (1 ~ 6번 노드가 샘플로 주어진다.)
for (int i = 1; i <= V; i++) {
graph[i]= new LinkedList<>();
}
mst = new ArrayList<>();
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당. 엣지가 총 9개 주어졌으니 9번 돈다.)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 노드1에서 노드2로 가는 방향으로 저장.
graph[v1].add(new Edge(v1,v2,value));
// 노드2에서 노드1로 가는 방향으로 저장.
graph[v2].add(new Edge(v2,v1,value));
// 왜 양방향으로 저장할까?
// 노드를 기준으로 뻗어 나가는 엣지를 정의하고 그 중 비용이 작은 것을 택하는 것이기 때문에 각 노드에서 뻗어나가는 모든 엣지를 합하면 결국 양방향이 되고 전체 엣지의 2배가 된다.
}
// Kruskal에서 while(mst.size() < (V-1)) { }에 해당. 메인 메소드에 다 넣지 않고 빼놓은 것 뿐이다.
makeMst();
System.out.println(mst);
}
static void makeMst() {
// 1. 시작 노드는 아무거나 지정.
// 2. 선택한 노드에 연결된 엣지들을 PrioityQueue에 넣는다. (비용을 기준으로 오름차순 정렬됨.)
// 3. 비용이 최소인 Edge 객체를 poll()한다. 이 객체는 [start, end, value]를 갖고 있고, end를 visit 검사를 통해 방문 여부를 확인한다.
// 4. 2~3 반복. n-1개의 간선이 선택할때까지 or 모든 정점이 연결될때까지
// 노드를 기준으로 연결된 엣지를 담을 PriorityQueue를 하나 인스턴스화 한다. 그러면 해당 노드에 연결된 엣지들을 비용을 기준으로 오름차순 정렬한다.
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 프림 알고리즘을 돌리기 위해 현재 방문중인 노드를 nowV라는 int타입 변수에 넣는다.
// 1로 임의로 정한 것은 시작점을 1로 하겠다는 의미다. 3에서 시작하고 싶다면 3을 넣으면 된다.
int nowV = 1;
while(mst.size() < (V-1)) {
// 현재 노드는 방문 했으니 true로 바꾼다.
visit[nowV] = true;
// LinkedList<Edge>[] graph에 모든 노드를 담고 시작했다. nowV에 해당하는 노드의 엣지를 하나씩 꺼낸다.
// 즉, 1번 노드에 엣지가 3개면 각 엣지로 for문을 3번 돌거고, 5번 노드에 엣지가 1개면 for문을 1번 돌고 그런 식이다.
// 그리고 이 엣지는 nowV라는 노드가 볼 때, start(자기 자신), end(연결된 노드), value(비용)을 가진 객체다.
// 따라서 이 for문은 주어진 노드에 연결된 엣지를 개수만큼 꺼내 위에서 선언한 pq에 넣어 비용을 기준으로 엣지를 오름차순 정렬시킨다.
// 이때 해당 노드의 모든 엣지를 무조건 가져올 수도 있찌만 이미 방문한 노드는 다시 계산할 필요가 없으니 if(!visit[edge.end]) { } 를 통해 방문된 노드와 연결된 엣지는 무시한다.
for (Edge edge : graph[nowV]) {
// Edge가 start -> end니까. start가 지금 들어온 nowV번 노드고, end가 start에서 뻗어 나간 엣지의 도착 방향의 노드다.
// 이미 방문된 노드의 엣지는 무시하기 위한 로직.
// *** 여기서 중요한 것은 방문한 노드가 end인 엣지를 추가하지 않았지만 그게 더 효율적일 수도 있다. 즉, 눈으로 볼 때는 그게 쉽게 보이지만
// 컴퓨터로 볼 때는 그렇지 않다. 그러면 어떻게 처리를 할까? 방문한 노드 방향의 엣지를 담지 않는 대신 해당 엣지는 이미 이전에 반대편 노드가 start로 들어왔을 때
// pq에 담겨있고, 그 pq를 매번 돌 때마다 초기화 하지 않기 때문에 유지가 된다. 즉,
if(!visit[edge.end]) {
pq.add(edge);
}
}
// nowV 노드의 엣지를 비용으로 정렬시킨 PriorityQueue가 모두 사라질 때까지 반복한다.
while(!pq.isEmpty()) {
// nowV 노드의 엣지중 비용이 작은 것부터 꺼낸다.
Edge edge = pq.poll();
// 해당 엣지의 end(nowV와 연결된 노드)가 방문하지 않았다면 if문으로 들어간다.
if(!visit[edge.end]) {
// 이제 유효한 엣지를 찾았으니 방문중인 노드 nowV는 다음 노드로 이동한다.
nowV = edge.end;
// 그리고 그 엣지를 mst에 넣는다.
mst.add(edge);
// mst를 찾았으면 해당 nowV의 다른 엣지(지금 찾은 엣지보다 비용이 더 큰 엣지)는 반복을 중단한다.
break;
}
}
}
}
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
// TODO Auto-generated method stub
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}마지막 노드를 방문한 다음 바로 종료하면 좋겠는데, 마지막 노드 방문 후 현재 방문중인 노드(nowV)를 임시(temp)로 담는 queue가 완전히 비어있을 때까지 돌리는 로직 때문에 마지막 노드에서 혹시 유효한 엣지가 있는지를 검사하며 아직 사용하지 못하고 큐에 남아있는 모든 엣지를 모두 검사한 다음 로직을 종료한다. 즉... 해당 로직은 모든 엣지를 다 검사하고 끝낸다. 굳이......
1 ) while문을 큐가 빌 때 까지 도는 대신 mst의 크기가 (V-1)보다 작을때까지 돌도록 해서, 불필요한 반복을 줄인다.
2 ) 따라서 큐에 넣고 빼는 대신, 바로 nowV에 바로 현재 방문중인 노드를 넣어준다.
사실... 여기서 pq에 담긴 객체 중 start와 end가 모두 visit = true인 것을 바로 제거하면 불필요한 로직을 더 줄일 수 있을 것 같긴 한데, 오히려 이걸 검사하는게 더 많은 로직을 실행해서 비효율적일 것 같아서 그 부분은 건드리지 않았다.
Tag.
크러스컬 알고리즘, 크루스칼 알고리즘, kruskal algorithm, kruskal's algorithm, kruskal's, 프림 알고리즘, prim's algorithm, prim's, prim algorithm, Prim Algorithm, Prim's Algorithm
'개발자 > Algorithm' 카테고리의 다른 글
| Kruskal & Prim 비교 (0) | 2020.09.22 |
|---|---|
| Kruskal's Algorithm (0) | 2020.09.14 |
| 05. 장기판 포 말잡기 (0) | 2020.08.30 |
| 04. 토끼 잡기 (0) | 2020.08.28 |
| 02. 수열 A와 수열 B가 같은지 확인하기 (0) | 2020.08.24 |