最小生成树算法实验报告.docx

作业1最小生成树的生成算法

在实际生活中，图的最小花费生成树问题有着广泛的应用。例如，用图的顶点代表城市， 顶点与顶点之间的边代表城市之间的道路或通信线路，用边的权代表道路的长度或通信线路 的费用，则最小花费生成树问最小，并令，S'=SU{j}， T'=TU{e}，G'=(S',T')。
此时，有：
G'是树。因为e只和S中的一个顶点关联，加入后不会使G'构成回路，且G' 仍然连通。
G'是G的最小代价生成树的子树。
因为，如果eET*，这个结论成立；如果eET*，那么，与e关联的顶点，必是T* 中两个不相邻接的顶点，根据性质4， T* U{e}将包含回路。
e是回路的一条边，且，e=(i,j)， iES，jE N。则回路中必存在另一条边， e'=(x,y)，xES，yE N。按算法的选择，e的权小于或等于e'的权。令T**=T*U{e}- {e'}。 则T**的权小于或等于T*的权。
若T**的权小于T*的权，与T*是最小代价生成树的边集相矛盾，所以，eET* ；若 T**的权等于T*的权，这时，用新的T*来标记T**。
在这两种情况下，都有e1ET*。
综上所述T=T*，普里姆算法所产生的生成树是的最小代价生成树。


int v,e;
int i,j;
int x=1;
int start,end;
float distance;
printf(-请输入连通带权图的顶点数和边数：")
while(scanf("%d%d”,&v,&e))
{
printf("\n ");
for(i=1;i<=v;i++)
{
#include ""
#define true 1
#define false 0
float int_max=0x7fff,graph[100][100];
int neig[100],key_point[100];
int s[100];// 集合 s
void prim(int end,int v);
int main()
{
for(j=1;j<=v;j++)
graph[i][j]=int_max;
}
printf("\n请输A%d条边的起点和终点，以及 权值。\n",e);
printf("\n \n");
while(e--)
{
printf("第％d条边的起点：终点：权值”,x);
scanf("%d%d%f”,&start,&end,&distance);
graph[start][end]=graph[end][start]=distance;
x=x+1;
}
printf("\n \n");
prim(1,v);
printf("\n");
}
return 0;
}
void prim(int end,int v)
{
int i,j;
float min;
s[1]=true;//s={1}
for(i=2;i<=v;i++)
{
neig[i]=end;//顶点i的近邻
key_point[i]=graph[end][i];// 顶点i 的与近邻的 关联边的权值
s[i]=false;
}
key_poin