最小生成树算法之Prim算法
本文介绍了最小生成树的定义，Prim算法的实现步骤，通过简单举例实现了C语言编程。
1.什么是最小生成树算法？
简言之，就是给定一个具有n个顶点的加权的无相连通图，用n-1条边连接这n个顶点，并且使得连接之后的所有边的权值之和最小。这就叫最小生成树算法，最典型的两种算法就是Kruskal算法和本文要讲的Prim算法。
2.Prim算法的步骤是什么？
这就要涉及一些图论的知识了。
a.假定图的顶点集合为V，边集合为E.
b.初始化点集合U={u}.//u为V中的任意选定的一点
c.从u的邻接结点中选取一点v使这两点之间的权重最小,然后将v加入集合U中.
d.从结点v出发，重复c步骤，直到V={}.
3.举个例子来说明Prim算法的步骤：
一个简单的加权拓扑图如下所示
选取1为初始点，则按照上面所示的步骤访问结点的顺序依次次为：
则最终访问结点的顺序：1,3,4,2,5.
4.Prim算法的具体C语言编程实现：
#include <stdio.h>
#include <cstdlib>
#include<memory.h>
const int Max =0x7fffffff;
const int N=50;
int n;
int g[N][N],dis[N],visited[N];
int prim()
{
int i,j;
int pos,min;
int ans=0;
memset(visited,0,sizeof(visited));
visited[1]=1;pos=1;
//assign a value to the dis[N] first
for(i=2;i<=n;i++)
dis[i]=g[pos][i];
for(i=1;i<n;i++)
{
min=Max;
for(j=1;j<=n;j++)
{
if(visited[j]==0&&min>dis[j])
{
min=dis[j];
pos=j;
}
}
printf("The node being traversed is :%d\n",pos);
ans+=min;
printf("The value of ans is %d\n",ans);
//mark the node
visited[pos]=1;
//update the weight
for(j=1;j<=n;j++)
if(visited[j]==0&&dis[j]>g[pos][j])
dis[j]=g[pos][j];
}
return ans;
}
int main()
{
int i=1,j=1;
int ans=0;
int w;
printf("Please enter the number of the nodes:\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j)
g[i][j]=0;
else
g[i][j]=Max;
}
printf("Please enter the number of the edges:\n");
int edgenum;
scanf("%d",&edgenum);
int v1,v2;
printf("Please enter the number and the corresponding weight:\n");
for(i=1;i<=edgenum;i++)
{
scanf("%d%d%d",&v1,&v2,&w);
g[v1][v2]=g[v2][v1]=w;
}
ans=prim();
printf("The sum of the weight of the edges is:%d\n",ans);
system("pause");
return 0;
}
5.程序运行后的结果截图
以上就是本文的全部内容，希望对大家的学习有所帮助。
相关推荐
-
在SQL Server中实现最短路径搜索的解决方法
开始这是去年的问题了,今天在整理邮件的时候才发现这个问题,感觉顶有意思的,特记录下来. 在表RelationGraph中,有三个字段(ID,Node,RelatedNode),其中Node和RelatedNode两个字段描述两个节点的连接关系:现在要求,找出从节点"p"至节点"j",最短路径(即经过的节点最少). 图1. 解析: 了能够更好的描述表RelationGraph中字段Node和 RelatedNode的关系,我在这里特意使用一个图形来描述,如图2. 图2
-
最小生成树算法C语言代码实例
在贪婪算法这一章提到了最小生成树的一些算法,首先是Kruskal算法,实现如下: MST.h 复制代码 代码如下: #ifndef H_MST#define H_MST #define NODE node *#define G graph *#define MST edge ** /* the undirect graph start */typedef struct _node { char data; int flag; struct _node *parent;} node; typede
-
详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）
1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树 1.1 问题背景: 假设要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路.这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网.在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价.n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢? 1.2 分析问题(建立模型): 可以用连通网来表示n个城市以及n个城市间可能设置的通信线
-
c++查询最短路径示例
复制代码 代码如下: //shortest_path.c#include<stdio.h>#include<stdlib.h>//用file#include<string.h>//可用gets(),puts()#include"shortest_path.h"#define MAX 32767#define MENU "欢迎进入导航系统!\n==========菜单===========\n0.载入北外地图\n1.建立地图\n2.查询最短路
-
C#实现的最短路径分析
复制代码 代码如下: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static int length = 6; static string[] shortedPath = new string[length];
-
Java实现利用广度优先遍历(BFS)计算最短路径的方法
本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga
-
Dijkstra算法与Prim算法的异同案例详解
目录 Dijkstra简述 Prim简述 异 同 思想 时间复杂度 Dijkstra特例 Dijkstra简述 Dijkstra算法用于构建单源点的最短路径树(MST)--即树中某个点到任何其他点的距离都是最短的.例如,构建地图应用时查找自己的坐标离某个地标的最短距离.可以用于有向图,但是不能存在负权值(Bellman-Ford可以处理负权值). 伪代码 Dijkstra() { for each u in G,V { //此处做初始化操作,给每个节点u赋键值+∞,设置空为父节点 u.key =
-
Python 经典贪心算法之Prim算法案例详解
最小生成树的Prim算法也是贪心算法的一大经典应用.Prim算法的特点是时刻维护一棵树,算法不断加边,加的过程始终是一棵树. Prim算法过程: 一条边一条边地加, 维护一棵树. 初始 E ＝ {}空集合, V = {任选的一个起始节点} 循环(n – 1)次,每次选择一条边(v1,v2), 满足:v1属于V , v2不属于V.且(v1,v2)权值最小. E = E + (v1,v2) V = V + v2 最终E中的边是一棵最小生成树, V包含了全部节点. 以下图为例介绍Prim算法的执行过程
-
最小生成树算法之Prim算法
本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中
-
python最小生成树kruskal与prim算法详解
kruskal算法基本思路:先对边按权重从小到大排序,先选取权重最小的一条边,如果该边的两个节点均为不同的分量,则加入到最小生成树,否则计算下一条边,直到遍历完所有的边. prim算法基本思路:所有节点分成两个group,一个为已经选取的selected_node(为list类型),一个为candidate_node,首先任取一个节点加入到selected_node,然后遍历头节点在selected_node,尾节点在candidate_node的边,选取符合这个条件的边里面权重最小的边,加入到
-
C++使用Kruskal和Prim算法实现最小生成树
很久以前就学过最小生成树之Kruskal和Prim算法,这两个算法很容易理解,但实现起来并不那么容易.最近学习了并查集算法,得知并查集可以用于实现上述两个算法后,我自己动手实现了最小生成树算法. 宏观上讲,Kruskal算法就是一个合并的过程,而Prim算法是一个吞并的过程,另外在Prim算法中还用到了一种数据结构--优先级队列,用于动态排序.由于这两个算法很容易理解,在此不再赘述.接下来给出我的源代码. 输入 第一行包含两个整数n和m,n表示图中结点个数,m表示图中边的条数:接下来m行,每一行
-
Java求最小生成树的两种算法详解
目录 1 最小生成树的概述 2 普里姆算法(Prim) 2.1 原理 2.2 案例分析 3 克鲁斯卡尔算法(Kruskal) 3.1 原理 3.2 案例分析 4 邻接矩阵加权图实现 5 邻接表加权图实现 6 总结 介绍了图的最小生成树的概念,然后介绍了求最小生成树的两种算法:Prim算法和Kruskal算法的原理,最后提供了基于邻接矩阵和邻接链表的图对两种算法的Java实现. 阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:Java数据结构之图的原理与实现. 1 最小生成树的
-
NetworkX之Prim算法(实例讲解)
引言 Prim算法与Dijkstra的最短路径算法类似,它采用贪心策略.算法开始先把图中权值最小的边添加到树T中,然后不断把权值最小的边E(E的一个端点在T中,另一个在G-T中).当没有符合条件的E时算法结束,此时T就是G的一个最小生成树. NetworkX是一款Python的软件包,用于创造.操作复杂网络,以及学习复杂网络的结构.动力学及其功能. 本文借助networkx.Graph类实现Prim算法. 正文 Prim算法的代码 Prim def prim(G, s): dist = {} #
-
C++示例详解Prim算法与优先队列
目录 Prim算法 prim代码实现 优先队列 优先队列代码实现 自定义类型优先序列 贪心算法的本质是:一个问题的局部最优解,也是该问题的全局最优解. 最小生成树的最优子结构性质:假设一个无向图包含两部分A,B,其中A为最小生成树部分,B为剩余部分,则存在以下性质:该无向图中一个顶点在A部分,另一个顶点在B部分的边中,权值最小的边一定属于整个无向图的最小生成树,即部分最小权值是整个最小生成树的局部最有解,该性质符合贪心算法的特点. Prim算法 基于最小生成树的该性质,使用prim算法来求解最小
-
Java贪心算法之Prime算法原理与实现方法详解
本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在
-
java实现最短路径算法之Dijkstra算法
前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无