最小生成树的Prim算法提高型实验报告

最小生成树实验报告最小生成树实验报告一、引言最小生成树是图论中的一个重要概念，它在实际问题中有着广泛的应用。

本次实验旨在通过编程实现最小生成树算法，并通过实验数据对算法进行分析和评估。

二、算法介绍最小生成树算法的目标是在给定的带权无向图中找到一棵生成树，使得树上所有边的权重之和最小。

本次实验我们选择了两种经典的最小生成树算法：Prim 算法和Kruskal算法。

1. Prim算法Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展生成树的规模，直到包含所有顶点为止。

算法的具体步骤如下：（1）选择一个起始顶点，将其加入生成树中。

（2）从与生成树相邻的顶点中选择一个权重最小的边，将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法Kruskal算法是一种基于并查集的贪心算法，它首先将图中的边按权重从小到大进行排序，然后逐个加入生成树中，直到生成树包含所有顶点为止。

算法的具体步骤如下：（1）将图中的边按权重从小到大进行排序。

（2）逐个加入边，如果该边的两个顶点不在同一个连通分量中，则将其加入生成树中。

（3）重复上述步骤，直到生成树包含所有顶点。

三、实验过程本次实验我们使用C++语言实现了Prim算法和Kruskal算法，并通过随机生成的图数据进行了测试。

1. Prim算法的实现我们首先使用邻接矩阵表示图的结构，然后利用优先队列来选择权重最小的边。

具体实现过程如下：（1）创建一个优先队列，用于存储生成树的候选边。

（2）选择一个起始顶点，将其加入生成树中。

（3）将与生成树相邻的顶点及其边加入优先队列。

（4）从优先队列中选择权重最小的边，将其加入生成树中，并更新优先队列。

（5）重复上述步骤，直到生成树包含所有顶点。

2. Kruskal算法的实现我们使用并查集来维护顶点之间的连通关系，通过排序后的边序列来逐个加入生成树中。

具体实现过程如下：（1）将图中的边按权重从小到大进行排序。

最小生成树（Minimum Spanning Tree）实验报告1. 实验目的本实验旨在通过实践掌握最小生成树算法的基本原理和实现方法。

最小生成树是图论中的一个重要概念，用于解决具有权重的连通图的最优路径问题。

通过本实验，我们将学习如何使用最小生成树算法找到一棵连接图的所有节点且总权重最小的树。

2. 实验原理最小生成树是一个连通图的一种生成树，它的所有边的权重之和最小。

最小生成树的求解算法有多种，其中两种常用的算法是 Prim 算法和 Kruskal 算法。

2.1 Prim 算法Prim 算法是一种贪心算法，从一个节点开始，逐步扩展最小生成树的边。

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

2. 在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

3. 将该节点标记为已访问。

4. 重复步骤 2 和步骤 3，直到所有节点都被访问。

2.2 Kruskal 算法Kruskal 算法也是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。

具体步骤如下： 1. 对所有边按照权重进行排序。

2. 依次选择权重最小的边，如果该边的两个端点不在同一个连通分量中，则将该边加入最小生成树，并将这两个端点合并到同一个连通分量中。

3. 重复步骤 2，直到所有节点都在同一个连通分量中，即最小生成树构建完成。

3. 实验步骤本实验将使用 Prim 算法和 Kruskal 算法分别求解给定图的最小生成树。

3.1 数据准备首先，我们需要准备一个具有权重的连通图作为实验数据。

假设该图有 n 个节点和 m 条边，我们可以使用邻接矩阵或邻接表来表示这个图。

3.2 Prim 算法求解最小生成树1.首先，选择一个起始节点作为最小生成树的根节点，并将该节点标记为已访问。

2.初始化一个空的最小生成树，用于存储最终的结果。

3.重复以下步骤，直到所有节点都被访问：1.在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

实验报告题目说明：POJ2395 Out of Ray题目大意：Beth有m个农场，农场之间有些相通，有些不通。

已知，Beth每一英里要一盎司的水，Beth希望走遍所有的农场但携带最少的水。

问：Beth最多需要带多少水？（每个农场都可以补充水）本程序利用Prim算法俩实现题目要求。

1.<创建>输入农场数和农场之间的距离（均为整数），程序给出连通判断。

2.修改路径按格式输入修改值，此时路线可能会改变。

3.<输出最大携带水量>，附上最小生成树实验说明：1.基本思想利用邻接表G [ ][ ] 储存农场信息，然后使用Prim算法来完成最小生成树的构建；最后寻找出最大边，如果农场是不连通的将给出提示，可以对路径修改。

2.函数模块（1）int InitiTable(int G[][MaxFarm],int num);//创建邻接表，返回值是农场数目{int j,k,TempValue;while(true){cout<<"请输入农场的数目:"<<' ';cin>>num;if(num<=MaxFarm&&num>0)break;cout<<"错误！请重新输入."<<endl<<endl;}for(j=0;j<num;j++){for(k=0;k<num;k++){if(j==k)G[j][k]=MaxWeight;else if(j<k){while(true){cout<<"请输入农场"<<j+1<<"至农场"<<k+1<<"的距离。

如果该路不存在请输入-1："<<endl;cin>>TempValue;if(TempValue>=-1&&TempValue<MaxWeight) break;cout<<"输入无效，请重新输入。

学生实验报告学院：软件与通信工程学院课程名称：算法设计与分析专业班级：软件工程142班姓名：周平学号： 0143987学生实验报告一、实验综述实现贪心法的下列六个算法之一：1、可切割背包问题2、单源点最短路径求解算法——Dijkstra算法3、Dijkstra算法的改进版4、最小耗费生成树Kruskal算法5、最小耗费生成树Prim算法6、最小耗费生成树Prim算法的改进版要求与说明：1、各人独立完成，2、实验报告要求有：算法说明与描述、代码、数据集合（各算法1 要求达到百、千级）。

3、实验报告要有2-3个截图，包括导入数据、重要中间过程、最后结果等；4、额外完成所实现的算法，每完成一个加1 分；5、程序要求用C 语言完成，每个实验报告的代码都会被测试，对运行环境有特别要求的需要专门说明，否则，程序测试不通过责任自负；6、实验报告都有步骤分，但是，程序测试结果与实验报告结果不相符的，将被加重扣分；7、严禁抄袭——代码重复度超过90%者视作抄袭，抄袭者以0 分记，可以对评审提出质疑。

疑。

2、实验仪器、设备或软件1、个人电脑2、Microsoft Visual Studio 2015二、实验过程（实验步骤、记录、数据、分析）实验代码如下:#include<stdio.h>#include<stdlib.h>#define MAX 100#define MAXCOST 0x7fffffffint graph[MAX][MAX];int Prim(int graph[][MAX], int n){/* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ int lowcost[MAX];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */int mst[MAX];int i, j, min, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化 */for (i = 2; i <= n; i++){/* 最短距离初始化为其他节点到1号节点的距离 */lowcost[i] = graph[1][i];/* 标记所有节点的起点皆为默认的1号节点 */mst[i] = 1;}/* 标记1号节点加入生成树 */mst[1] = 0;/* n个节点至少需要n-1条边构成最小生成树 */for (i = 2; i <= n; i++){min = MAXCOST;minid = 0;/* 找满足条件的最小权值边的节点minid */for (j = 2; j <= n; j++){/* 边权值较小且不在生成树中 */if (lowcost[j] < min && lowcost[j] != 0){min = lowcost[j];minid = j;}}/* 输出生成树边的信息:起点，终点，权值 */printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);/* 累加权值 */sum += min;/* 标记节点minid加入生成树 */lowcost[minid] = 0;/* 更新当前节点minid到其他节点的权值 */for (j = 2; j <= n; j++){/* 发现更小的权值 */if (graph[minid][j] < lowcost[j]){/* 更新权值信息 */lowcost[j] = graph[minid][j];/* 更新最小权值边的起点 */mst[j] = minid;}}}/* 返回最小权值和 */return sum;}int main(){printf("请输入点数和边数：");int i, j, k, m, n;int x, y, cost;char chx, chy;scanf("%d%d", &m, &n);/* 读取节点和边的数目 */getchar();printf("请输入边的信息：");/* 初始化图，所有节点间距离为无穷大 */for (i = 1; i <= m; i++){for (j = 1; j <= m; j++){graph[i][j] = MAXCOST;}}/* 读取边信息 */for (k = 0; k < n; k++){scanf("%c %c %d", &chx, &chy, &cost);getchar();i = chx - 'A' + 1;j = chy - 'A' + 1;graph[i][j] = cost;graph[j][i] = cost;}/* 求解最小生成树 */cost = Prim(graph, m);/* 输出最小权值和 */printf("Total:%d\n", cost);//system("pause");return 0;}代码说明：1、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。

用Prim算法构造最小生成树班级：2010级计算机1班学号：2010131116 ：才一、实验目的了解最小生成树的概念，掌握生成最小生成树的方法。

二、实验容建立一个含任意结点的无向连通网，并用Prim算法构造其最小生成树三、实验要点及说明如果无向连通图是一个网，则其所有生成树中必有一棵树的边的权值总和最小，这棵生成树为最小生成树。

Prim算法：在图G=（V，E）（V为顶点集，E为边集）中任选一顶点v0,令集合U={v0}为初态，在一个顶点在U中，另一顶点在V-U中的所有边中找权值最小的边（u,v）（U∈u,v∈V-U），并将v加入到U中，同时将边（u,v）加入集合T中（T的初态为空集），这样不断地扩大U，直至U=V，则集合T中的边为所求最小生成树的边四、算法思想与算法描述1、邻接矩阵的数据类型的定义如下：typedef struct{ int no; /*顶点编号*/string name; /*顶点其他信息*/} VertexType; /*顶点类型*/typedef struct/*图的定义*/{ int edges[MAXV][MAXV]; /*邻接矩阵*/int vexnum,arcnum; /*顶点数,弧数*/VertexType vexs[MAXV]; /*存放顶点信息*/}MGraph;2、临时数组的存放的数据类型struct {int closest; // U集中的顶点序号int lowcost; // 边的权值} closedge[MAXV];int const INF=32767; /*INF表示∞*/3、prime算法实现：（原理见实验说明）void prime(MGraph g,int v){int lowcost[MAXV];int min;int closest[MAXV];int i,j,k;for(i=0;i<g.vexnum;i++){lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.vexnum;i++){min=INF;for(j=0;j<g.vexnum;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("边(%d,%d)权为:%d\n",closest[k],k,min);lowcost[k]=0;for(j=0;j<g.vexnum;j++)if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}4、邻接矩阵的创建void CreatMGraph(MGraph &M){int n,e;cout<<"输入定点数:";cin>>n;M.vexnum=n;cout<<"输入弧数:";cin>>e;M.arcnum=e;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)M.edges[i][j]=0;elseM.edges[i][j]=INF;}}cout<<"输入边的权：（如1 2 3 表示点到点的权时）"<<endl; for(int i=0;i<2*e;i++){int x,y,z;cin>>x>>y>>z;M.edges[x][y]=z;}cout<<"输入点编号，名字："<<endl;for(int i=0;i<n;i++){int No;string str;cin>>No>>str;M.vexs[i].name=str;M.vexs[i].no=No;}}int const MAXV=164、主函数int main(void){MGraph m;CreatMGraph(m);cout<<"输出无向图的二维矩阵："<<endl;for(int i=0;i<m.vexnum;i++){for(int j=0;j<m.vexnum;j++){if(m.edges[i][j]==INF)cout<<" ";elsecout<<m.edges[i][j]<<" ";}cout<<endl;}cout<<"输入最小生成树："<<endl;prime(m,0);return 0;}五、实验测试及结果1.输入图的定点数和边数2.输入邻矩阵：3.顶点编号级名字的输入：4.运行结果：六、总结与体会实验任务基本完成，加深队算法思想的认识附源码：#include<iostream> #include<string> using namespace std;int const MAXV=16;typedef struct{ int no; /*顶点编号*/string name; /*顶点其他信息*/} VertexType; /*顶点类型*/typedef struct/*图的定义*/{ int edges[MAXV][MAXV]; /*邻接矩阵*/int vexnum,arcnum; /*顶点数,弧数*/VertexType vexs[MAXV]; /*存放顶点信息*/}MGraph;struct {int closest; // U集中的顶点序号int lowcost; // 边的权值} closedge[MAXV];int const INF=32767; /*INF表示∞*/void prime(MGraph g,int v){int lowcost[MAXV];int min;int closest[MAXV];int i,j,k;for(i=0;i<g.vexnum;i++){lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.vexnum;i++){min=INF;for(j=0;j<g.vexnum;j++)if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("边(%d,%d)权为:%d\n",closest[k],k,min);lowcost[k]=0;for(j=0;j<g.vexnum;j++)if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}void CreatMGraph(MGraph &M){int n,e;cout<<"输入定点数:";cin>>n;M.vexnum=n;cout<<"输入弧数:";cin>>e;M.arcnum=e;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)M.edges[i][j]=0;elseM.edges[i][j]=INF;}}cout<<"输入边的权：（如1 2 3 表示点到点的权时）"<<endl;for(int i=0;i<2*e;i++){int x,y,z;cin>>x>>y>>z;M.edges[x][y]=z;}cout<<"输入点编号，名字："<<endl;for(int i=0;i<n;i++){int No;string str;cin>>No>>str;M.vexs[i].name=str;M.vexs[i].no=No;}}int main(void){MGraph m;CreatMGraph(m);cout<<"输出无向图的二维矩阵："<<endl;for(int i=0;i<m.vexnum;i++){for(int j=0;j<m.vexnum;j++){if(m.edges[i][j]==INF)cout<<" ";elsecout<<m.edges[i][j]<<" ";}cout<<endl;}cout<<"输入最小生成树："<<endl;prime(m,0);return 0;}。

摘要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的权值最小的生成树。

本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。

Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。

最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络等等一系列的应用。

关键词：最小生成树，邻接矩阵，Kruskal算法，Prim算法目录一、引言 (3)二、设计目的与任务 (4)2.1课程设计目的 (4)2.2课程设计的任务 (4)三、设计方案 (4)3.1需求分析 (4)3.2数据结构分析 (4)3.2.1抽象数据类型(ADT)如下 (4)3.2.2基本操作 (5)3.2.3存储结构 (5)3.3最小生成树的算法分析 (7)3.3.1主函数模块代码......................... 错误!未定义书签。

3.3.2邻接矩阵定义模块代码 (7)3.3.3创建链接矩阵模块代码 (7)3.3.4最小生成树Prim算法及代价模块代码...... 错误!未定义书签。

3.3.5最小生成树kruskal算法及代价模块代码 (8)四、调试分析与体会 (9)五、运行结果 (10)六、结论 (16)七、参考文献 (16)一、引言《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。

本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。

本课程设计我们要解决的问题是图最小生成树问题。

要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。

最小生成树实验报告最小生成树实验报告引言：最小生成树是图论中一个重要的概念，它在许多实际问题中都有广泛的应用。

本次实验旨在通过实际操作，深入理解最小生成树的概念、算法及其在实际问题中的应用。

本文将从实验的目的、实验过程、实验结果及分析等方面进行详细的论述。

实验目的：1. 理解最小生成树的概念及其在实际问题中的应用；2. 掌握最小生成树的两种常用算法：Prim算法和Kruskal算法；3. 通过实际操作，加深对最小生成树算法的理解。

实验过程：1. 实验环境的搭建：首先，我们需要在计算机上搭建一个图论实验环境。

选择一门编程语言，如Python，来实现最小生成树算法。

通过安装相应的开发环境和图论库，我们可以方便地进行实验。

2. 数据的准备：为了进行最小生成树的实验，我们需要准备一组具有权值的图数据。

可以通过手动输入或从文件中读取的方式获取数据。

确保数据的合理性和完整性，以便进行后续的实验操作。

3. Prim算法的实现：Prim算法是一种贪心算法，用于求解最小生成树。

在实验中，我们需要实现Prim算法，并将其应用于准备好的图数据上。

通过编程实现，我们可以得到Prim算法生成的最小生成树。

4. Kruskal算法的实现：Kruskal算法是另一种常用的最小生成树算法。

与Prim算法不同，Kruskal算法是一种基于边的贪心算法。

同样地，我们需要实现Kruskal算法，并将其应用于准备好的图数据上，以获得Kruskal算法生成的最小生成树。

实验结果与分析：通过实验，我们得到了Prim算法和Kruskal算法生成的最小生成树。

我们可以将这两个结果进行对比和分析，以进一步理解这两种算法的特点和应用场景。

首先，我们可以比较两个算法生成的最小生成树的权值。

通过计算权值的总和，我们可以确定哪个算法生成的最小生成树更优。

此外，我们还可以比较两个算法生成的最小生成树的结构，观察它们是否存在差异。

其次，我们可以分析两个算法的时间复杂度和空间复杂度。

算法分析与设计实验报告第次实验}最小生成树N=4:最小生成树N=5:最小生成树N=6:通过本次实验明白了最小生成树贪心算法的设计思路，掌握了prim算法附录：完整代码#include<iostream>#include <stdio.h>#include <time.h>#include <iomanip>#include <string.h>#define MaxInt 0x3f3f3f3f#define N 110using namespace std;//创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问int map[N][N],low[N],closest[N],visited[N];int n;int prim(){int i;int min=MaxInt,result=0;memset(visited,0,sizeof(visited));visited[1]=1;//从某点开始，分别标记和记录该点for(i=2;i<=n;i++){low[i]=map[1][i];//给low数组赋值closest[i]=1;visited[i]=0;}for(i=1;i<n;i++)//运行n-1次{//找出最小权值并记录位置min=MaxInt;int k=1;for(int j=2;j<=n;j++)if(visited[j]==0&&min>low[j]){min=low[j];k=j;cout<<k<<"与"<<closest[k]<<"相连"<<endl;}result+=min;//最小权值累加visited[k]=1;//标记该点for(int j=2;j<=n;j++)//更新权值if(visited[j]==0&&low[j]>map[k][j]){low[j]=map[k][j];closest[j]=k;}}return result;}int main(){int i,p=0;double k=0.0;clock_t start,end,over;start=clock(); end=clock();over=end-start;start=clock();int v,j,ans;cout<<"(以EOF为程序结束符)输入顶点数n:";while(scanf("%d",&n)!=EOF){cout<<"输入n*n的权值矩阵:"<<endl;memset(map,MaxInt,sizeof(map));//所有权值初始化为最大for(i=1;i<=n;i++)for(j=1;j<=n;j++){cin>>v;map[i][j]=v;}ans=prim();cout<<"最小生成树的权值之和为："<<ans<<endl;for(i=0;i<1000000000;i++) p=p+i;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK);}return 0;}。

prim算法实验报告Prim算法实验报告一、引言Prim算法是一种常用的最小生成树算法，用于在一个加权连通图中生成一棵覆盖所有顶点且边权和最小的树。

本实验旨在通过编程实现Prim算法，并分析其时间复杂度和实际应用。

二、算法描述Prim算法的基本思想是从一个初始顶点开始，逐步扩展生成树，每次选择与当前生成树连接的最短边对应的顶点，并将其加入生成树中，直到所有顶点都被加入为止。

具体步骤如下：1. 选择一个初始顶点作为生成树的根节点。

2. 在剩余的顶点中，选择与当前生成树连接的最短边对应的顶点，并将其加入生成树中。

3. 更新生成树与剩余顶点之间的边权，即若新加入的顶点到其他剩余顶点的距离更短，则更新距离。

4. 重复步骤2和步骤3，直到所有顶点都被加入生成树为止。

三、实验过程本实验使用C++编程语言实现Prim算法。

首先，通过邻接矩阵表示给定的加权连通图，其中顶点间的距离用边的权值表示，无连接的顶点间距离设为无穷大。

然后，选择一个初始顶点作为生成树的根节点，并将其加入生成树中。

接下来，循环执行以下步骤，直到所有顶点都被加入生成树为止：1. 找到与当前生成树连接的最短边对应的顶点，将其加入生成树中。

2. 更新生成树与剩余顶点之间的边权。

3. 记录每次加入生成树的边及其权值。

四、实验结果本实验使用了一个具体的加权连通图进行测试。

测试结果显示，Prim算法能够正确生成最小生成树，并且生成的树的边权和确实是最小的。

通过对比不同初始顶点的选择，发现生成树的形状可能会有所差异，但边权和仍然是最小的。

五、时间复杂度分析Prim算法的时间复杂度主要取决于两个因素：顶点数和边数。

在每次循环中，需要找到与当前生成树连接的最短边，这个过程需要遍历所有剩余顶点，时间复杂度为O(V)。

总共需要执行V次循环，因此Prim算法的时间复杂度为O(V^2)。

如果使用优先队列来优化寻找最短边的过程，时间复杂度可以降至O((V+E)logV)，其中E为边数。

一、实验目的1. 理解普里姆算法的基本原理和步骤。

2. 掌握使用C语言实现普里姆算法的方法。

3. 熟悉最小生成树的概念及其在实际应用中的重要性。

4. 通过实验验证普里姆算法的正确性和效率。

二、实验环境1. 操作系统：Windows 102. 编程语言：C语言3. 开发环境：Visual Studio三、实验原理普里姆算法是一种贪心算法，用于在加权无向图中寻找最小生成树。

最小生成树是指一个无向图的所有顶点构成的树，其边权值之和最小。

普里姆算法的基本思想是从某个顶点开始，逐步增加边，直到包含所有顶点为止。

四、实验步骤1. 定义邻接矩阵：首先定义一个二维数组表示图的邻接矩阵，其中元素表示两个顶点之间的边权值。

2. 初始化数据结构：定义一个结构体表示顶点，包含顶点的编号和距离。

初始化一个数组存储所有顶点的结构体。

3. 选择起始顶点：选择一个顶点作为起始顶点，将其距离设置为0，其余顶点的距离设置为无穷大。

4. 遍历邻接矩阵：对于每个顶点，遍历其邻接矩阵，找到距离最小的边，将其加入最小生成树中，并更新相邻顶点的距离。

5. 重复步骤4：重复步骤4，直到所有顶点都被加入最小生成树中。

6. 输出结果：输出最小生成树的边和权值。

五、实验代码```c#include <stdio.h>#include <stdlib.h>#define MAXVEX 6#define INF 10000typedef struct {int adjvex; // 邻接顶点的位置int lowcost; // 与adjvex顶点相连的边的权值} MinNode;typedef struct {char vexs[MAXVEX]; // 顶点表MinNode adjmatrix[MAXVEX][MAXVEX]; // 邻接矩阵int numVertexes, numEdges; // 图中当前顶点的数量和边的数量} MGraph;void CreateMGraph(MGraph G) {int i, j, k, w;printf("请输入顶点数量和边数量：\n");scanf("%d %d", &G->numVertexes, &G->numEdges);printf("请输入顶点信息：\n");for (i = 0; i < G->numVertexes; i++) {scanf("%s", G->vexs[i]);}for (i = 0; i < G->numVertexes; i++) {G->adjmatrix[i][j].adjvex = 0;G->adjmatrix[i][j].lowcost = INF;}}for (k = 0; k < G->numEdges; k++) {printf("请输入边(%d)的两个顶点和权值：\n", k + 1); scanf("%d %d %d", &i, &j, &w);G->adjmatrix[i][j].adjvex = j;G->adjmatrix[i][j].lowcost = w;G->adjmatrix[j][i].adjvex = i;G->adjmatrix[j][i].lowcost = w;}}void Prim(MGraph G, int u) {int min, i, j, k;MinNode adjvex;int visited[MAXVEX] = {0}; // 标记顶点是否被访问过visited[u] = 1;printf("%c ", G.vexs[u]); // 输出起始顶点for (i = 1; i < G.numVertexes; i++) {min = INF;k = u;if (visited[j] == 0 && G.adjmatrix[k][j].lowcost < min) { min = G.adjmatrix[k][j].lowcost;adjvex = G.adjmatrix[k][j];k = j;}}printf("%c ", G.vexs[k]); // 输出当前顶点visited[k] = 1;G.adjmatrix[u][k].lowcost = INF;G.adjmatrix[k][u].lowcost = INF;}}int main() {MGraph G;int u;printf("请输入起始顶点编号：\n");scanf("%d", &u);CreateMGraph(&G);Prim(G, u);return 0;}```六、实验结果1. 输入顶点数量和边数量：6 82. 输入顶点信息：A B C D E F3. 输入边(1)的两个顶点和权值：0 1 14. 输入边(2)的两个顶点和权值：0 2 25. 输入边(3)的两个顶点和权值：1 2 36. 输入边(4)的两个顶点和权值：1 3 67. 输入边(5)的两个顶点和权值：2 3 48. 输入边(6)的两个顶点和权值：2 4 59. 输入边(7)的两个顶点和权值：3 4 710. 输入边(8)的两个顶点和权值：4 5 811. 输入起始顶点编号：0实验结果：A B C D E F七、实验总结通过本次实验，我们成功实现了普里姆算法，并验证了其在实际应用中的有效性。

黄冈师范学院提高型实验报告实验课题最小生成树的Prim算法（实验类型：□综合性■设计性□应用性）实验课程算法程序设计实验时间 2010年12月24日学生姓名周媛鑫专业班级计科 0801学号 200826140110一．实验目的和要求（1）根据算法设计需要, 掌握连通网的灵活表示方法;（2）掌握最小生成树的Prim算法;（3）熟练掌握贪心算法的设计方法;二．实验条件（1）硬件环境：实验室电脑一台（2）软件环境：winTC三．实验原理分析（1）最小生成树的定义：假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。

可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。

其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。

（2）构造最小生成树可以用多种算法。

其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。

若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。

（3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。

算法思想如下：假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。

算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。

此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

四．实验步骤（1）数据结构的设计：采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作：邻接矩阵的抽象数据结构定义：#define INFINITY INT_MAX //最大值#define MAX_ERTEX_NUM 20 //最大顶点数typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{VRType adj ; // VRType 是顶点关系的类型。

prim计算实验报告Prim计算实验报告引言：Prim算法是一种常用的图论算法，用于解决最小生成树问题。

在本次实验中，我们通过使用Prim算法，对一个给定的图进行计算，并得出最小生成树。

一、实验目的本次实验的目的是熟悉Prim算法的原理和实现方法，通过实际操作，了解算法的具体过程和效果。

同时，通过对比实验结果，探讨Prim算法在不同图结构下的优劣势。

二、实验方法1. 算法原理Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展最小生成树的边集合，直到包含所有顶点为止。

具体步骤如下：（1）选择一个起始顶点，将其加入最小生成树的顶点集合。

（2）从与选定顶点相连的边中，选择一条权值最小的边，将其加入最小生成树的边集合。

（3）将新加入的顶点也加入最小生成树的顶点集合。

（4）重复步骤（2）和（3），直到最小生成树的顶点包含所有顶点。

2. 实验步骤（1）读取图的数据，构建邻接矩阵表示图的结构。

（2）选择一个起始顶点，将其加入最小生成树的顶点集合。

（3）从与选定顶点相连的边中，选择一条权值最小的边，将其加入最小生成树的边集合。

（4）将新加入的顶点也加入最小生成树的顶点集合。

（5）重复步骤（3）和（4），直到最小生成树的顶点包含所有顶点。

（6）输出最小生成树的边集合和权值。

三、实验结果我们选择了一个具有10个顶点和15条边的图进行实验。

经过计算，得出的最小生成树的边集合和权值如下：边集合：（1, 2），（1, 3），（2, 4），（2, 5），（3, 6），（4, 7），（4, 8），（5, 9），（6, 10）权值之和：28四、实验分析通过对比实验结果，我们可以发现Prim算法在求解最小生成树问题上具有以下优势：1. 时间复杂度低：Prim算法的时间复杂度为O(V^2)，其中V为顶点数。

相比于其他算法，Prim算法的时间复杂度较低，适用于大规模图的计算。

2. 结果唯一性：Prim算法得到的最小生成树是唯一的，不受图的表示方式和顶点选择的影响。

最小生成树实验报告1.引言最小生成树（Minimum Spanning Tree，简称MST）是图论中的重要概念，在各个领域都有广泛的应用。

最小生成树是指在给定的加权连通图中，选择一个子集，使得该子集包含了所有的顶点，并且所有边的权值之和最小。

本实验主要目的是探讨最小生成树的算法并比较它们的效率和准确性。

2.实验方法本次实验使用Python编程语言实现了两种著名的最小生成树算法：Prim算法和Kruskal算法。

Prim算法是一种贪心算法，从一个顶点开始不断扩张集合，直到包含所有顶点，生成最小生成树。

Kruskal算法则是基于并查集的算法，将边按照权值排序后逐一加入生成树，同时要保证加入的边不会产生环路。

3.实验过程首先，我们从文件中读取了一张加权无向图的数据。

图的表示采用邻接矩阵的方式，即用一个二维数组来存储顶点之间的连接关系和权值。

读取完图的数据后，我们分别使用Prim算法和Kruskal算法求解最小生成树。

在Prim算法中，我们使用一个辅助数组来记录顶点是否已被访问过，然后从任意一个顶点开始，依次将与当前集合相邻的顶点加入，并选择权值最小的边。

直到所有顶点都被访问过，并形成了一个最小生成树。

在Kruskal算法中，我们首先将所有边按照权值从小到大进行排序。

然后，从权值最小的边开始，逐一将边加入生成树。

加入时，需要判断两个顶点是否在同一个连通分量中，以避免产生环路。

实验中，我们使用了Python中的heapq库来实现了堆排序，以加快Prim算法的运行速度。

4.实验结果经过实验，我们得到了图的最小生成树以及对应的权值。

实验数据显示，当图中顶点较少时，Prim算法和Kruskal算法几乎没有明显的差别。

但当图的规模增大时，Prim算法明显比Kruskal算法更快。

5.实验分析从实验结果可以看出，Prim算法和Kruskal算法都可以求解最小生成树，但在不同情况下它们的性能表现并不相同。

Prim算法适用于稠密图，因为它的时间复杂度与顶点的平方成正比；而Kruskal算法适用于稀疏图，因为它的时间复杂度与边的数量成正比。

最小生成树prim算法实验报告最小生成树Prim算法实验报告引言：最小生成树（Minimum Spanning Tree，简称MST）是图论中的一个重要概念，意为在一个连通图中找到一棵生成树，使得树上所有边的权值之和最小。

Prim算法是一种常用的解决MST问题的贪心算法。

本实验旨在通过实际操作和观察，深入理解Prim算法的原理与过程。

实验目的：1. 理解Prim算法的基本原理；2. 掌握Prim算法的具体实现过程；3. 利用Prim算法求解最小生成树问题；4. 分析Prim算法的时间复杂度。

实验过程：1. 实验环境搭建：在实验开始前，我们需要搭建合适的实验环境。

首先，我们选择一种编程语言，如Python或C++，来实现Prim算法。

其次，我们需要准备一个图的数据集，可以是随机生成的或者是从现实问题中提取的。

最后，我们需要一个用于可视化的工具，以便观察Prim算法的执行过程和结果。

2. Prim算法实现：Prim算法的核心思想是从一个顶点开始，逐步扩展生成树，直到包含所有顶点为止。

具体实现过程如下：a. 初始化一个空的生成树，选择一个起始顶点；b. 在剩余的顶点中，选择与生成树距离最近的顶点，并将其加入生成树；c. 更新生成树与剩余顶点的距离，如果存在更短的路径，则更新；d. 重复步骤b和c，直到生成树包含所有顶点。

3. Prim算法求解最小生成树问题：利用Prim算法求解最小生成树问题的步骤如下：a. 根据实验环境搭建中准备的图数据集，构建图的邻接矩阵或邻接表表示；b. 选择一个起始顶点，将其加入生成树；c. 重复以下步骤，直到生成树包含所有顶点：i. 从生成树中选择一个顶点v，找到与v相连的顶点中距离最小的顶点u； ii. 将顶点u加入生成树，并将(u, v)边加入生成树的边集；iii. 更新生成树与剩余顶点的距离，如果存在更短的路径，则更新。

实验结果与分析：我们通过实验环境搭建和Prim算法实现，成功求解了多个最小生成树问题。

篇一：prim算法实验报告算法实验报告学院：xxx班级：xxx学号：xxx姓名：xxx prim篇二：prim最小生成树算法实验报告算法分析与设计之prim学院：软件学院学号：201421031059 姓名：吕吕一、问题描述1. prim的定义prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。

(强调的是树，树是没有回路的)。

2. 实验目的选择一门编程语言，根据prim算法实现最小生成树，并打印最小生成树权值。

二、算法分析与设计1.prim算法的实现过程基本思想：假设g＝(v，e)是连通的，te是g上最小生成树中边的集合。

算法从u＝{u0}（u0∈v）、te＝{}开始。

重复执行下列操作：在所有u∈u，v∈v－u的边(u，v)∈e中找一条权值最小的边(u0,v0)并入集合te中，同时v0并入u，直到v＝u为止。

此时，te中必有n-1条边，t=(v，te)为g的最小生成树。

prim算法的核心:始终保持te中的边集构成一棵生成树。

2.时间复杂度prim算法适合稠密图，其时间复杂度为o(n^2)，其时间复杂度与边得数目无关，n为顶点数，而看ruskal算法的时间复杂度为o(eloge)跟边的数目有关，适合稀疏图。

三、数据结构的设计图采用类存储，定义如下：class graph{private:int *verticeslist; int **edge; int numvertices; int numedges; int maxvertices; graph(); ~graph(); bool insertvertex(const int vertex); bool insertedge(int v1,int v2,int cost); int getvertexpos(int vertex); int getvalue(int i); int getweight(int v1,int v2); int numberofvertices();1public:} void prim();其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。

作业1最小生成树的生成算法1.1算法应用背景在实际生活中, 图的最小花费生成树问题有着广泛的应用。

例如, 用图的顶点代表城市, 顶点与顶点之间的边代表城市之间的道路或通信线路, 用边的权代表道路的长度或通信线路的费用, 则最小花费生成树问题, 就表示为城市之间最短的道路或费用最小的通信线路问题。

其中普里姆算法是使用贪婪法策略设计的典型算法。

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

许多应用问题都是一个求无向连通图的最小生成树问题。

例如：要在n个城市之间铺设光缆, 主要目标是要使这n 个城市的任意两个之间都可以通信, 但铺设光缆的费用很高, 且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。

这就需要找到带权的最小生成树。

1.3算法描述1)最小生成树之普里姆算法描述:令G=(V,E,W), 为简单期间, 令顶点集为V={0,1,2…, n-1}。

假定与顶点i, j相关联的边为ei, j, ei, j的权用c[i][j]表示, T是最小花费生成树的边集。

这个算法维护两个顶点集合S 和N, 开始时: 令T=Ф,S={0},N=V-S。

然后, 进行贪婪选择, 选取i∈S, j∈N, 并且c[i][j]最小的i和j；并使S=S∪S{j},N=N-{j},T=T∪{ei, j}.重复上述步骤, 直到N为空, 或找到n-1条边为止。

此时, T中的边集, 就是所要求取的G中的最小花费生成树。

由此, 可描述普里姆算法的步骤如下:（1）T=Ф, S={0},N=V-S。

（2）如果N为空, 算法结束；否则, 转步骤（3）。

（3）寻找使i∈S, j∈N, 并且c[i][j]最小的i和j。

（4）S=S∪S{j},N=N-{j},T=T∪{ei, j}；转步骤（2）。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==prim算法实验报告篇一：Prim算法实验报告算法实验报告学院：xxx班级：xxx学号：xxx姓名：xxx Prim篇二：Prim最小生成树算法实验报告算法分析与设计之Prim学院：软件学院学号：201X21031059 姓名：吕吕一、问题描述1. Prim的定义Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。

(强调的是树，树是没有回路的)。

2. 实验目的选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。

二、算法分析与设计1.Prim算法的实现过程基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。

算法从U＝{u0}（u0∈V）、TE＝{}开始。

重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。

此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心:始终保持TE中的边集构成一棵生成树。

2.时间复杂度Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。

三、数据结构的设计图采用类存储，定义如下：class Graph{private:int *VerticesList; int **Edge; int numVertices; int numEdges; int maxVertices; Graph(); ~Graph(); bool insertVertex(const int vertex); bool insertEdge(int v1,int v2,int cost); int getVertexPos(int vertex); int getValue(int i); int getWeight(int v1,int v2); int NumberOfVertices();1public:} void Prim();其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。

实验三：Prim最小生成树（验证性、4学时）一、实验目的和要求●理解图的遍历●理解构造无向联通图的最小生成树的方法（Prim算法实现）●能用Prim算法构造最小生成树出来二、实验内容和原理⑴实验内容：用Prim算法构造一颗最小生成树(2) 实验原理：①从网中任一顶点开始，先把该顶点包含在生成树中，此时生成树只有一个顶点。

②找出一个端点在生成树中另一端点在生成树外的所有边，并把权值最小的边连到同它所关联的另一个顶点添加到生成树中；当有两条及以上具有相同最小权值的边可供选择时，任选一条。

③反复执行②，直到所有顶点都包含在生成树时为止。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）Turbo C 3.0四、算法描述及实验步骤1、描述从连通网中的某一定点开始，以此作为生成树的初始状态，然后不断地将网中的其他顶点添加到生成树上，知道最后一个顶点添加到生成树上是得到最小生成树。

一个无向连通网的生成树可能不是唯一的，当总代价一定是最小的。

2、算法流程图3、代码(注释)#include<stdio.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_NAME 5#define MAX_VERTEX_NUM 20 /*权的上限值*/typedef char Vertex[MAX_NAME];/*顶点名字串*/typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/ struct MGraph/*定义图*/{ Vertex vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum; };typedef struct{ Vertex adjvex; /*当前点*/int lowcost; /*代价*/}minside[MAX_VERTEX_NUM];int LocateVex(MGraph G,Vertex u)//定位{ int i;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;return -1; }void CreateGraph(MGraph &G){ int i,j,k,w;Vertex va,vb;printf("请输入无向网G的顶点数和边数(以空格为分隔)\n");scanf("%d %d",&G.vexnum,&G.arcnum);printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;++i) /* 构造顶点集*/scanf("%s",G.vexs[i]);for(i=0;i<G.vexnum;++i) /*初始化邻接矩阵*/for(j=0;j<G.vexnum;++j)G.arcs[i][j]=0x7fffffff;printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);for(k=0;k<G.arcnum;++k){ scanf("%s%s%d%*c",va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcs[i][j]=G.arcs[j][i]=w; } } /*对称*/int minimum(minside SZ,MGraph G){ int i=0,j,k,min;while(!SZ[i].lowcost)i++;min=SZ[i].lowcost; /*将最小权值记在min中*/k=i; /*把与边关联的生成树外的顶点序号记在k中*/for(j=i+1;j<G.vexnum;j++)if(SZ[j].lowcost>0&&min>SZ[j].lowcost){ min=SZ[j].lowcost;k=j; }return k; }void MiniSpanTree_PRIM(MGraph G,Vertex u){ int i,j,k;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;++j){ strcpy(closedge[j].adjvex,u);closedge[j].lowcost=G.arcs[k][j]; }closedge[k].lowcost=0; /*将顶点vk加入生成树中*/printf("最小代价生成树的各条边为:\n");for(i=1;i<G.vexnum;++i){ k=minimum(closedge,G);printf("(%s-%s)\n",closedge[k].adjvex,G.vexs[k]); /*输出最小边及权值*/closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost){ strcpy(closedge[j].adjvex,G.vexs[k]);closedge[j].lowcost=G.arcs[k][j]; } } } /*修改权值域*/int main(){ MGraph g;CreateGraph(g);MiniSpanTree_PRIM(g,g.vexs[0]);system("PAUSE");return 0; }五、调试过程(1)没有定位（2）没有定义最小生成树（3）j的如何取值，循环没有六、实验结果（1）实验数据1实验结果1实验数据2实验结果2七、总结（1）理解用prim算法构造无向联通图的最小生成树的方法；（2）对于如何能够求得最小生成树加深了了解；（3）熟悉的prim算法的构造最小生成树的思路和方法；并且能够运用prim算法构造出最小生成树。