프림의 알고리즘

난이도 중급
자주 묻는 질문 아마존 시스코 삼성
Graph 탐욕스러운 최소 스패닝 트리 프림의 알고리즘조회수 37

Prim의 알고리즘은 최소 스패닝 트리 (MST) 연결되거나 지시되지 않은 그래프. 그래프의 스패닝 트리는 또한 하위 그래프입니다. 나무 모든 정점을 포함합니다. 최소 스패닝 트리는 최소 에지 가중치 합계가있는 스패닝 트리입니다.

Graph

프림의 알고리즘

최소 스패닝 트리 (MST)

프림의 알고리즘

Prim의 알고리즘을위한 알고리즘

Prim의 알고리즘은 두 세트를 유지하는 탐욕스러운 알고리즘입니다. 하나는 포함 된 정점 (MST)을 나타내고 다른 하나는 포함되지 않은 정점 (MST)을 나타냅니다.
모든 단계에서 세트 1의 정점을 세트 2의 정점에 연결하고 세트 1 (또는 MST)에 대한 가장자리의 다른 쪽 정점을 포함하는 최소 가중치 가장자리를 찾습니다.
정점 집합을 다른 정점 집합에 연결하는 가장자리 그룹은 절단 그래프 이론에서는 Prim의 알고리즘은 절단에서 최소 가중치 가장자리를 찾고 MST의이 가장자리에 정점을 포함하고 모든 정점이 MST에 포함될 때까지이 프로세스를 반복합니다.

  1. 현재 정점이 포함되는지 여부를 나타내는 includedMST 배열을 만듭니다 (MST에).
  2. 현재 정점의 컷에서 최소 가중치 가장자리를 나타내는 다른 배열 minEdgeCut을 만듭니다.
  3. minEdgeCut을 모든 정점에 대해 INFINITE로 초기화하고 첫 번째 정점에 대해 0을 초기화합니다.
  4. 포함되지 않은 (MST에) minEdgeCut 값이있는 정점 (예 : u)을 선택하고 MST에 포함합니다.
  5. 선택한 정점에 대해 포함되지 않은 (MST에) 모든 인접 정점에 대한 minEdgeCut 값을 업데이트합니다.
  6. 값을 업데이트하려면 모든 인접 정점 v에 대해 가장자리 uv의 가중치가 v의 현재 minEdgeCut 값보다 작 으면 minEdgeCut 값을 uv의 가중치로 업데이트합니다.
  7. 모든 정점이 포함되지 않을 때까지 4, 5, 6 단계를 반복합니다.

Prim의 알고리즘에 대한 설명

아래 이미지에 표시된 그래프를 고려하여 위의 알고리즘을 적용하여 MST를 찾습니다.

프림의 알고리즘

처음에는 MST에 꼭지점이 없으므로
includedMST [] = {거짓, 거짓, 거짓, 거짓}
minEdgeCut [] = {0, INFINITE, INFINITE, INFINITE}

MST에 포함되지 않은 minEdgeCut 값이있는 정점, 즉 정점 0이 선택되고이를 MST에 포함하고 인접 항목의 minEdgeCut 값을 업데이트합니다. 그래서,
includedMST [] = {참, 거짓, 거짓, 거짓}
minEdgeCut [] = {0, 5, 8, INFINITE}

이번에는 정점 1이 MST에 포함되지 않고 최소 minEdgeCut 값을 갖고 있으므로 MST에 포함하고 인접 항목을 업데이트하므로 이번에 선택됩니다. 그래서,
includedMST [] = {참, 참, 거짓, 거짓}
minEdgeCut [] = {0, 5, 8, 15}

정점 2가 선택됩니다. MST에 포함하고 인접 항목을 업데이트하십시오. 그래서,
includedMST [] = {참, 참, 참, 거짓}
minEdgeCut [] = {0, 5, 8, 15}

정점 3가 선택됩니다. MST에 포함하고 인접 항목을 업데이트하십시오. 그래서,
includedMST [] = {참, 참, 참, 참}
minEdgeCut [] = {0, 5, 8, 15}

프림의 알고리즘

모든 정점이 MST에 포함되어 있으므로 중지합니다.

Prim 알고리즘 용 JAVA 코드

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PrimsAlgorithm {
    private static void findPrintMST(ArrayList<Edge> graph[]) {
        int n = graph.length;
        // parent array stores the parent vertex of the current vertex in MST
        int parent[] = new int[n];
        int minEdgeCut[] = new int[n];
        boolean includedMST[] = new boolean[n];

        // Initialise all minEdgeCut values as INFINITE and all vertices as not included in MST
        for (int i = 0; i < n; i++) {
            minEdgeCut[i] = Integer.MAX_VALUE;
            includedMST[i] = false;
        }

        // Initialise minEdgeCut value of first vertex as 0
        minEdgeCut[0] = 0;
        parent[0] = -1;

        // Create a min heap to pick the smallest minEdgeCut value at every step
        // Min heap of vertex and corresponding minEdgeCut value
        PriorityQueue<Element> minHeap = new PriorityQueue<>(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return Integer.compare(o1.minEdgeCutValue, o2.minEdgeCutValue);
            }
        });
        for (int i = 0; i < n; i++)
            minHeap.add(new Element(i, minEdgeCut[i]));

        // While all vertices are not included in MST
        while(!minHeap.isEmpty()) {
            // Select the vertex with minimum minEdgeCut value
            int u = minHeap.poll().vertex;

            // Update minEdgeCut value for all adjacent vertices
            for (int j = 0; j < graph[u].size(); j++) {
                Edge curr = graph[u].get(j);
                // If weight of edge u-v is less than the current minEdgeCut value of v
                // update the minEdgeCut value as weight of u-v
                if (minEdgeCut[curr.to] > curr.weight && !includedMST[curr.to]) {
                    minEdgeCut[curr.to] = curr.weight;
                    parent[curr.to] = u;
                }
            }
        }

        // Print MST
        for (int i = 1; i < n; i++) {
            System.out.println("Edge from " + parent[i] + " to " + i + " weight " + minEdgeCut[i]);
        }
    }

    public static void main(String[] args) {
        // Graph
        ArrayList<Edge> graph[] = new ArrayList[4];
        for (int i = 0; i < 4; i++)
            graph[i] = new ArrayList<>();

        // Make the graph in given example
        graph[0].add(new Edge(1, 5));
        graph[0].add(new Edge(2, 8));
        graph[1].add(new Edge(0, 5));
        graph[1].add(new Edge(2, 10));
        graph[1].add(new Edge(3, 15));
        graph[2].add(new Edge(0, 8));
        graph[2].add(new Edge(1, 10));
        graph[2].add(new Edge(3, 20));
        graph[3].add(new Edge(1, 15));
        graph[3].add(new Edge(2, 20));

        // Find MST using Prim's Algorithm and print it
        findPrintMST(graph);
    }

    // Class representing an edge in the graph
    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    // Class representing pair of vertex and its minEdgeCut value
    // Used in minHeap in Prim's Algorithm for MST
    static class Element {
        int vertex;
        int minEdgeCutValue;

        public Element(int vertex, int minEdgeCutValue) {
            this.vertex = vertex;
            this.minEdgeCutValue = minEdgeCutValue;
        }
    }
}

Prim의 알고리즘을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// Class representing pair of vertex and its minEdgeCut value
// Used in minHeap in Prim's Algorithm for MST
class Element {
    public:
    int vertex;
    int minEdgeCutValue;
    Element(int v, int value) {
        vertex = v;
        minEdgeCutValue = value;
    }
};

// Class representing an edge in the graph
class Edge {
    public:
    int to;
    int weight;
    Edge(int t, int w) {
        to = t;
        weight = w;
    }
};

// Comparator to sort Element according to minEdgeCutValue
struct ElementComp {
    bool operator ()(const Element& e1, const Element& e2) {
        return (e2.minEdgeCutValue < e1.minEdgeCutValue);
    }
};

void findPrintMST(vector<Edge> graph[], int n) {
    // parent array stores the parent vertex of the current vertex in MST
    int parent[n];
    int minEdgeCut[n];
    bool includedMST[n];
    
    // Initialise all minEdgeCut values as INFINITE and all vertices as not included in MST
    for (int i = 0; i < n; i++) {
        minEdgeCut[i] = INT_MAX;
        includedMST[i] = false;
    }
    
    // Initialise minEdgeCut value of first vertex as 0
    minEdgeCut[0] = 0;
    parent[0] = -1;
    
    // Create a min heap to pick the smallest minEdgeCut value at every step
    // Min heap of vertex and corresponding minEdgeCut value
    priority_queue<Element, vector<Element>, ElementComp> minHeap;
    for (int i = 0; i < n; i++) {
        Element ele(i, minEdgeCut[i]);
        minHeap.push(ele);
    }
    
    // While all vertices are not included in MST
    while (minHeap.size() != 0) {
        // Select the vertex with minimum minEdgeCut value
        int u = minHeap.top().vertex;
        minHeap.pop();
        
        // Update minEdgeCut value for all adjacent vertices
        for (int j = 0; j < graph[u].size(); j++) {
            Edge curr = graph[u][j];
            // If weight of edge u-v is less than the current minEdgeCut value of v
            // update the minEdgeCut value as weight of u-v
            if (minEdgeCut[curr.to] > curr.weight && includedMST[curr.to] == false) {
                minEdgeCut[curr.to] = curr.weight;
                parent[curr.to] = u;
            }
        }
    }
    
    // Print MST
    for (int i = 1; i < n; i++) {
        cout<<"Edge from "<<parent[i]<<" to "<<i<<" weight "<<minEdgeCut[i]<<endl;
    }
}

int main() {
    vector<Edge> graph[4];
    
    // Make the graph in given example
    Edge e1(1, 5);
    Edge e2(2, 8);
    Edge e3(0, 5);
    Edge e4(2, 10);
    Edge e5(3, 15);
    Edge e6(0, 8);
    Edge e7(1, 10);
    Edge e8(3, 20);
    Edge e9(1, 15);
    Edge e10(2, 20);
    
    graph[0].push_back(e1);
    graph[0].push_back(e2);
    graph[1].push_back(e3);
    graph[1].push_back(e4);
    graph[1].push_back(e5);
    graph[2].push_back(e6);
    graph[2].push_back(e7);
    graph[2].push_back(e8);
    graph[3].push_back(e9);
    graph[3].push_back(e10);
    
    // Find MST using Prim's Algorithm and print it
    findPrintMST(graph, 4);
    
    return 0;
}
Edge from 0 to 1 weight 5
Edge from 0 to 2 weight 8
Edge from 1 to 3 weight 15

복잡성 분석

시간 복잡성 = O (E log (V)), 여기서 E –> 가장자리 수 및 V –> 정점 수.

공간 복잡성 = O (E + V) E 개의 모서리와 V 개의 정점이있는 인접 목록을 생성하기 때문입니다.

참조

Translate »