최소신장트리-프림알고리즘(백준 1197번)

이 문제같은 경우는 최소신장트리를 구하는 알고리즘이다. 최소신장트리를 구하는 알고리즘은 크게 프림알고리즘과 크루스칼알고리즘 두가지가 있다. 여기서 조금더 구현하기가 수월한 프림알고리즘을 이용하여 최소신장트리를 구현할것이다.

---

1. 최소신장 트리란?

---

최소 신장트리란 주어진 그래프에서 모든 정점을 연결하며 그 비용이 최소인 간선만 연결된 트리를 말한다.

---

2.프림 알고리즘(그림으로 설명하는 것이 편할 것같아 그림으로 ㅅ

---

package graph;
 
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
class AdjVertex implements Comparable<AdjVertex> {
    int adjVertex;
    int weight;
    public AdjVertex(int adjVertex,int weight) {
        // TODO Auto-generated constructor stub
        this.adjVertex=adjVertex;
        this.weight=weight;
    }
    @Override
    public int compareTo(AdjVertex o) {
        // TODO Auto-generated method stub
        if(this.weight>o.getWeight()) return 1;
        else if(this.weight==o.getWeight()) return 0;
        else return -1;
    }
    public int getAdjVertex() {
        return adjVertex;
    }
    public void setAdjVertex(int adjVertex) {
        this.adjVertex = adjVertex;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
}
public class Baekjun1197MinSpanningTree {
    
    static ArrayList<AdjVertex>[] vertexList;
    static boolean visited[];
    static int result;
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int V=sc.nextInt();
        int E=sc.nextInt();
        
        vertexList=new ArrayList[V+1];
        visited=new boolean[V+1];
        
        //인접리스트 초기화
        for(int i=1;i<V+1;i++) {
            vertexList[i]=new ArrayList<AdjVertex>();
        }
        for(int i=0;i<E;i++) {
            int start=sc.nextInt();
            int end=sc.nextInt();
            int weight=sc.nextInt();
            AdjVertex av=new AdjVertex(end, weight);
            AdjVertex av2=new AdjVertex(start, weight);
            vertexList[start].add(av);
            vertexList[end].add(av2);
        }
        //최소값을 빼주기 위한 우선순위 큐
        PriorityQueue<AdjVertex> pq=new PriorityQueue<AdjVertex>();
        visited[1]=true;
        Iterator<AdjVertex> it=vertexList[1].iterator();
        while(it.hasNext()) {
            pq.offer(it.next());
        }
        int count=0;
        while(!pq.isEmpty()) {
            AdjVertex pollVertex=pq.poll();
            int v=pollVertex.getAdjVertex();
            if(visited[v]==true) continue;
            int w=pollVertex.getWeight();
            result+=w;
            visited[v]=true;
            count++;
            if(count==V+1) break;
            Iterator<AdjVertex> it2=vertexList[v].iterator();
            while(it2.hasNext()) {
                pq.add(it2.next());
            }
        }
        System.out.println(result);
    }
}
 

다익스트라 알고리즘과 비슷한 로직을 가집니다. 다만 큐에서 최소값을 빼주며 방문한 정점들을 체크를 해주어서 이미 체크된 정점 같은 경우는 결과값에 포함시키지않는다.