prim算法 订阅
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。 展开全文
普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。
信息
提出时间
1930年
别    称
最小生成树算法
提出者
沃伊捷赫·亚尔尼克(Vojtěch Jarník)
应用学科
计算机,数据结构,数学(图论)
中文名
普里姆算法
适用领域范围
应用图论知识的实际问题
算    法
贪心
外文名
Prim Algorithm
Prim算法描述
1).输入:一个加权连通图,其中顶点集合为V,边集合为E;2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;3).重复下列操作,直到Vnew = V:a.在集合E中选取权值最小的边,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);b.将v加入集合Vnew中,将边加入集合Enew中;4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。
收起全文
精华内容
下载资源
问答
  • Prim算法
    2021-04-21 08:45:52

    该楼层疑似违规已被系统折叠 隐藏此楼查看此楼

    A.Prim算法:

    procedure prim(v0:integer);

    var

    lowcost,closest:array[1..maxn] of integer;

    i,j,k,min:integer;

    begin

    for i:=1 to n do

    begin

    lowcost:=cost[v0,i];

    closest:=v0;

    end;

    for i:=1 to n-1 do

    begin

    {寻找离生成树最近的未加入顶点k}

    min:=maxlongint;

    for j:=1 to n do

    if (lowcost[j]< min) and (lowcost[j]< >0) then

    begin

    min:=lowcost[j];

    k:=j;

    end;

    lowcost[k]:=0; {将顶点k加入生成树}

    {生成树中增加一条新的边k到closest[k]}

    {修正各点的lowcost和closest值}

    for j:=1 to n do

    if cost[k,j]< lwocost[j] then

    begin

    lowcost[j]:=cost[k,j];

    closest[j]:=k;

    end;

    end;

    end;{prim}

    更多相关内容
  • Prim算法与Dijkstra的最短路径算法类似,它采用贪心策略。算法开始先把图中权值最小的边添加到树T中,然后不断把权值最小的边E(E的一个端点在T中,另一个在G-T中)。当没有符合条件的E时算法结束,此时T就是G的一个...
  • 主要讲解了普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树,需要的朋友可以参考下
  • Prim算法计算最小生成树(无向图&邻接矩阵)——C语言实现。
  • 主要介绍了C++使用Kruskal和Prim算法实现最小生成树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 恋情申道友优先肯prim算法随机生成迷宫,有自动寻路功能,做了界面,需要easyX库的支持
  • 用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
  • 基于matlab的最小生成树的prim算法,有详细的解释,可直接运行
  • 之前都是看书,大部分也是c++的实现,但是搞前端不能忘了JS啊,所以JS实现一遍这两个经典的最小生成树算法。 一、权重图和最小生成树 权重图:图的边带权重 最小生成树:在连通图的所有生成树中,所有边的权重和...
  • 本代码利用c#语言,实现了基于Prim算法实现最小生成树的可视化界面。用户可以自己输入点以及边的权值,计算出最小生成树。
  • 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。 最小生成树可以用kruskal(克鲁斯卡尔)算法prim(普里姆)算法求出。
  • prim算法

    千次阅读 2021-01-22 18:10:06
    prim算法 prim算法(普利姆算法):对图G(V,E)设置集合S,存放已访问的顶点,然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为中介点,优化所有从u能到达的顶点v与...

    prim算法

    prim算法(普利姆算法):对图G(V,E)设置集合S,存放已访问的顶点,然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u),访问并加入集合S。之后,令顶点u为中介点,优化所有从u能到达的顶点v与集合S之间的最短距离。执行n次(n为顶点个数),直到集合S已包含所有顶点。

    算法实例演示

    首先让我们来看一个example。如下图所示,图a是一个连通图(右图是图a对应的邻接矩阵,假设图中的边的权值大于0),我们现在基于该图来演示Prim算法的过程。
    在这里插入图片描述
    在这里插入图片描述
    我们选择一个起点,然后在与起点相连且未被选的节点中选择一个权值最小的节点,将该节点与其相连边添加入生成树。假设起点是0节点,与0节点相连且未被选的节点是{1,2,3},分别对应的权值是{6,1,5},可见当前最小的权值1,权值最小的节点就是2节点,所以将2节点和0-2的边添加入生成树,如图b所示。
    在这里插入图片描述
    接着我们在与已选节点相连且未被选的节点中选择一个权值最小的节点,将该节点与其相连边添加入生成树。当前已选节点是0,2节点,与已选节点相连且未被选的节点有{1,3,4,5},分别对应的权值是{(6,5),(5,5),6,4,},可见当前最小的权值4,权值最小的节点就是5节点,所以将5节点和2-5的边添加入生成树,如图c所示。(其实在编程时,我们只需记录与更新当前较小的那个权值,如与{1,3,4,5}对应的权值我们只需记录{5,5,6,4},当然我们也需利用了另一个数组来加以区别当前权值对应的连接点,如当前权值{5,5,6,4}所对应的连接点就是{2,0,2,2})
    在这里插入图片描述
    接着我们继续在与已选节点相连且未被选的节点中选择一个权值最小的节点,将该节点与其相连边添加入生成树。当前已选节点是0,2,5节点,与已选节点相连且未被选的节点有{1,3,4},分别对应的权值是{(6,5),(2,5,5),(6,6),}(其实当前我们可只记录{5,2,6},同时记录其对应的连接点分别是{2,5,2}),可见当前最小的权值2,权值最小的节点就是3节点,所以将3节点和5-3的边添加入生成树,如图d所示。
    在这里插入图片描述
    接着我们依照上一次的步骤继续在与已选节点相连且未被选的节点中选择一个权值最小的节点,将该节点与其相连边添加入生成树。如图e,f所示。最终图f就是我们通过Prim算法得到的最小生成树了。
    在这里插入图片描述在这里插入图片描述
    prim算法基本思想:对图G(V,E)设置集合S来存放已被访问的顶点,然后执行n次下面的两个步骤(n为顶点个数)

    1. 每次从集合V-S中选择与集合S最近的一个顶点(记为u),访问u并将其加入集合S,同时把这条离集合S最近的边加入最小生成树。
    2. 令顶点u作为集合S与集合V-S连接的接口,优化从u能到达的未访问顶点v与集合S的最短距离

    prim算法的具体实现

    1. 集合S的实现方法:使用一个bool型数组vis[]表示顶点是否已被访问。其中vis[i]==true表示顶点Vi已被访问,vis[i]==false则表示顶点Vi未被访问。
    2. 不妨令int型数组d[]来存放顶点Vi(0<=i<=n-1)与集合S的最短距离。初始时除了起点s的d[s]赋为0,其余顶点都赋为一个很大的数来表示INF,即不可达。

    prim算法与Dijkstra算法区别:
    Dijkstra算法的数组d[]含义为起点s达到顶点Vi的最短距离。
    prim算法的数组d[]含义为顶点Vi与集合S的最短距离

    prim算法伪代码

    Prim(G, d[])
    {
    	初始化;
    	for(循环n次)
    	{
    		u = 使d[u]最小的还未被访问的顶点的标号;
    		记u已被访问;
    		for(从u出发能到达的所有顶点v)
    		{
    			if(v未被访问 && 以u为中介点使得v与集合S的最短距离d[v]更优)
    			{
    				将G[u][v]赋值给v与集合S的最短距离d[v];
    			}
    		}
    	}
    }
    

    Dijkstra算法和prim算法实际上是相同思路,数组d[]含义不同。

    定义MAXV为最大顶点数,INF为一个很大的数字

    const int MAXV = 1000; //最大顶点数
    const int INF = 100000000; //设INF为一个很大的数
    
    1. 邻接矩阵版
    int n, G[MAXV][MAXV]; //n为顶点数,MAXV为最大顶点数
    int d[MAXV]; //顶点与集合S的最短距离
    bool vis[MAXV] = {false}; //标记数组,vis[i] == true表示访问。初值均为false
    intprim() //默认0号为初始点,函数返回最小生成树的边权之和
    {
    	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
    	d[0] = 0; //只有0号顶点到集合S的距离为0,其余全是INF
    	int ans = 0; //存放最小生成树的边权之和
    	for(int i = 0; i < n; i++) //循环n次
    	{
    		int u = -1, MIN = INF; //u使d[u]最小,MIN存放该最小的d[u]
    		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
    		{
    			if(vis[j] == false && d[j] < MIN)
    			{
    				u = j;
    				MIN = d[j];
    			}
    		}
    		//找不到小于INF的d[u],则剩下的顶点和集合S不连通
    		if(u == -1)
    			return -1;
    		vis[u] = true; //标记u为已访问
    		ans += d[u]; //将与集合S距离最小的边加入最小生成树
    		for(int v = 0; v < n; v++)
    		{
    		    //v未访问 && u能到达v && 以u为中介点可以使v离集合S更近
    			if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v])
    			{
    				d[v] = G[u][v]; //将G[u][v]赋值给d[v]
    			}
    		}
    	}
    	return ans; //返回最小生成树的边权之和
    }
    
    1. 邻接表版
    struct Node
    {
    	int v, dis; //v为边的目标顶点,dis为边权
    };
    vector<Node> Adj[MAXV]; //图G,Adj[u]存放从顶点u出发可以到达的所有顶点
    int n; //n为顶点数,图G使用邻接表实现,MAXV为最大顶点数
    int d[MAXV]; //顶点与集合S的最短距离
    bool vis[MAXV] = {false}; //标记数组,vis[i] == true表示已访问。初值均为false
    
    int prim() //默认0号为初始点,函数返回最小生成树的边权之和
    {
    	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
    	d[0] = 0; //只有0号顶点到集合S的距离为0,其余全是INF
    	int ans = 0; //存放最小生成树的边权之和
    	for(int i = 0; i < n; i++) //循环n次
    	{
    		int u = -1, MIN = INF; //u使d[u]最小,MIN存放该最小的d[u]
    		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
    		{
    			if(vis[j] == false && d[j] < MIN)
    			{
    				u = j;
    				MIN = d[j];
    			}
    		}
    		//找不到小于INF的d[u],则剩下的顶点和集合S不连通
    		if(u == -1)
    			return -1;
    		vis[u] = true; //标记u为已访问
    		ans += d[u]; //将与集合S距离最小的边加入最小生成树
    		//只有下面这个for与邻接矩阵的写法不同
    		for(int j = 0; j < Adj[u].size(); j++)
    		{
    			int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
    			if(vis[v] == false && Adj[u][j].dis < d[v])
    			{
    			    //如果v未访问 && 以u为中介点可以使v离集合S更近
    				d[v] = Adj[u][j].dis;
    			}
    		}
    	}
    	return ans; //返回最小生成树的边权之和
    }
    

    例题

    求最小生成树
    在这里插入图片描述
    从V0开始,依次找到各顶点边权最小的,然后相连
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int MAXV = 1000; //最大顶点数
    const int INF = 1000000000; //设INF为一个很大的数
    
    int n, m, G[MAXV][MAXV]; //n为顶点数,MAXV为最大顶点数
    int d[MAXV]; //顶点与集合S的最短距离
    bool vis[MAXV] = {false}; //标记数组,vis[i]==true表示已访问。初值均为false
    
    int prim() //默认0号为初始点,函数返回最小生成树的边权之和
    {
    	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
    	d[0] = 0; //只有0号顶点到集合S的距离为0,其余全是INF
    	int ans = 0; //存放最小生成树的边权之和
    	for(int i = 0; i < n; i++) //循环n次
    	{
    		int u = -1, MIN = INF; //u使d[u]最小,MIN存放该最小的d[u]
    		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
    		{
    			if(vis[j] == false && d[j] < MIN)
    			{
    				u = j;
    				MIN = d[j];
    			}
    		}
    		//找不到小于INF的d[u],则剩下的顶点和集合S不连通
    		if(u == -1)
    			return -1;
    		vis[u] = true; //标记u为已访问
    		ans += d[u]; //将与集合S距离最小的边加入最小生成树
    		for(int v = 0; v < n; v++)
    		{
    			//v未访问 && u能到达v && 以u为中介点可以使v离集合S更近
    			if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v])
    			{
    				d[v] = G[u][v]; //将G[u][v]赋值给d[v]
    			}
    		}
    	}
    	return ans; //返回最小生成树的边权之和
    }
    
    int main()
    {
    	int u, v, w;
    	scanf("%d%d", &n, &m); //顶点个数、边数
    	fill(G[0], G[0] + MAXV * MAXV, INF); //初始化图G
    	for(int i = 0; i < m; i++)
    	{
    		scanf("%d%d%d", &u, &v, &w); //输入u,v以及边权
    		G[u][v] = G[v][u] = w; //无向图
    	}
    	int ans = prim(); //prim算法入口
    	printf("%d\n", ans);
    	return 0;
    }
    
    //输入数据
    6 10 //6个顶点,10条边,以下10行10边
    0 1 4 //边0->1与1->0的边权为4,下同
    0 4 1
    0 5 2
    1 2 6
    1 5 3
    2 3 6
    2 5 5
    3 4 4
    3 5 5
    4 5 3
    
    //输出结果
    15
    
    展开全文
  • 标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现,纯手写!下载后如有疑问可以私信联系!全部手撸,一键运行,都封装成函数了,易读性很强
  • 输入矩阵是边加权矩阵,未连接的边被指定为 0 >>A = [0 192 344 0 0 0 0 0 0 0 0; 192 0 309 0 555 0 0 0 0 0 0; 344 309 0 499 0 0 0 0 0 0 0; 0 0 499 0 840 0 229 286 0 0 0; 0 555 0 840 0 237 0 0 0 0 0;...
  • Prim算法(数据结构)

    2013-12-17 16:31:55
    最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树)... 为了得到最小生成树,人们设计了很多算法,最著名的有prim算法和kruskal算法。
  • NULL 博文链接:https://128kj.iteye.com/blog/1705936
  • NULL 博文链接:https://128kj.iteye.com/blog/1667993
  • 算法设计与分析——prim算法

    千次阅读 2020-05-28 15:44:51
    最小生成树算法、prime算法、JavaScript算法(后续更新嘿嘿)、C语言算法算法导论、算法设计与分析

    前言

    在上一篇文章中,我们聊了聊KMP算法,一个极其高效但又非常难以理解(个人看来)的算法,如果有朋友想要深度讨论,欢迎私信。
    本篇我们来聊聊prim算法,我最早接触prim算法已经记不清是数据结构课中还是离散数学课中了,但即便科目不同,prim算法还是那个prim算法。
    prim算法是一种用于在连通图中获取最小生成树的算法同样用于获取最小生成树的算法还有Kruskal算法(大家有兴趣同样可以了解了解,但其实二者是比较相似的),prim算法属于贪心算法的一种,至于为什么,或许在分析其过程的时候大家就明白了。
    要理解prim算法,大家首先要理解好什么是连通图?什么是最小生成树?这里我们来简单介绍一下,因为这不是我们本次的重点(如果已经有基础的朋友,可以适当跳过)。

    • 什么是连通图?,首先理解什么是图?(这里面的学问其实有点大,所以我说咱们就是简单介绍下哈,本篇文章还是对有基础的朋友较友好,因为对于有基础的朋友,我可能是在废话哈哈哈)简单来说,平面内许多点通过一些路径相互连接(不一定要全部连接),就构成了一个图,而根据这些点之间的路径是否有方向,又分为了无向图和有向图。如下图,分别是一种无向图和有向图。
      无向图和有向图
      那么?什么是连通图呢?简单来说(只能简单来说了,说多了可以另起一篇文章。。。),就是图中的点通过图中的某些路径(带方向的就必须按照方向来)可以抵达任意一个点。最为简单的模型就是一个地区的许多村落之间的通信,如果每个村庄之间都可以达成通信,就是连通的。

    • 最小生成树是什么呢? 连通图中,每条路径都存在一个权值(理解为距离/成本也行吧,但其实不是这么理解的)。从该连通图出发,寻找一个路径数最少,但每个点之间都可达,就是一个生成树了(专业术语是连通无环子图)。生成树不止一个,而所以生成树中权值之和最小的生成树称为最小生成树。

    以上是对最小生成树的简单介绍,如果大家想详细了解一下,可查询资料,这些都不是我们本次的重点。如下给出《算法设计与分析基础》中生成树和最小生成树的定义。
    生成树和最小生成树定义
    如下为一些例子:
    在这里插入图片描述

    一、算法思想分析

    在简单讲解最小生成树的概念后,我们来聊聊prim算法的思想。前面提到过,prim算法是贪心算法的一种,而贪心算法,讲究的就是要极力满足当前最优,这个当前最优正是prim算法的核心思想。
    首先,prim算法中存在两个存储空间, 一个用来存放已加入最小生成树的顶点,而另外一个则用来存放还未加入最小生成树中的顶点。 当连通图中所有顶点已放入用于最小生成树的空间中,那么我们最小生成树算法结束!

    • 算法开始,起始顶点可随机找或指定一个。将起始顶点先放入已选顶点集合中
    • 未放入已选顶点集合中查找一条已选顶点集合中所有点最短(或者是权值最小,这里看自己理解了)的路径(说是一条线或许更合适吧)。刚开始的话,我们已选顶点集合只有一个点!而之后我们会将未加入的顶点一个一个加入已选顶点集合,所以这里的条件必须是已选顶点集合中所有点。显然,在我们找到的这条最短(权值最小)路径的两端的顶点,一个肯定属于还未加入最小生成树中的顶点,另一个肯定属于已加入最小生成树的顶点。将还未加入已选顶点集合的那个点,加入已选顶点集合,本轮任务完成。如果需要路径的,可以将路径记录保存下来。
    • 重复第二步,直到所有顶点已加入已选顶点集合,那么,我们的最小生成树就完成了。如果需要计算最小生成树的权值之和,在每一次找到最短路径的时候求一次和即可,需要具体路径的进行标记即可。

    接下来,我们举个栗子来做个示范:
    在这里插入图片描述
    2
    3
    4
    5
    6
    该例后续代码将会用到,大家可以自行看看该例。

    二、算法效率分析

    prim算法的具体效率,是与图的顶点和边数都是有关的。《算法设计与分析基础》中是这么分析的:
    prim算法分析
    以上是一种高级的分析,我们就简单来点吧。
    假设总共又n个顶点,那么我肯定有n次比较过程!而在第k次比较过程中,又有n-k个点和另外n-k个顶点相互比较,那么总结起来,那么算法复杂度几乎再n的立方级别。或许有朋友问了,这么算起来,好像也不是很高效哦?n³级别复杂度的确不是很高,但其实prim算法真正效率是介于n²和n³之间的,因为我们如上的分析是一种最坏的情况,就是每个点之间都存在一条路径。
    再者,相比于穷举法(也就是蛮力法)来查找最小生成树,prim算法已是大大提升了。《算法设计与分析基础》中这样写到:
    prim算法和穷举法比较

    三、算法代码

    C语言代码

    这里我们图的表示用邻接矩阵来表示,具体请看代码极其注释:

    /*最小生成树 prim算法 从一个连通图中获取一个最小生成树*/
    /*
    输入要求:输入一个连通图 存储模式:邻接矩阵表示 0表示不可达  点依次默认命名为a,b,c,d,e,f,g...
    例如:n*n数组
    6
    0 1 0 0 6 5
    1 0 1 0 0 4
    0 1 0 6 0 4
    0 0 6 0 8 5
    6 0 0 8 0 2
    5 4 4 5 2 0
    即为一种输入 实际上为上课讲解时的连通图表示
    输出要求: n-1长度数组 包含n-1条路径 ()表示的为m号点到k号点的那条路径 
    (1,2) (2,3) (2,6) (6,5) (6,4)
    最小生成树权值之和:1+1+4+5+2=13
    */
    #include<stdio.h>
    #define MAXN 1000
    /*二维数组存储 采用邻阶矩阵数据*/
    int input[MAXN][MAXN];
    int sign[MAXN]= {0}; // 标记sign数组 初始化全为0 ,1表示已经加入已选列表
    int prime(int n) {
    	int sum=0; // 最小生成树权值之和 初始值为0
    	/* 默认从第一个点开始 */
    	sign[1]=1;
    	int counter=1; // 计算当前状态已加入最小生成树队列的个数
    	
    	int flagX=-1,flagY=-1,minNodeValue=1000000;
    	while(counter!=n) {
    		flagX=-1,flagY=-1,minNodeValue=1000000; // 每一次都要初始化 
    		/* 每一次循环都是一次贪心 当前局势的一种最优解 */
    		for(int i=1; i<=n; i++) {
    			if(sign[i]==0) continue; // 如果当前为加入队列 直接下一次循环 其实这是一个笨方法
    			for(int j=1; j<=n; j++) {
    				// 在查找下一个连接点时 发现这个连接点已经在里面了(或者为0,即不可达) 我们直接跳过 我能说这是一个笨方法么?但似乎只能这样
    				if(sign[j]==1||input[i][j]==0) continue;
    				if(input[i][j]<minNodeValue){
    					// 更小的一个进行标记
    					flagX=i;
    					flagY=j;
    					minNodeValue=input[i][j]; 
    				}
    			}
    		}
    		
    		/* 一轮查找后 */
    			sign[flagY]=1; // 谁该标1 要清楚
    			counter++; // 找到加一 
    			sum+=input[flagX][flagY]; // 这里其实不用担心指针越界 如果是连通图 在一轮查找下来 肯定能找到一个最小的 
    			printf(" (%d,%d) ",flagX,flagY); // 其实我们都知道 flagX flagY 的位置 在这里顺序不重要 
    	}
    	return sum;
    }
    int main() {
    	/*作为输入的主函数*/
    	int n;
    	printf("请输入邻接矩阵的维度n:"); 
    	scanf("%d",&n);
    	printf("邻接矩阵:\n");
    	for(int i=1; i<=n; i++) {
    		for(int j=1; j<=n; j++) {
    			scanf("%d",&input[i][j]);
    		}
    	}
    	/*调用函数*/
    	int sum = prime(n);
    	printf("\n最小生成树权值之和:sum=%d\n",sum);
    }
    
    

    代码中有部分存在取巧,如果大家有任何建议都可私信或留言。

    后记

    经过一番分析,prim算法的效率似乎是接近n³的,可能偏离了大家的预期。但是一个算法的高效,不是在于它的算法复杂度是多少,而是在于这个算法和解决同样问题的其他算法,相比之下,这个算法是否高效。
    简而言之,高效算法是相对的,并不是绝对的。如果在解决最小生成树问题有其他算法比prim算法更为高效,那么那个算法也可以称之为高效算法。
    以上只是我的理解,如果大家有其他意见和想法,欢迎留言或私信。

    展开全文
  • 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

    展开全文
  • prim算法和Kruskal算法

    2021-12-26 18:46:31
    文章目录一、prim算法1.基本介绍2.应用场景——修路问题3.代码实现二、Kruskal算法1.基本介绍2.应用场景3.代码实现 一、prim算法 1.基本介绍 普利姆(Prim)算法求最小生成树,也就是在包含n个顶点的连通图中,找出...
  • Prim算法(java)

    2022-02-02 16:19:12
    一、Prim算法介绍   Prim(普利姆)算法是一种构造最小生成树的算法。Prim算法的时间复杂度为O(∣V∣2)O(|V|^2)O(∣V∣2),不依赖于EEE,因此它适用于求解边稠密的图的最小生成树。 二、Prim算法原理   (1)...
  • Prim算法 中文被称为普利姆算法,作为一种最小生成树的常见算法,与上节所介绍的KruskalKruskalKruskal算法存在的区别为: KruskalKruskalKruskal算法:将边权从小到大排序后选择作为两个树的连接边的边加入集合...
  • MATLAB源码集锦-最小生成树Prim算法代码
  • 基本图算法 陈嘉庆 最小生成树问题 最小生成树 1回便的 无向图 生成树1...算法prim普里姆)算法求出 最小生成树算法的目标:一个n个点的图, 选若干条边(一定是n-1条)使得图连在 起,并且所有选中的边的长度和最小 最小生

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,584
精华内容 13,033
关键字:

prim算法

友情链接: hc912prog18.zip