프림의 최소 스패닝 트리 알고리즘_2

1. 모든 간선 정보를 저장 (adjacent_edges)

2. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)'에 삽입

3. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list)에 삽입

4. 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출해서,

   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입

5. 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(connected_nodes)'에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입

6. 선택된 간선은 간선 리스트에서 제거

7. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

프림 알고리즘

정점들의 정보와 간선들의 정보로 그래프 만들기

public class Prim_Algorithm {

인접 간선들을 담기위한 배열 선언
static List<Edge_prim>[] adjacent_edges;

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;
    adjacent_edges = new ArrayList[N];
    for (int i = 0; i < N; i++)
        adjacent_edges[i] = new ArrayList<>();
	
    시작 정점을 정한다(아무거나)
    char start_node = 'A';
    List<Edge_prim> result = prim(start_node, list);
    result.forEach(System.out::println);
}
//출력
5 : A - D
6 : D - F
7 : D - E
5 : E - C
7 : A - B
9 : E - G

class Edge_prim implements Comparable<Edge_prim>
{
    int weight;
    char from;
    char to;
    Edge_prim (int weight, char from, char to){
        this.weight = weight;
        this.from = from;
        this.to = to;
    }

    @Override
    public String toString() {
        return this.weight +" : "+this.from + " - " + this.to;
    }

    @Override
    public int compareTo(Edge_prim o) {
        return this.weight < o.weight ? -1 : 1;
    }
}

모든 정점에 대해서 각 정점에 연결된 간선 정보들을 바탕으로 최소 신장 트리 구현

private static List<Edge_prim> prim(char start_node, List<Edge_prim> list) {
    최소 신장 트리를 담는 리스트
    List<Edge_prim> MST = new ArrayList<>();

    모든 간선 정보 저장
    for (Edge_prim edge : list){
        adjacent_edges[edge.from - 'A'].add(new Edge_prim(edge.weight, edge.from, edge.to));
        adjacent_edges[edge.to - 'A'].add(new Edge_prim(edge.weight, edge.to, edge.from));
    }

    연결된 모든 정점들의 집합
    List<Character> connected_nodes = new ArrayList<>();
    connected_nodes.add(start_node);

    후보군 간선 Queue -> start노드에 연결된 간선 정보들이 들어간다
    PriorityQueue<Edge_prim> candidate_edge_list = 
    		new PriorityQueue<>(adjacent_edges[start_node - 'A']);

    모든 후보군들이 없어질 때 까지
    while (!candidate_edge_list.isEmpty())
    {
        간선의 가중치가 가장 작은 간선을 뽑는다 - 우선순위 큐이므로 자동으로 맨위에것이다
        Edge_prim edge = candidate_edge_list.poll();
        
        연결된 노드에 포함되지 않는다면 넣는다
        if (!connected_nodes.contains(edge.to)) {
            connected_nodes.add(edge.to);
            MST.add(edge);
            
            다음 노드의 인접 간선들에 대해 이미 연결된 노드에 포함되지 않는다면! 후보군 간선 Q에 넣는다
            for (Edge_prim nextEdge : adjacent_edges[edge.to - 'A']) {
                if (!connected_nodes.contains(nextEdge.to))
                    candidate_edge_list.add(nextEdge);
            }
        }
    }
    return MST;
}

시간 복잡도

최악의 경우는, 모든 간선 E에 대해서 우선순위 큐를 사용할 경우로 O(E * log E)이다