精华内容
下载资源
问答
  • 2022-03-21 19:38:33

    一.基本概念

    普里姆算法是最小生成树的一种算法,在了解最小生成树之前我们先了解什么是生成树?

    对于一个顶点个数为n的图,若存在一个子图含有n个顶点,n-1条不构成回路的边,就叫生成树

    这个概念也很好理解,在我们的树论概念中,树是只有一个前驱(即一个孩子至少有一个父亲,除根节点),而如果一个图构成了回路,等于:"我的孩子成为了我的父亲”,这种逻辑关系显然有时候不利于我们处理一些对于图论的应用问题,故我们需要生成树来区别于平常的子图。

    当然我们学习连通图的时候,发现:极小连通图也是含n个顶点,n-1个边的

    所以生成树就是连通图中的极小连通图,那么我们可以得出概念:生成树就是尽可能少的用边,而尽可能广的连接完所有的顶点,我们可以通过DFS或者BFS来生成两种不同的生成树(原理:DFS和BFS遍历算法都是具有不可逆性质的,即DFS和BFS都有visited数组来保证每个数据都最多被访问过一次和“出去”过一次,因此不会形成回路)

    而生成树中带有权值时,两顶点之间的途径的边权总值最小,这就是最小生成树

    二.算法概要

    普里姆思想:每次我们都选择一个当前【已被选择的顶点集合】中可以【被选择到的边】中的【边权最小】的一个边,然后使得边那端的另一个顶点加入【已被选择的顶点集合】

    重复此操作,每次都会消去一个顶点,然后增加一个边,最后使得顶点个数为n,边的个数为n-1,注意,由于我们无论怎么样都只选n-1条边作为生成树的边,所以无论如何都不会形成回路,所以我们放心加边就可以了,这也就是与克鲁斯卡尔算法不同的地方,普里姆算法只关心顶点的个数,不关心边的个数,故时间复杂度为O(N^{2}) 与边数无关。

    如果读者并未学习过普里姆算法,可以跳转至B站王卓数据结构进行学习最小生成树的具体过程,本文章目的在于对普里姆算法的实现和操作解释。

    三.算法实现

    (1.)准备阶段:我们需要初始化图的边和顶点,这里采用邻接矩阵来存储边(其实很多图论算法都是以邻接矩阵作为基础的,因为我们在算法应用的时候,对某顶点与某顶点之间是否有边的查询是非常频繁的,如果使用邻接表会特别麻烦,当然,邻接矩阵浪费空间的话,可以使用下三角法进行表示,节省空间)

    (2.)确定辅助函数或者数组:观察我刚刚描述的,一共有三个集体【已经被选择的顶点集合】【被选择到的边】,【边权】,那么笔者的写法是,设立PowerList数组(我称他为决策层,意思是当前层,可以被选择的顶点的权值,若不能被选择为无穷大),设立ConnectIndex(我称他为当前层找到的被选择的那个顶点,用于后边的决策层更新和输出),设立ID数组,ID[I]代表【I作为被访问的一个顶点,此时为某其他顶点访问边权时,找到了下标I对应的那个顶点,此时ID[I]=某其他顶点,也就是为某个边赋值他的“主人”,用于输出】,最后设立一个sum用于计算总权和

    数据结构的算法,当你面对像普里姆,迪杰斯特拉这种看似棘手的算法的时候,不妨自己推一遍流程,然后写一下伪代码,逐一实现伪代码,对理解很有帮助!

    普里姆算法实现伪代码:

    1.初始化一下决策层,也就是把出发点的所有与其他点的距离填进去,然后ID数组的主人全填出发点下标

    2.此时进行循环,先找ConnectIndex,也就是当前决策层下,找到哪条边了?找到的哪条边他的另一头是谁?另一头就是ConnectIndex,因为我们需要ConnectIndex的下标,来得知我们新增加了哪个顶点,找ConnectIndex其实不难,无非就是取所有【可选择的边】的最小权值的那个,只需要排除【已经被选择过的】,当我们获取到ConnectIndex后,我们直接令PowerList[ConnectIndex]=0,由于权值一般大于0,设置成0的代表这个顶点已经被连接,也就是前面的排除是判断条件

    3.此时进行循环,决策层新增加了ConnectIndex,那该下标的新增,会不会导致其他原本不可以被连接的边能连接了呢?或者其他可以被连接的边的权值和更小?其实这时候我们找PowerList,就不能限制【Powerlist【j】!=0】了,因为有可能在前面给当前J下标赋值的一条路并不是最小权值的,可能是我们新增的这条边也可以到达,而且权值更小!这时候我们边更新,边赋值新的主人

    4.打印输出即可

    四.代码展示

    #include <iostream>
    using namespace std;
    #define maxnum 20
    class Graph
    {
    public:
        int vernum, edgenum;
        int edge[maxnum][maxnum];//第i条边与第j条边的权重(若无边则为无穷大)
        string vset[maxnum];//顶点数据
        void prim();//普里姆算法
        void init();
    };
    
    void Graph::init()
    {
        cout << "输出顶点数,边数" << endl;
        cin >> this->vernum >> this->edgenum;
        cout << "下面开始初始化全部边" << endl;
        for (int i = 0;i < this->vernum;i++)
        {
            for (int j = 0;j < this->vernum;j++)
            {
                if (i == j)this->edge[i][j] = 0;
                else
                {
                    edge[i][j] = INT_MAX;
                }
            }
        }
        cout << "矩阵初始化完毕==================================================" << endl;
        cout << "初始化顶点数据" << endl;
        for (int i = 0;i < this->vernum;i++)cin >> this->vset[i];//初始化顶点数据
        cout << "==================================================================" << endl;
        for (int i = 0;i < this->edgenum;i++)
        {   
            int start, end;
            cin >> start >> end;
            cin >> this->edge[start][end];
            this->edge[end][start] = this->edge[start][end];
        }
    }
    
    void Graph::prim()
    {   
        int n = this->vernum;
        int sum = 0;
        int powerlist[maxnum];//当前决策层的最小权值
        int id[maxnum];//第i个节点被连接是通过id[i]作为起点连接的
        for (int i = 1;i < n;i++)
        {
            powerlist[i] = this->edge[0][i];
            id[i] = 0;
        }
        id[0] = 0;
        for (int i = 1;i < n;i++)
        {
            int minval = INT_MAX;
            int connectIndex = 0;
            for (int j = 1;j < n;j++)
            {
                if (powerlist[j] != 0 && powerlist[j] < minval)
                {
                    minval = powerlist[j];
                    connectIndex = j;
                }
            }
            cout << this->vset[id[connectIndex]] << " 出发到 " << this->vset[connectIndex] << " 权值为:" << minval<<endl;
            sum += minval;
            powerlist[connectIndex] = 0;
            for (int j = 1;j < n;j++)
            {
                if (powerlist[j] > this->edge[connectIndex][j])//有新节点加入,看看是否原来的决策层连接不到,或者连接的比较短的能否更新
                {
                    powerlist[j] = this->edge[connectIndex][j];
                    id[j] = connectIndex;
                }
            }
    
        }
        cout << "最终权值和为:" << sum<<endl;
    }
    
    int main()
    {
        Graph g;
        g.init();
        g.prim();
    
    }

    展示效果:

    借用了B站王卓老师的数据样例,结果一致。

     

    文章为笔者笔记,如果文章有错误之处,描述不当之处还请您告知。

    希望这篇文章能给您带来一些收获

    更多相关内容
  • 沈阳航空航天大学 课程设计报告 课程设计名称数据结构课程设计 课程设计题目Prim算法求最小生成树 院系专业: 院系 专 业: 班 级: 学 号: 姓 名: 指导教师: 计算机学院 计算机科学与技术物联网方向 扌旨导教师评语: ...
  • 普里姆算法

    2022-06-02 22:25:01
    普里姆算法(Prim’s algorithm)是图中的一种算法,可在加权连通图中搜索最小生成树。该算法的作用就是根据图中权值找到连接所有顶点的最短路径,也就是连接所有顶点的最小权值之和,也是这个加权图中的最小生成树...

    普里姆(Prim)算法java

    普里姆算法

    普里姆算法(Prim’s algorithm)是图中的一种算法,可在加权连通图中搜索最小生成树。

    该算法的作用就是根据图中权值找到连接所有顶点的最短路径,也就是连接所有顶点的最小权值之和,也是这个加权图中的最小生成树。

    普里姆算法步骤

    1.选取权值最小边的其中一个顶点作为起始点。
    2.找到离当前顶点权值最小的边,并记录该顶点为已选择。
    3.重复第二步,直到找到所有顶点,就找到了图的最小生成树。

    普里姆算法时间复杂度

    假如我们有 V 表示图中的顶点个数,E 表示图中的边个数。

    通过邻接矩阵图表示的简易实现中,找到所有最小权边共需 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nQamMZIL-1654179872656)(https://juejin.cn/equation?tex=O(V%5E%7B2%7D)]) 的运行时间。

    使用简单的二叉堆和邻接表来表示的话,普里姆算法的运行时间则可缩减为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1c3rRc3l-1654179872657)(https://juejin.cn/equation?tex=O(E%20%5Clog%20V%20)])。

    如果使用较为复杂的斐波那契堆,则可将运行时间进一步缩短为 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rJaGMXas-1654179872657)(https://juejin.cn/equation?tex=O(E%2BV%20%5Clog%20V)]),这在连通图足够密集时,可较显著地提高运行速度。

    普里姆算法示例

    img

    根据上面加权连通图找到最小生成树。

    img

    首先选择顶点 A 作为起点。顶点 D、F、B 与 A 相连,且 AD 之间的权值最小,因此选择这条边。此时 A、D 为已选择顶点,E、F、B 为待选择顶点,H、G 为未选择顶点。

    img

    下一个顶点应选择离 A、D 权值最小的顶点,因此选择 AB 这条边。此时 A、D、B 为已选择顶点,E、F、G 为待选择顶点,H 为未选择顶点。

    img

    下一个顶点应选择离 A、D、B 权值最小的顶点,因此选择 DE 这条边。此时 A、D、B、E 为已选择顶点,F、G、H 为待选择顶点,没有未选择顶点。

    img

    下一个顶点应选择离 A、D、B、E 权值最小的顶点,因此选择 EH 这条边。此时 A、D、B、E、H 为已选择顶点,F、G 为待选择顶点,没有未选择顶点。

    img

    下一个顶点应选择离 A、D、B、E、H 权值最小的顶点,因此选择 FH 这条边。此时 A、D、B、E、H、F 为已选择顶点,G 为待选择顶点,没有未选择顶点。

    img

    最后,只剩下一个顶点 G,到顶点 G 的权值最小的是 HG。现在图中所有顶点都连接了,红色连接的边就是最小生成树,最小生成树的权值之和为 42。

    总结

    普里姆算法就是通过一个顶点扩散开找权值最小的边,所经过的顶点和边就是这个图的最小生成树。通过不用的数据结构存储图会导致时间复杂度不一致,用邻接矩阵的时间复杂度是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IASJSjcY-1654179872660)(https://juejin.cn/equation?tex=O(V%5E%7B2%7D)]),二叉堆和邻接表的时间复杂度是 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-23UQZu68-1654179872660)(https://juejin.cn/equation?tex=O(E%20%5Clog%20V%20)])。

    代码

    package com.atguigu.prim;
    
    import java.util.Arrays;
    
    public class PrimAlgorithm {
    	
    	public static void main(String[] args) {
    		
    		//测试看看图是否创建ok
    		char[] data = new char[]{'A','B','C','D','E','F','G'};
    		int verxs = data.length;
    		//邻接矩阵的关系使用二维数组表示,10000这个大数,表示两个点不联通
    		int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};
                
            //创建MGraph对象
            MGraph graph = new MGraph(verxs);
            //创建一个MinTree对象
            MinTree minTree = new MinTree();
            minTree.createGraph(graph, verxs, data, weight);
            //输出
            minTree.showGraph(graph);
           //测试普利姆算法
            minTree.prim(graph, 1);//
    	}
    }
    
    
    //创建最小生成树->村庄的图
    class MinTree {
    	//创建图的邻接矩阵
    	/**
    	 * 
    	 * @param graph 图对象
    	 * @param verxs 图对应的顶点个数
    	 * @param data 图的各个顶点的值
    	 * @param weight 图的邻接矩阵
    	 */
    	public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
    		int i, j;
    		for(i = 0; i < verxs;i++) {//顶点
    			graph.data[i] = data[i];
    			for(j = 0; j < verxs; j++) {
    				graph.weight[i][j] = weight[i][j];
    			}
    		}
    
    	}
    	
    	//显示图的邻接矩阵
    	public void showGraph(MGraph graph) {
    		for(int[] link: graph.weight) {
    			System.out.println(Arrays.toString(link));
    		}
    	}
    	
    	
    	//编写prim算法,得到最小生成树
    	/**
    	 * 
    	 * @param graph 图
    	 * @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...
    	 */
    	public void prim(MGraph graph, int v) {
    		//visited[] 标记结点(顶点)是否被访问过
    		int visited[] = new int[graph.verxs];
    		//visited[] 默认元素的值都是0, 表示没有访问过
    //		for(int i =0; i <graph.verxs; i++) {
    //			visited[i] = 0;
    //		}
    		
    		//把当前这个结点标记为已访问
    		visited[v] = 1;
    		//h1 和 h2 记录两个顶点的下标
    		int h1 = -1;
    		int h2 = -1;
    		int minWeight = 10000; //将 minWeight初始成一个大数,后面在遍历过程中,会被替换
    		for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点,普利姆算法结束后,有 graph.verxs-1边
    			//这个是确定每一次生成的子图 ,和哪个结点的距离最近
    			for(int i = 0;i < graph.verxs;i++) {// i结点表示被访问过的结点
    				for(int j = 0; j < graph.verxs;j++) {
    					if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
    						//替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
    						minWeight = graph.weight[i][j];
    						h1 = i;
    						h2 = j;
    					}
    				}
    			}
    			//找到一条边是最小
    			System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
    			//将当前这个结点标记为已经访问
    			visited[h2] = 1;
    			//minWeight 重新设置为最大值 10000
    			minWeight = 10000;
    		}
    	}
    }
    
    
    class MGraph{
    	int verxs;//表示图的结点的个数
    	char[] data;//存放结点数据
    	int[][] weight;//存放边,就是我们的邻接矩阵
    	
    	public MGraph(int verxs) {
    		this.verxs = verxs;
    		data = new char[verxs];
    		weight = new int[verxs][verxs];
    	}
    	
    }
    
    
    

    verxs;//表示图的结点的个数
    char[] data;//存放结点数据
    int[][] weight;//存放边,就是我们的邻接矩阵

    public MGraph(int verxs) {
    	this.verxs = verxs;
    	data = new char[verxs];
    	weight = new int[verxs][verxs];
    }
    

    }

    
    
    展开全文
  • 普里姆算法在找最小生成树时,将顶点分为两类,一类是在查找的过程中已经包含在树中的(假设为 A 类),剩下的是另一类(假设为 B 类)。 对于给定的连通网,起始状态全部顶点都归为 B 类。在找最小生成树时,选定...
  • prim算法(普里姆算法)详解

    千次阅读 2022-01-21 14:49:36
    prim算法(普里姆算法)详解 了解了什么是最小生成树后,本节为您讲解如何用普里姆(prim)算法查找连通网(带权的连通图)中的最小生成树。 普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个...

    prim算法(普里姆算法)详解

    了解了什么是最小生成树后,本节为您讲解如何用普里姆(prim)算法查找连通网(带权的连通图)中的最小生成树。

    普里姆算法查找最小生成树的过程,采用了贪心算法的思想。对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重复 N-1 次,由 N-1 条权值最小的边组成的生成树就是最小生成树。

    那么,如何找出 N-1 条权值最小的边呢?普里姆算法的实现思路是:

    将连通网中的所有顶点分为两类(假设为 A 类和 B 类)。初始状态下,所有顶点位于 B 类;

    选择任意一个顶点,将其从 B 类移动到 A 类;

    从 B 类的所有顶点出发,找出一条连接着 A 类中的某个顶点且权值最小的边,将此边连接着的 A 类中的顶点移动到 B 类;

    重复执行第 3 步,直至 B 类中的所有顶点全部移动到 A 类,恰好可以找到 N-1 条边。

    举个例子,下图是一个连通网,使用普里姆算法查找最小生成树,需经历以下几个过程:

    在这里插入图片描述

    图 1 连通网

    1. 将图中的所有顶点分为 A 类和 B 类,初始状态下,A = {},B = {A, B, C, D, S, T}。

    2. 从 B 类中任选一个顶点,假设选择 S 顶点,将其从 B 类移到 A 类,A = {S},B = {A, B, C, D, T}。从 A 类的 S 顶点出发,到达 B 类中顶点的边有 2 个,分别是 S-A 和 S-C,其中 S-A 边的权值最小,所以选择 S-A 边组成最小生成树,将 A 顶点从 B 类移到 A 类,A = {S, A},B = {B, C, D, T}。

    在这里插入图片描述

    图 2 S-A 边组成最小生成树

    1. 从 A 类中的 S、A 顶点出发,到达 B 类中顶点的边有 3 个,分别是 S-C、A-C、A-B,其中 A-C 的权值最小,所以选择 A-C 组成最小生成树,将顶点 C 从 B 类移到 A 类,A = {S, A, C},B = {B, D, T}。

    在这里插入图片描述

    图 3 A-C 边组成最小生成树

    1. 从 A 类中的 S、A、C 顶点出发,到达 B 类顶点的边有 S-C、A-B、C-B、C-D,其中 C-D 边的权值最小,所以选择 C-D 组成最小生成树,将顶点 D 从 B 类移到 A 类,A = {S, A, C, D},B = {B, T}。

    在这里插入图片描述

    图 4 C-D 边组成最小生成树

    1. 从 A 类中的 S、A、C、D 顶点出发,到达 B 类顶点的边有 A-B、C-B、D-B、D-T,其中 D-B 和 D-T 的权值最小,任选其中的一个,例如选择 D-B 组成最小生成树,将顶点 B 从 B 类移到 A 类,A = {S, A, C, D, B},B = {T}。

    在这里插入图片描述

    图 5 D-B 边组成最小生成树

    1. 从 A 类中的 S、A、C、D、B 顶点出发,到达 B 类顶点的边有 B-T、D-T,其中 D-T 的权值最小,选择 D-T 组成最小生成树,将顶点 T 从 B 类移到 A 类,A = {S, A, C, D, B, T},B = {}。

    在这里插入图片描述

    图 6 D-T 边组成最小生成树

    1. 由于 B 类中的顶点全部移到了 A 类,因此 S-A、A-C、C-D、D-B、D-T 组成的是一个生成树,而且是一个最小生成树,它的总权值为 17。

    在这里插入图片描述

    图 7 最小生成树

    普里姆算法的具体实现

    接下来,我们将给出实现普里姆算法的 C、Java、Python 程序,程序中有详尽的注释,您可以借助编译器一边运行程序一边观察程序的执行过程,彻底搞清楚普里姆算法是如何找到最小生成树的。

    如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 C 语言程序:

    #include<stdio.h>
    #define V 6    // 记录图中顶点的个数
    typedef enum { false, true } bool;
    //查找权值最小的、尚未被选择的顶点,key 数组记录了各顶点之间的权值数据,visited数组记录着各个顶点是否已经被选择的信息
    int min_Key(int key[], bool visited[])
    {
        int min = 2147483647, min_index;  //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
        //遍历 key 数组
        for (int v = 0; v < V; v++) {
            //如果当前顶点为被选择,且对应的权值小于 min 值
            if (visited[v] == false && key[v] < min) {
                //更新  min 的值并记录该顶点的位置
                min = key[v];
                min_index = v;
            }
        }
        //返回最小权值的顶点的位置
        return min_index;
    }
    //输出最小生成树
    void print_MST(int parent[], int cost[V][V])
    {
        int minCost = 0;
        printf("最小生成树为:\n");
        //遍历 parent 数组
        for (int i = 1; i < V; i++) {
            //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
            printf("%d - %d wight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
            //统计最小生成树的总权值
            minCost += cost[i][parent[i]];
        }
        printf("总权值为:%d", minCost);
    }
    //根据用户提供了图的信息(存储在 cost 数组中),寻找最小生成树
    void find_MST(int cost[V][V])
    {    //key 数组用于记录 B 类顶点到 A 类顶点的权值
        //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
        //visited 数组用于记录各个顶点属于 A 类还是 B 类
        int parent[V], key[V];
        bool visited[V];
        // 初始化 3 个数组
        for (int i = 0; i < V; i++) {
            key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
            visited[i] = false;     // 所有的顶点全部属于 B 类
            parent[i] = -1;         // 所有顶点都没有父节点
        }
        // 选择 key 数组中第一个顶点,开始寻找最小生成树
        key[0] = 0;  // 该顶点对应的权值设为 0
        parent[0] = -1; // 该顶点没有父节点
        // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
        for (int x = 0; x < V - 1; x++)
        {
            // 从 key 数组中找到权值最小的顶点所在的位置
            int u = min_Key(key, visited);
            // 该顶点划分到 A 类
            visited[u] = true;
            // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
            for (int v = 0; v < V; v++)
            {
                // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
                if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
                {
                    // 更新 parent 数组记录的各个顶点父节点的信息
                    parent[v] = u;
                    // 更新 key 数组
                    key[v] = cost[u][v];
                }
            }
        }
        //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
        print_MST(parent, cost);
    }
    // main function
    int main()
    {
        int p1, p2;
        int wight;
        int cost[V][V] = { 0 };
        printf("输入图(顶点到顶点的路径和权值):\n");
        while (1) {
            scanf("%d %d", &p1, &p2);
            //如果用户输入 -1 -1,表示输入结束
            if (p1 == -1 && p2 == -1) {
                break;
            }
            scanf("%d", &wight);
            cost[p1 - 1][p2 - 1] = wight;
            cost[p2 - 1][p1 - 1] = wight;
        }
        // 根据用户输入的图的信息,寻找最小生成树
        find_MST(cost);
        return 0;
    }
    

    如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Java 程序:

    import java.util.Scanner;
    public class prim {
        static int V = 6;
        public static int min_Key(int []key,boolean []visited) {
            //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
            int min = 2147483647,min_index = 0;
            //遍历 key 数组
            for (int v = 0; v < V; v++) {
                //如果当前顶点为被选择,且对应的权值小于 min 值
                if (visited[v] == false && key[v] < min) {
                    //更新  min 的值并记录该顶点的位置
                    min = key[v];
                    min_index = v;
                }
            }
            //返回最小权值的顶点的位置
            return min_index;  
        }
      
        public static void print_MST(int []parent, int [][]cost) {
            int minCost = 0;
            System.out.println("最小生成树为:");
            //遍历 parent 数组
            for (int i = 1; i < V; i++) {
                //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
                System.out.println((parent[i]+1)+" - "+(i+1)+" wight:"+cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
                //统计最小生成树的总权值
                minCost += cost[i][parent[i]];
            }
            System.out.print("总权值为:"+minCost);
        }
        public static void find_MST(int [][]cost) {
            //key 数组用于记录 B 类顶点到 A 类顶点的权值
            //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
            //visited 数组用于记录各个顶点属于 A 类还是 B 类
            int []parent = new int[V];
            int []key = new int[V];
            boolean []visited=new boolean[V];
            // 初始化 3 个数组
            for (int i = 0; i < V; i++) {
                key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
                visited[i] = false;     // 所有的顶点全部属于 B 类
                parent[i] = -1;         // 所有顶点都没有父节点
            }
            // 选择 key 数组中第一个顶点,开始寻找最小生成树
            key[0] = 0;  // 该顶点对应的权值设为 0
            parent[0] = -1; // 该顶点没有父节点
            // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
            for (int x = 0; x < V - 1; x++)
            {
                // 从 key 数组中找到权值最小的顶点所在的位置
                int u = min_Key(key, visited);
                // 该顶点划分到 A 类
                visited[u] = true;
                // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
                for (int v = 0; v < V; v++)
                {
                    // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
                    if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
                    {
                        // 更新 parent 数组记录的各个顶点父节点的信息
                        parent[v] = u;
                        // 更新 key 数组
                        key[v] = cost[u][v];
                    }
                }
            }
            //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
            print_MST(parent, cost);
        }
        public static void main(String[] args) {
            int [][]cost = new int[V][V];
            System.out.println("输入图(顶点到顶点的路径和权值):");
            Scanner sc = new Scanner(System.in);
            while (true) {
                int p1 = sc.nextInt();
                int p2 = sc.nextInt();
              //  System.out.println(p1+p2);
                if (p1 == -1 && p2 == -1) {
                    break;
                }
                int wight = sc.nextInt();
                cost[p1-1][p2-1] = wight;
                cost[p2-1][p1-1] = wight;
            }
            // 根据用户输入的图的信息,寻找最小生成树
            find_MST(cost);
        }
    }
    

    如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Python 程序:

    V = 6     #图中顶点的个数
    cost = [[0]*V for i in range(V)]
    print("输入图(顶点到顶点的路径和权值):")
    while True:
        li = input().split()
      
        p1 = int(li[0])
        p2 = int(li[1])
        if p1 == -1 and p2 == -1:
            break
        wight = int(li[2])
        cost[p1-1][p2-1] = wight
        cost[p2-1][p1-1] = wight
    #查找权值最小的、尚未被选择的顶点,key 列表记录了各顶点之间的权值数据,visited列表记录着各个顶点是否已经被选择的信息
    def min_Key(key,visited):
        #遍历 key 列表使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
        min = float('inf')
        min_index = 0
        #遍历 key 列表
        for v in range(V):
            #如果当前顶点为被选择,且对应的权值小于 min 值
            if visited[v] == False and key[v]<min:
                #更新  min 的值并记录该顶点的位置
                min = key[v]
                min_index=v
        #返回最小权值的顶点的位置
        return min_index
    #输出最小生成树
    def print_MST(parent,cost):
        minCost=0
        print("最小生成树为:")
        #遍历 parent 列表
        for i in range(1,V):
            #parent 列表下标值表示各个顶点,各个下标对应的值为该顶点的父节点
            print("%d - %d wight:%d"%(parent[i]+1, i+1, cost[i][parent[i]]))
            #统计最小生成树的总权值
            minCost = minCost + cost[i][parent[i]];
        print("总权值为:%d"%(minCost))
    #根据用户提供了图的信息(存储在 cost 列表中),寻找最小生成树
    def find_MST(cost):
        #key 列表用于记录 B 类顶点到 A 类顶点的权值
        #parent 列表用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
        #visited 列表用于记录各个顶点属于 A 类还是 B 类
        parent = [-1]*V
        key = [float('inf')]*V
        visited = [False]*V
        # 选择 key 列表中第一个顶点,开始寻找最小生成树
        key[0] = 0
        parent[0]= -1
        # 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
        for x in range(V-1):
            # 从 key 列表中找到权值最小的顶点所在的位置
            u = min_Key(key,visited)
            visited[u] = True
            # 由于新顶点加入 A 类,因此需要更新 key 列表中的数据
            for v in range(V):
                # 如果类 B 中存在到下标为 u 的顶点的权值比 key 列表中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
                if cost[u][v] !=0 and visited[v] == False and cost[u][v] < key[v]:
                    # 更新 parent 列表记录的各个顶点父节点的信息
                    parent[v] = u
                    # 更新 key 列表
                    key[v] = cost[u][v]
        # 根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
        print_MST(parent,cost);
    find_MST(cost)
    

    图 1 连通网中的顶点 A、B、C、D、S、T 分别用 1~6 的数字表示,上面程序的运行结果均为:

    输入图(顶点到顶点的路径和权值):
    1 5 7
    1 3 3
    5 3 8
    1 2 6
    2 3 4
    2 4 2
    3 4 3
    2 6 5
    4 6 2
    -1 -1
    最小生成树为:
    4 - 2 wight:2
    1 - 3 wight:3
    3 - 4 wight:3
    1 - 5 wight:7
    4 - 6 wight:2
    总权值为:17

    展开全文
  • 最小生成树之普里姆算法
  • 数据结构课程设计 设计说明书 最小生成树普里姆算法的实现 学生姓名 学 号 班 级 成 绩 指导教师 数学与计算机科学学院 2013年3月15日 课程设计任务书 20122013学年第二学期 课程设计名称 数据结构课程设计 课程设计...
  • 求最小生成树的prim算法的C语言简单实现
  • PAGE 2 数据结构课程设计 设计说明书 最小生成树普里姆算法的实现 学生姓名 学号 班级 计本 成绩 指导教师 计算机科学与技术系 数据结构 课程设计评阅书 题目 最小生成树普里姆算法的实现 学生姓名 学号 指导教师...
  • 迪杰斯特拉算法(Dijkstra)

    迪克斯特拉算法        

            迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。

    普里姆算法

            普里姆算法,图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

    #include <stdio.h>
    #include <malloc.h>
    
    #define MAX_DISTANCE 1000
    
    typedef struct Net{ //图的定义
    	int** weights;
    	int numNodes;
    } *NetPtr;
    
    NetPtr initNet(int paraSize, int** paraData) { //图的初始化   
    	int i, j;
    	NetPtr resultPtr = (NetPtr)malloc(sizeof(Net));	
    	resultPtr -> numNodes = paraSize;
    
    	resultPtr->weights = (int**)malloc(paraSize * sizeof(int*));
    	for (i = 0; i < paraSize; i ++) {
    		resultPtr -> weights[i] = (int*)malloc(paraSize * sizeof(int));
    		for (j = 0; j < paraSize; j ++) {
    			resultPtr -> weights[i][j] = paraData[i][j];
    		}
    	}
    	
    	return resultPtr;
    }
    
    
    int dijkstraOrPrim(NetPtr paraPtr, int paraAlgorithm) {   //算法
    	int i, j, minDistance, tempBestNode, resultCost;
    	int source = 0;
    	int numNodes = paraPtr->numNodes;
    	int *distanceArray = (int*)malloc(numNodes * sizeof(int)); //申请空间
    	int *parentArray = (int*)malloc(numNodes * sizeof(int)); //申请空间
    	int *visitedArray = (int*)malloc(numNodes * sizeof(int));  //申请空间
    
    	for (i = 0; i < numNodes; i++) {
    		distanceArray[i] = paraPtr->weights[source][i]; //赋权值
    		parentArray[i] = source;
    		visitedArray[i] = 0;
    	}
    	distanceArray[source] = 0; //距离为0
    	parentArray[source] = -1; //父母为-1 没有父母
    	visitedArray[source] = 1; //已经见过了 ture
    
    	tempBestNode = -1;
    	for (i = 0; i < numNodes - 1; i++) {
    		minDistance = MAX_DISTANCE;  //找距离最小的,先把距离拉成最大
    		for (j = 0; j < numNodes; j++) {
    			if (visitedArray[j]) {
    				continue;  //拜访过了,直接continue
    			}
    
    			if (minDistance > distanceArray[j]) {
    				minDistance = distanceArray[j]; //找到最小的
    				tempBestNode = j;
    			} 
    		}
    
    		visitedArray[tempBestNode] = 1;  //拜访过了
    
    		for (j = 0; j < numNodes; j++) {
    			if (visitedArray[j]) {
    				continue;
    			}
    
    			if (paraPtr->weights[tempBestNode][j] >= MAX_DISTANCE) {   //距离大,应该不会
    				continue;
    			}
    
    			if (paraAlgorithm == 0) {
    				if (distanceArray[j] > distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j]) { //迪克斯特拉算法
    					distanceArray[j] = distanceArray[tempBestNode] + paraPtr->weights[tempBestNode][j];
    					parentArray[j] = tempBestNode;
    				}
    			} else {
    				if (distanceArray[j] > paraPtr->weights[tempBestNode][j]) { //普里姆算法
    					distanceArray[j] = paraPtr->weights[tempBestNode][j];
    					parentArray[j] = tempBestNode;
    				}
    			}
    		}
    	}
    
    	printf("the parent of each node: ");
    	for (i = 0; i < numNodes; i++) {
    		printf("%d, ", parentArray[i]);
    	}
    
    	if (paraAlgorithm == 0) {
    		printf("\nFrom node 0, path length to all nodes are: ");
    		for (i = 0; i < numNodes; i++) {
    			printf("%d (%d), ", i, distanceArray[i]);
    		}
    	} else {
    		resultCost = 0;
    		for (i = 0; i < numNodes; i++) {
    			resultCost += distanceArray[i];
    			printf("\r\ncost of node %d is %d, total = %d", i, distanceArray[i], resultCost);
    		}
    		printf("\nFinally, the total cost is %d.\r\n ", resultCost);
    	}
    	
    	printf("\r\n");
    
    	return resultCost;
    }
    
    
    
    
    NetPtr constructSampleNet() {
    	int i, j;
    	int myGraph[6][6] = { 
    		{0, 6, 1, 5, 0, 0},
    		{6, 0, 5, 0, 3, 0}, 
    		{1, 5, 0, 5, 6, 4}, 
    		{5, 0, 5, 0, 0, 2}, 
    		{0, 3, 6, 0, 0, 6},
    		{0, 0, 4, 2, 6, 0}};
    	int** tempPtr;
    	int numNodes = 6;
    	printf("Preparing data\r\n");
    		
    	tempPtr = (int**)malloc(numNodes * sizeof(int*));
    	for (i = 0; i < numNodes; i ++) {
    		tempPtr[i] = (int*)malloc(numNodes * sizeof(int));
    	}
    	 
    	for (i = 0; i < numNodes; i ++) {
    		for (j = 0; j < numNodes; j ++) {
    			if (myGraph[i][j] == 0) {
    				tempPtr[i][j] = MAX_DISTANCE;
    			} else {
    				tempPtr[i][j] = myGraph[i][j];
    			}
    		}
    	}
     
    	printf("Data ready\r\n");
    	
    	NetPtr resultNetPtr = initNet(numNodes, tempPtr);
    	return resultNetPtr;
    }
    
    void testPrim() {
    	NetPtr tempNetPtr = constructSampleNet();
    	printf("=====Dijkstra algorithm=====\r\n");
    	dijkstraOrPrim(tempNetPtr, 0);
    	printf("=====Prim algorithm=====\r\n");
    	dijkstraOrPrim(tempNetPtr, 1);
    }
    
    int main(){
    	testPrim();
    	return 1;
    }

    运算结果:

    Preparing data
    Data ready
    =====Dijkstra algorithm=====
    the parent of each node: -1, 0, 0, 0, 2, 2,
    From node 0, path length to all nodes are: 0 (0), 1 (6), 2 (1), 3 (5), 4 (7), 5 (5),
    =====Prim algorithm=====
    the parent of each node: -1, 2, 0, 5, 1, 2,
    cost of node 0 is 0, total = 0
    cost of node 1 is 5, total = 5
    cost of node 2 is 1, total = 6
    cost of node 3 is 2, total = 8
    cost of node 4 is 3, total = 11
    cost of node 5 is 4, total = 15
    Finally, the total cost is 15.
    

    原本的图:

     Prim算法:

     Dijkstra 算法:

     完毕;

    展开全文
  • 普里姆算法详解

    千次阅读 2020-08-13 12:26:58
    普里姆算法介绍 1)普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出只有(n-1)条边包含所有n个顶点的连通子图,也就是所谓的极小连通子图 2)普利姆的算法如下: (1)设G=(V,E)是连通网,T=(U,D)是...
  • JINGCHU UNIVERSITY OF TECHNOLOG Y 数据结构C语言描述? 课程设计 学 院 计算机工程学院 班 级 12级软件技术1班 学 号 2012304040122 120 124133121 学生姓名 周鑫王彬彬李松平 张圣玮魏远迎 扌指导教师 余云霞 2014...
  • 普里姆算法(prim)

    2021-10-23 11:59:36
    普里姆算法求最小生成树: 算法思路: 先从图中任选一个顶点并做标记,再比较与该顶点直接连接的所有顶点的权值,从中挑选最小权值相连,并将该顶点做标记,得到第一条路径。再从已标记的顶点的所有直接相连顶点且...
  • 最小生成树问题的概念—普里姆算法是从点的角度来解决。若在解决问题过程中需要遍历图的所有点,则普里姆算法更好。 基本思想: 普里姆算法更像构建一棵树。联想我们构建二叉树的过程,从根节点出发,构建左右子树,...
  • 而Prim算法就是构造最小生成树的一种算法。定义:假设N = (P,{E})是连通网,TE是N上最小生成树中边的集合。算法从U = {U0}(U0属于V)。开始重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找到一条代价...
  • 克鲁斯卡尔算法:【1】克鲁斯卡尔算法普里姆算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树。克鲁斯卡尔算法是直接以边为目标去构建。因为权值是在边上,直接去找最小权值的边来构建生成树也是...
  • 6)求最小生成树的算法主要是普里姆算法和克鲁卡尔算法。 三,基本介绍 普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找到只有(n - 1)条包含所有n个顶点的连通图,也就是所谓的极小连通子图 四,...
  • 普里姆算法学习(Java)

    2021-02-01 15:35:17
    普里姆算法学习(Java) 学习视频:尚硅谷韩老师java讲解数据结构和算法 一、应用场景-修路问题 1.1、看一个应用场景和问题: 有胜利乡有 7 个村庄(A, B, C, D, E, F, G) ,现在需要修路把 7 个村庄连通 各个村庄的...
  • 前言需求今天我们学习的是普里姆算法,我们还是从一个场景里引入看看有7个村庄(A, B, C, D, E, F, G) ,现在需要修路把7个村庄连通1.各个村庄的距离用边线表示(权) ,比如 A – B 距离 5公里2.问如何修路保证各个...
  • 深度学习普里姆算法(Prim)

    千次阅读 多人点赞 2020-04-21 10:36:02
    如果你对数据结构了解不深,又想要学习普里姆算法,建议你看看我这篇,我尽量往细致的方向写,如果有些大佬认为我写的比较啰嗦,请见谅,毕竟我的目的是为了让数据结构小白能够在理解普里姆算法上相对容易一些。...
  • 最小生成树算法——普里姆算法

    千次阅读 2020-04-13 14:06:58
    普里姆算法 假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,U和TE的初始值为空。算法过程: 首先从V中任取一个顶点(假定v1),将它并入U中,此时U={v1} 然后...
  • Python详细实现普里姆算法 Python详细实现最小生成树
  • 普里姆算法求最小生成树与之前发的迪杰斯特拉算法求最小生成树的思想类似,都是用到一个dis数组,不过与迪杰斯特拉算法不同的是,之前迪杰斯特拉算法求最短路里dis存储的是源点到各点的最短路,每次循环找离源点最近...
  • 第六章图-算法6.8普里姆算法 代码实现 #pragma once #include <iostream> using namespace std; //图的邻接矩阵存储(创建无向图) //表示极大值 #define MaxInt 32767 //最大顶点数 #define MVNum 100 //...
  • 普里姆算法(Prim) 思路步骤: 1、从顶点开始出发,选择权重最小的边连接。 2、连接完新的顶点后继续找最小权重边,与已经连接的全部顶点所连接的边都要对比。 3、连接后判断是否形成环,形成的...
  • 克鲁斯卡尔算法(Kruskal): 设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个...普里姆算法是另一种构造最小生成树的算法,它是按逐个将顶点连通的方式来构造最小生成树的。 从连通网络 N = { V, E }中的某

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,119
精华内容 2,047
关键字:

普里姆算法

友情链接: chick.rar