개선된 프림의 최소 스패닝 트리 알고리즘_3

개선된 프림 알고리즘

• 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식이다
• 시간복잡도가 E log E가 아닌 E log V이다 -> 간선이 복잡한 그래프일 경우 크루스칼 또는 이전 프림알고리즘 보다 시간복잡도가 더욱 개선된다

구현 방식

• 초기화 - (정점 : key)구조를 만들어 놓고, 특정(시작) 정점의 key 값은 0으로 하고, 이외의 정점들의 key 값들은 무한대로 놓고 모든 (정점 : key)값을 우선순위 큐에 넣는다
• 가장 key값이 작은 (정점 : key)값을 추출해서
  • 해당 정점에 인접한 정점(간선이 아닌 정점!!)들에 대해 key값과 연결된 가중치를 비교해서 인접한 간선의 가중치가 더 작다면 해당 (정점 : key)값의 key값을 가중치값으로 갱신한다
  • 여기서 (정점:key)값을 갱신하면, 우선순위 큐는 최소의 key값을 가지는 (정점:key)를 루트노드에 올려놓는다

위 내용은 파이썬의 heapdict 라이브러리를 사용해서 heapify를 이용하여 구현하는 것
자바에서는 PriorityQueue를 이용하여 구현했다

코드 구현

Main

public class advanved_prim_algorithm {
static boolean[] visited;
public static void main(String[] args) {
    List<Edge_prim> list = new ArrayList<>();
    list.add(new Edge_prim(7, 'A', 'B'));
    list.add(new Edge_prim(5, 'A', 'D'));
    list.add(new Edge_prim(8, 'B', 'C'));
    list.add(new Edge_prim(9, 'B', 'D'));
    list.add(new Edge_prim(7, 'B', 'E'));
    list.add(new Edge_prim(5, 'C', 'E'));
    list.add(new Edge_prim(7, 'D', 'E'));
    list.add(new Edge_prim(6, 'D', 'F'));
    list.add(new Edge_prim(8, 'E', 'F'));
    list.add(new Edge_prim(9, 'E', 'G'));
    list.add(new Edge_prim(11, 'F', 'G'));
    
    int N = 7; //정점의 개수
    visited = new boolean[N];
    
    List<Edge_prim> result = prim('A', list);
    int sum = result.stream().mapToInt(s -> s.weight).sum();
    System.out.println(sum);
}
}

prim 알고리즘 구현 부분

private static List<Edge_prim> prim(char start, List<Edge_prim> list) {

    List<Edge_prim> MST = new ArrayList<>();

    //인접 행렬을 저장하기 위한 초기화
    List<Edge_prim>[] adjacent_Edge = new ArrayList[visited.length];
    for (int i = 0; i < visited.length; i++)
        adjacent_Edge[i] = new ArrayList<>();

    //모든 인접 행렬에 대한 정보를 저장
    for (Edge_prim edge : list){
        adjacent_Edge[edge.from - 'A'].add(new Edge_prim(edge.weight, edge.from, edge.to));
        adjacent_Edge[edge.to - 'A'].add(new Edge_prim(edge.weight, edge.to, edge.from));
    }

    //시작 정점 설정, 시작 정점에 연결된 모든 간선 정보 넣기
    visited[start - 'A'] = true;
    PriorityQueue<Edge_prim> pq = new PriorityQueue<>(adjacent_Edge[start - 'A']);

    while (!pq.isEmpty()){
        Edge_prim now = pq.poll();
        if (!visited[now.to - 'A']) {
            visited[now.to - 'A'] = true;
            MST.add(now);
            for (Edge_prim next : adjacent_Edge[now.to - 'A']){
                if (!visited[next.to - 'A'])
                    pq.add(next);
            }
        }
    }

    return MST;
}