最小生成树prim算法实验报告

⑴ 构造可以使n个城市连接的最小生成树

/*普里姆算法构造最小生成树*/
#define MAXVEX 30
#define MAXCOST 1000
void prim(int c[MAXVEX][MAXVEX],int n)
/*己知图的顶点为{1,2,...,n},c[i][j]和c[j][i]为边(i,j)的权,打印最小生成树
的每条边*/
{
int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];;
for (i=2;i<=n;i++) /*从顶点1开始*/
{
lowcost[i]=c[1][i];
closest[i]=1;
}
closest[1]=0;
for (i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/
{
min=MAXCOST;
j=1;k=i;
while (j<=n)
{
if (lowcost[j]<min && closest[j]!=0)
{
min=lowcost[j];
k=j;
}
j++;
}
printf("(%d,%d) ",closest[k],k); /*打印边*/
closest[k]=0; /*k加入到U中*/
for (j=2;j<=n;j++)
if (closest[j]!=0 && c[k][j]<lowcost[j])
{
lowcost[j]=c[k][j];
closest[j]=k;
}
}
}
main()
{
int n=7,i,j,mx[MAXVEX][MAXVEX];
for (i=0;i<=n;i++)
for (j=0;j<=n;j++)
mx[i][j]=MAXCOST;
mx[1][2]=50;
mx[1][3]=60;
mx[2][4]=65;
mx[2][5]=40;
mx[3][4]=52;
mx[3][7]=45;
mx[4][5]=50;
mx[5][6]=70;
mx[4][6]=30;
mx[4][7]=42;
printf("最小生成树边集:\n ");
prim(mx,n);
}
数据结构导学上的，
/*克鲁斯卡尔算法构造最小生成树*/
#define MAXEDGE 30 /*MAXEDGE为最大的边数*/
struct edges /*边集类型,存储一条边的起始顶点bv、终止顶点tv和权w*/
{
int bv,tv,w;
};
typedef struct edges edgeset[MAXEDGE];
int seeks(int set[],int v)
{
int i=v;
while (set[i]>0) i=set[i];
return(i);
}
kruskal(edgeset ge,int n,int e)
/*ge表示的图是按权值从小到大排列的*/
{
int set[MAXEDGE],v1,v2,i,j;
for (i=1;i<=n;i++) set[i]=0; /*给set中的每个元素赋初值*/
i=1; /*i表示待获取的生成树中的边数,初值为1*/
j=1; /*j表示ge中的下标,初值为1*/
while (j<n && i<=e) /*按边权递增顺序,逐边检查该边是否应加入到生成树中*/
{
v1=seeks(set,ge[i].bv); /*确定顶点v所在的连通集*/
v2=seeks(set,ge[i].tv);
if (v1!=v2) /*当v1,v2不在同一顶点集合,确定该边应当选入生成树*/
{
printf("(%d,%d) ",ge[i].bv,ge[i].tv);
set[v1]=v2;
j++;
}
i++;
}
}
main()
{
int n=7,e=10;
edgeset mx;
mx[1].bv=4;mx[1].tv=6;mx[1].w=30;
mx[2].bv=2;mx[2].tv=5;mx[2].w=40;
mx[3].bv=4;mx[3].tv=7;mx[3].w=42;
mx[4].bv=3;mx[4].tv=7;mx[4].w=45;
mx[5].bv=1;mx[5].tv=2;mx[5].w=50;
mx[6].bv=4;mx[6].tv=5;mx[6].w=50;
mx[7].bv=3;mx[7].tv=4;mx[7].w=52;
mx[8].bv=1;mx[8].tv=3;mx[8].w=60;
mx[9].bv=2;mx[9].tv=4;mx[9].w=65;
mx[10].bv=5;mx[10].tv=6;mx[10].w=70;
printf("最小生成树边集:\n ");
kruskal(mx,n,e);
}


⑵ 根据Prim算法，求图示的最小代价生成树。 设①为起点，要求画出构造过程。

#include <iostream>
#include <iomanip>
using namespace std;

#define MAX_VERTEX_NUM 10 //最大顶点个数
#define INFINITY 1000 //定义最大值为1000
typedef char VerType;//定点向量
typedef int VRType;//定点之间的关系（即权值）
typedef struct
{
VerType vexs[MAX_VERTEX_NUM]; //顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}mgraph, * MGraph;
typedef struct
{
VerType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];//记录从顶点集U到V-U的代价最小的边的辅助数组定义

//初始化图
void init_mgraph(MGraph &g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=0;
g->arcnum=0;
for(int i=0;i<MAX_VERTEX_NUM;i++)
g->vexs[i]=0;
for(i=0;i<MAX_VERTEX_NUM;i++)
for(int j=0;j<MAX_VERTEX_NUM;j++)
g->arcs[i][j]=INFINITY;
}

void add_vexs(MGraph &g) //增加顶点
{
cout<<"请输入顶点的个数:"<<endl;
cin>>g->vexnum;
cout<<"请输入顶点的值"<<endl;
for(int i=0;i<g->vexnum;i++)
{
cin>>g->vexs[i];
}
}
void add_arcs(MGraph &g) //增加边
{
cout<<"请输入边的个数:"<<endl;
cin>>g->arcnum;
VerType ch1,ch2;
int weight;
int row,col;

for(int i=0;i<g->arcnum;i++)
{
cin>>ch1>>ch2>>weight;
for(int j=0;j<g->vexnum;j++)
{
if(g->vexs[j]==ch1)
{
row=j;
}
if(g->vexs[j]==ch2)
{
col=j;
}
}
g->arcs[row][col]=weight; //有向带权图只需把1改为weight
g->arcs[col][row]=weight;
}
}
void creat_mgraph(MGraph &g) //创建图
{
add_vexs(g); //增加顶点
add_arcs(g); //增加边
}

void print_mgraph(MGraph &g) //打印图
{
for(int i=0;i<g->vexnum;i++)
cout<<" "<<g->vexs[i]<<" ";
cout<<endl;
for(i=0;i<g->vexnum;i++)
{
cout<<g->vexs[i];
for(int j=0;j<g->vexnum;j++)
{
cout<<setw(5)<<g->arcs[i][j]<<" ";
}
cout<<endl;
}
}

//返回顶点v在顶点向量中的位置
int LocateVex(MGraph &g, VerType v)
{
int i;
for(i = 0; v != g->vexs[i] && i < g->vexnum; i++)
;
if(i >= g->vexnum)
return -1;
return i;
}
//求出T的下一个节点，第k节点
int minimun(MGraph &g, closedge closedge)
{
int min=INFINITY,k=0,i;
for(i=0;i<g->vexnum;i++)
{
if(closedge[i].lowcost != 0 && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
k = i;
}
}
return k;
}
//普里姆算法
void MiniSpanTree_Prim(MGraph &g, VerType u) //普里姆算法从顶点u出发构造G的最小生成树T，输出T的各条边。
{
closedge closedge;

int i,j;
int k=LocateVex(g,u);
for(j=0;j<g->vexnum;j++) //辅助数组初始化
{
if(j!=k)
{
closedge[j].adjvex=u;
closedge[j].lowcost=g->arcs[k][j];
}
}
closedge[k].lowcost = 0; //初始，U={u}

for(i=1;i<g->vexnum;i++) //选择其余g.vexnum-1个顶点
{
k=minimun(g,closedge); //求出T的下一个节点，第k节点
cout<<closedge[k].adjvex<<" "<<g->vexs[k]<<" "<<closedge[k].lowcost<<endl; //输出生成树的边
closedge[k].lowcost=0; //第k顶点并入U集

for(j=0;j<g->vexnum;j++)
{
if(g->arcs[k][j] < closedge[j].lowcost) //新顶点并入集后，选择新的边，将小的边放到辅助数组中
{
closedge[j].adjvex = g->vexs[k];
closedge[j].lowcost = g->arcs[k][j];
}
}
}
}//MiniSpanTree_Prim

int main()
{
MGraph G;
init_mgraph(G); //初始化图
creat_mgraph(G); //创建图
print_mgraph(G); //打印图
MiniSpanTree_Prim(G,G->vexs[0]); //最小生成树

return 0;
}

⑶ 用普里姆算法求最小生成树（C++）

求最小生成树的谱里姆算法
#include <iostream>
using namespace std;

const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};

class tree
{public :
int s[n+1][n+1];
edgeset ct[n+1];

void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i<n;i++)
{t.ct[i].front=1;
t.ct[i].end=i+1;
t.ct[i].weight=t.s[1][i+1];}

for(k=2;k<=n;k++)
{min=32767;
m=k-1;

for(j=k-1;j<n;j++)
if(t.ct[j].weight<min)
{min=t.ct[j].weight;
m=j;}
edgeset temp=t.ct[k-1];
t.ct[k-1]=t.ct[m];
t.ct[m]=temp;
j=t.ct[k-1].end;
for(i=k;i<n;i++)
{t1=t.ct[i].end;
w=t.s[j][t1];
if(w<t.ct[i].weight)
{t.ct[i].weight=w;
t.ct[i].front=j;}}}}
};

void main ()
{int j,w;tree t;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j)t.s[i][j]=0;
else t.s[i][j]=32767;

for(int k=1;k<=e;k++)
{cout<<"输入一条边及边上的权值 ";
cin>>i>>j>>w;
cout<<endl;
t.s[i][j]=w;
t.s[j][i]=w;}

t.prim(t);
for(i=1;i<n;i++)
{cout<<t.ct[i].front<<" "<<t.ct[i].end<<" "<<t.ct[i].weight<<endl;}
}
我们的实验上机做了的
运行结果
输入一条边及边上的权值 1 2 6

输入一条边及边上的权值 1 3 1

输入一条边及边上的权值 1 4 6

输入一条边及边上的权值 2 3 5

输入一条边及边上的权值 2 5 3

输入一条边及边上的权值 3 4 7

输入一条边及边上的权值 3 5 5

输入一条边及边上的权值 3 6 4

输入一条边及边上的权值 4 6 2

输入一条边及边上的权值 5 6 6

1 3 1
3 6 4
6 4 2
3 5 5
5 2 3
Press any key to continue
你有的图不一样就该顶点和边就是
const int n=6;
const int e=10;

⑷ 关于PRIM算法求最小生成树的问题（c语言版）

/*
邻接矩阵存储图
测试数据
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
*/

#include <stdio.h>
#include <limits.h>
#define N 100

int p[N], key[N], tb[N][N];

void prim(int v, int n)
{
int i, j;
int min;

for (i = 1; i <= n; i++)
{
p[i] = v;
key[i] = tb[v][i];
}
key[v] = 0;
for (i = 2; i <= n; i++)
{
min = INT_MAX;
for (j = 1; j <= n; j++)
if (key[j] > 0 && key[j] < min)
{
v = j;
min = key[j];
}
printf("%d%d ", p[v], v);
key[v] = 0;
for (j = 1; j <= n; j++)
if (tb[v][j] < key[j])
p[j] = v, key[j] = tb[v][j];
}
}

int main()
{
int n, m;
int i, j;
int u, v, w;
while (scanf("%d%d", &n, &m))
{
for(i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
tb[i][j] = INT_MAX;
}

while (m--)
{
scanf("%d%d%d", &u, &v, &w);
tb[u][v] = tb[v][u] = w;
}
prim(1, n);
printf("\n");
}
return 0;
}

要求出所有的最小生成树。。貌似有点麻烦。。

⑸ 贪心算法之prim算法的证明

令 为一个带权连通图，T为G的一生成树。对任一不在T中的边 ，如果将 加入T中, 产生一条回路，且 是回路中权值最大的边,那么树T具有MST性质。
引理1：如果生成树 都具有MST性质，那他们的总代价相同。
proof （采用归纳法）：假设 有k条边不相同，下面对k进行归纳：

引理2：生成树T为最小生成树 T具有MST性质
proof:

设边 加入T以后产生回路，且回路中存在边 ,则我们将 删除，得到新的生成树 ，则有 , 这与T是最小生成树矛盾，因此 是回路中权重最大的边。

不妨设 是最小生成树，由必要性证明知 有MST性质，再由引理1知道 和 总代价相同，则 也是最小生成树。

proof（反证）:
假设构造的生成树为 ，且不具有MST性质，不妨设 E(G)-E(T) ，即不在T中的、最小的一条边，将 加入T中形成一个环，由于T不具有MST性质，则环中一定存在一条边 ，且 ，接下来分情况讨论：

综上所述，prim算法产生的生成树具有MST性质。

⑹ 利用PRIM算法生成最小生成树

普里姆算法. 普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的（假设为 A 类），剩下的是另一类（假设为 B 类）。. 对于给定的连通网，起始状态全部顶点都归为 B 类。. 在找最小生成树时，选定任意一个顶点作为起始点，并将之从 B 类移至 A 类；然后找出 B 类中到 A 类中的顶点之间权值最小的顶点，将之从 B 类移至 A 类，如此重复，直到 B 类中没有顶点为止。. 所走过的顶点和边就是该连通图的最小生成树

⑺ Prim算法的实现过程

G=（V,E）
①初始化：读入的数据用邻接矩阵x存储，一个一维布尔型数组chosen，记录第i个节点是否已选，初始值除1外全部设为false，记录权值的变量cost赋值为0；
以下②到④循环执行v-1次（每次生成一条边，运行（点的个数减1）次后，生成一棵最小生成树）：
②临时变量p赋值为无限大，用于记录当前最小值；
③二重循环（外循环i，内循环j）扫描邻接矩阵：如果chosen[i]=true（也就是说第i个点已选），那么扫描x[i]，如果not(chosen[j])（也就是说第j个点未选），那么如果x[i,j]<p，那么p赋值为x[i,j],临时变量q赋值为j;
④把cost赋值为cost+o，把chosen[q]赋值为true（也就是说第j个点已选）；
⑤输出cost。

一、以上给出具体的运行过程。这个算法的策略就是贪心，和dijkstra差不多，每次都选择未选的边中权值最小的那一条，直到生成最小生成树。用chosen的目的就是保证生成过程中没有环出现，也就是说保证选择的边不会通向一个已经包含在生成树中的点。
二、这个只输出最小生成树的每条边权值之和，如果要输出整棵最小生成树，加一个[1..n,1..2]的数组，在第④步的时候把每次选的边记录下来就可以了。
三、用小顶堆在第③步优化一下的话就不用每次都扫描那么多边了，只不过建堆维护堆代码写起来很麻烦。
四、prim适合用于比较稠密的网，点数和边数差不多的时候效率很恶心，一般都用kruskal。

⑻ 已知图G如下所示，根据Prim算法，构造最小生成树。（要求给出生成过程）

①将带权连通图G=的各边按权从小到大依次排列，如e1,e2,…,em,其中e1的权最小，em的权最大，m为边数。 ②取权最小的两条边构成边集T0，即T0={e1,e2},从e3起，按次序逐个将各边加进集合T0中去，若出现回路则将这条边排除（不加进去），按此法一直进行到em，最后得到n-1条边的集合T0={e1,e2,…,en-1}，则T0导出的子图就是图G的最小生成树。

⑼ 利用Prim（普里姆）算法 构造最小生成树 程序

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}