当前位置：文档之家 › Prim算法求解最小生成树

Prim算法求解最小生成树

  • 格式：doc
  • 大小：161.00 KB
  • 文档页数：9

Prim算法求解最小生成树
1.最小生成树问题描述
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。

2.Prim算法思想
大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗最小生成树。

因为有N个顶点，所以该MST就有N-1条边，每一次向集合V 中加入一个点，就意味着找到一条最小生成树的边。

3.Prim算法描述（步骤）
1.首先，初始化图G，并构建好无向图
for (i = 1; i <= m; i++)
{
for (j = 1; j <= m; j++)
{
graph[i][j] = MAXCOST;
}
}
for (k = 1; k <= n; k++)
{
scanf("%d %d %d",&i,&j,&cost);
graph[i][j] = cost;
graph[j][i] = cost;
}
2.再利用Prim算法来求解得到最小生成树
默认起点是1
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i];
mst[i] = 1;
}
找出距离1最近的点
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
4.算法实现（数据结构）
设置2个数据结构：
所有点默认起点是V1
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了最小生成树
mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是最小生成树的一条边，当mst[i]=0表示起点i加入最小生成树
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j])
//比较最小生成树外部的点到minid的距离或到之前的最小生成树里点的距离大小,更新lowcost[j]取最小值
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
//点j到最小生成树内的lowcost对应的最小生成树里的点是minid
}
} //相当于利用mind作为新的起点来更新lowcost[];
5.实验环境
硬件环境：WIN10系统笔记本
软件环境：Visual C++ 6.0
6.、实验结果
运行结果：
问题规模：
由算法代码中的循环嵌套可得知此算法的时间复杂度为O(n^2)。

运行时间：
7.附录（源程序代码）
#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
#define MAX 100
#define MAXCOST 0x7fffffff
int graph[MAX][MAX];
//Prim算法
int prim(int graph[][MAX], int n)
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i]; //lowcost[i]:表示以i为终点的边的最小权值
mst[i] = 1; //mst[]存放最小生成树外的点i到最小生成树最短距离时候对应的最小生成树里的点标号
}
mst[1] = 0; //当mst[i]=0表示起点i加入最小生成树
for (i = 2; i <= n; i++) //要找出n-1个点为止
{
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
printf("v%d-v%d=%d\n",mst[minid],minid,min);
sum += min;
lowcost[minid] = 0; //当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了最小生成树
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j]) //比较最小生成树外部的点到minid的距离或到之前的最小生成树里点的距离大小,更新lowcost[j]取最小值
{
lowcost[j] = graph[minid][j];
mst[j] = minid; //点j到最小生成树内的lowcost对应的最小生成树里的点是minid
}
}
}
return sum;
}
int main()
{
clock_t startTime,endTime;
int i, j, k, m, n;
int cost;
printf("请输入顶点数和边数(m n):\n");
scanf("%d %d",&m,&n); //m=顶点的个数，n=边的个数
//初始化图G
for (i = 1; i <= m; i++)
{
for (j = 1; j <= m; j++)
{
graph[i][j] = MAXCOST;
}
}
//构建图G
printf("请输入权值边对应的顶点和权值(i j w):\n");
for (k = 1; k <= n; k++)
{
scanf("%d %d %d",&i,&j,&cost);
graph[i][j] = cost;
graph[j][i] = cost; //对称
}
//求解最小生成树
startTime = clock();//计时开始
cost = prim(graph, m);
//输出最小权值和
printf("最小权值和=%d\n",cost);
endTime = clock();//计时结束
cout << "The run time is:" <<(double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
system("pause");
return 0;
}。

合集下载

的最小生成树算法Prim与Kruskal算法的比较

的最小生成树算法Prim与Kruskal算法的比较

的最小生成树算法Prim与Kruskal算法的比较Prim算法和Kruskal算法都是常用的最小生成树算法，它们可以在给定的加权连通图中找到连接所有节点的最小权重边集合。

然而，这两种算法在实现细节和时间复杂度上有所不同。

本文将对Prim算法和Kruskal算法进行比较，并讨论它们的优缺点以及适用场景。

一、Prim算法Prim算法是一种贪心算法，它从一个起始节点开始，逐步扩展最小生成树的边集合，直到包含所有节点为止。

具体步骤如下：1. 选取一个起始节点作为最小生成树的根节点。

2. 在最小生成树的边集合中寻找与当前树集合相连的最小权重边，并将这条边添加到最小生成树中。

3. 将新添加的节点加入到树集合中。

4. 重复步骤2和3，直到最小生成树包含所有节点为止。

Prim算法的时间复杂度为O(V^2)，其中V是节点的个数。

这是因为在每轮迭代中，需要从树集合以外的节点中找到与树集合相连的最小权重边，而在最坏情况下，可能需要检查所有的边。

二、Kruskal算法Kruskal算法是一种基于边的贪心算法，它按照边的权重从小到大的顺序依次选择边，并判断是否加入最小生成树中。

具体步骤如下：1. 初始化一个空的最小生成树。

2. 将所有边按照权重从小到大进行排序。

3. 依次检查每条边，如果这条边连接了两个不同的树（即不会形成环），则将这条边加入到最小生成树中。

4. 重复步骤3，直到最小生成树包含所有节点为止。

Kruskal算法使用并查集数据结构来快速判断连通性，时间复杂度为O(ElogE)，其中E是边的个数。

排序边的时间复杂度为O(ElogE)，而对每条边进行判断和合并操作的时间复杂度为O(E)。

三、比较与总结1. 时间复杂度：Prim算法的时间复杂度为O(V^2)，而Kruskal算法的时间复杂度为O(ElogE)。

因此，在边的数量较大的情况下，Kruskal 算法的效率优于Prim算法。

2. 空间复杂度：Prim算法需要维护一个大小为V的优先队列和一个大小为V的布尔数组，而Kruskal算法需要维护一个大小为V的并查集。

prim算法求最小生成树c代码

prim算法求最小生成树c代码

一、概述在图论中，最小生成树是指在一个连通图中生成一棵包含图中所有顶点且边权值之和最小的树。

prim算法是一种常用的求取最小生成树的算法之一，其基本思想是从一个起始顶点开始，逐步选择与当前树相邻的并且权值最小的边，直到包含了图中所有的顶点为止。

本文将介绍prim算法的原理以及给出相应的C代码实现。

二、prim算法原理1. 初始化选择任意一个顶点作为起始顶点，并将其标记为已访问。

设置一个集合V来存放已经访问的顶点，初始化为空集合。

2. 重复以下步骤直到V包含了所有顶点：（1）遍历集合V中的所有顶点，找到与之相邻且未被访问过的顶点中边权值最小的顶点，将其加入集合V中。

（2）将找到的顶点与其相邻的边加入最小生成树中。

3. 输出最小生成树当集合V包含了所有顶点之后，即可输出最小生成树。

三、prim算法C代码实现以下是prim算法的C代码实现：#include <stdio.h>#include <limits.h>#define V 5 // 顶点个数int minKey(int key[], bool mstSet[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++) {if (!mstSet[v] key[v] < min) {min = key[v], min_index = v;}}return min_index;}void printMST(int parent[], int graph[V][V]) {printf("Edge \tWeight\n");for (int i = 1; i < V; i++) {printf("d - d \td \n", parent[i], i, graph[i][parent[i]]);}void primMST(int graph[V][V]) {int parent[V]; // 存放最小生成树的结点int key[V]; // 存放与最小生成树相邻的边的权值bool mstSet[V]; // 存放已访问的顶点for (int i = 0; i < V; i++) {key[i] = INT_MAX, mstSet[i] = false;}key[0] = 0;parent[0] = -1;for (int count = 0; count < V - 1; count++) {int u = minKey(key, mstSet);mstSet[u] = true;for (int v = 0; v < V; v++) {if (graph[u][v] !mstSet[v] graph[u][v] < key[v]) { parent[v] = u, key[v] = graph[u][v];}}}printMST(parent, graph); }int m本人n() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};primMST(graph);return 0;}```四、代码说明1. minKey函数该函数用于在尚未加入最小生成树的结点中找到与最小生成树相邻的边中权值最小的结点。

最小生成树的Prim算法以及Kruskal算法的证明

最小生成树的Prim算法以及Kruskal算法的证明

最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。

其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。

Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。

引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成1、顶点vi2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）3、其余若⼲个连通分量（个数⼤于等于0）三个部分现在要重建⽣成树，就要重新连接之前被断开的各边虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。

这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。

Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。

Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。

简述prim算法的过程

简述prim算法的过程

简述prim算法的过程Prim算法是一种用于求解最小生成树的贪心算法，它把一个连通图分割成多个子图，使得每个子图都是一棵最小生成树，且这些子树的联合就是原连通图的最小生成树。

Prim算法是由安德鲁普里姆(Andrew.Prim)在1957年提出的，用于求解最短路径(解决连通度和权重问题)。

Prim算法一般步骤如下：（1）初始化：从图中任选一顶点，作为第一个顶点加入到最小生成树中；（2）循环：从剩余的顶点中，找到最小代价的边，将这条边加入到最小生成树中，并将这条边的顶点也加入到最小生成树中；（3）重复：重复步骤2，直到最小生成树中包括全部的顶点；（4）停止：最小生成树已经构造完成，停止算法的执行。

Prim算法是贪心算法的一种，它每次在可选的边中搜索代价最小的边，加入到最小生成树中，直至所有的顶点都在最小生成树中。

它的一般步骤可表示为：（1）从最小生成树中所有的顶点中，找出一个确定的顶点 u，它的邻居还未加入最小生成树；（2）从u的邻居v中，找出一个代价最小的边(u,v)，将这条边加到最小生成树中；（3）将顶点v加入到最小生成树中；（4）重复步骤1到3，直到最小生成树中包括所有的顶点；深入分析Prim算法，我们可以发现它是一种贪心策略，它在设计上采用了“最优化原则”，即每次都选择代价最小的边加入到最小生成树中，而不管这个边是否有利于求解最小生成树的问题，因而贪心算法的实现对“最优策略”的选择是关键。

Prim算法的时间复杂度取决于边的存储结构，如果存储为邻接表，其时间复杂度为O(V2)，如果存储为邻接矩阵，其时间复杂度为O(V2+E)。

其中，V为顶点数，E为边数。

Prim算法在现实生活中有着广泛的应用，比如电路设计时，需要求最小生成树，以此达到最短路径、最小花费的目的；另外，它还可以用于网络路由的设计，最小化网络的延迟；此外，它还可以用于求解旅行商问题，最小化客户的费用等等。

总之，Prim算法是一种有效的求解最小生成树的方法，它通过不断地在可选边中寻找代价最小的边，来构建最小生成树；在现实生活中，它也有着广泛的应用。