普里姆算法


难度级别 中等
经常问 亚马逊 思科 Samsung
图表 贪婪 最小生成树 普里姆算法

Prim的算法用于查找 最小生成树(MST) 连接或无向的 图形。 图的生成树是一个子图,它也是一个 并包括所有顶点。 最小生成树是具有最小边缘权重总和的生成树。

使用案列

图表

普里姆算法

最小生成树(MST)

普里姆算法

普里姆算法的算法

Prim的算法是一种贪婪算法,它维护两组,一组代表包含的顶点(在MST中),另一组代表不包含的顶点(在MST中)。
在每个步骤中,它都会找到将集1的顶点连接到集2的顶点并将其包含在集1(或MST)的另一侧的顶点的最小权重边。
将一组顶点连接到另一组顶点的一组边称为 在图论中 Prim的算法找到了切口中最小的权重边,并将顶点包含在MST的该边上,并重复此过程,直到所有顶点都包含在MST中。

  1. 创建一个包含MST的数组,该数组表示是否包含当前顶点(在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}

选择具有minEdgeCut值的顶点(不包含在MST中),即,将顶点0包含在MST中,并更新其相邻的minEdgeCut值。 所以,
includedMST [] = {true,false,false,false}
minEdgeCut [] = {0,5,8,INFINITE}

这次选择了顶点1,因为它不包含在MST中,并且具有最小的minEdgeCut值,将其包含在MST中并更新其邻近值。 所以,
includedMST [] = {true,true,false,false}
minEdgeCut [] = {0,5,8,15}

选择了顶点2。 将其包含在MST中并更新相邻的。 所以,
includedMST [] = {true,true,true,false}
minEdgeCut [] = {0,5,8,15}

选择了顶点3。 将其包含在MST中并更新相邻的。 所以,
includedMST [] = {true,true,true,true}
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顶点的邻接表。

參考資料