알고리즘 - MST

MST

---

MST

• Minimum Spanning Trees. 최소 신장 트리.

• 조건: 싸이클이 없는 무향 연결 그래프. 연결 그래프란 모든 정점 간에 경로가 존재하는 그래프를 말한다. 

• 간선의 합이 최소인 신장트리를 말한다.

 

Prim Algorithmn

• 임의의 시작 노드를 골라 min heap에 insert한 후 노드와 연결된 노드를 min heap에 insert해준다. 거리가 작은 노드부터 꺼내며 꺼낼 때마다 연결된 노드를 찾아 min heap에 넣어주는 과정을 반복한다. 

• min heap에 저장되는 정보는 현재 노드 정보와 이전 노드에서 현재 노드까지의 거리 정보이다.
• 수행시간: O(ElogV)
• 구현 with JAVA (백준 1197 최소 스패닝 트리)

public static void prim() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.offer(new Node(1, 0)); //1번 노드부터 시작.
        
        while(!q.isEmpty()) {
            Node current = q.poll(); //큐에서 cost가 가장 작은 노드를 꺼낸다.
            
            if(visited[current.node] == false) visited[current.node] = true;
            else continue; //이미 방문한 노드는 무시한다.     
            
            min += current.cost;
            for(int i = 0; i < list[current.node].size(); i++) {
                Node next = list[current.node].get(i);
                if(visited[next.node] == false) q.offer(next);
            }
        }
    }

 

reference