实验1采用普里姆(prim)算法构造网络的最小生成树
1、实验目的：深入理解虽小生成树的概念，熟练掌握普里姆(prim)算法的工作过程，并通过定
义合适的数据结构，采用C语言程序实现。
2、实验内容：根据模板程序编制普里姆算法的程序，在计算机中进行调试，同时寻找两个结
点大于6的网络，利用文件读入其邻接矩阵，运行程序。
记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。
要求从文本文件中读入网络的邻接矩阵。
3、实验原理
①prim算法的主要步骤
②数据表示
③算法实現细节
4、实验步骤与实验结果
①编写prim算法的C语言程序
②输入计算机进行调试
③准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。
实验结果：
①画出网络图，写出相应的邻接矩阵
②记录程序的运行结果，根据结果画岀最小生成树并写出最小生成树的权值。
附录：程序模板
# i ncIude <stdio. h>
/*定义一个结构体，用于记录一条边的始点与终点*/
typedef struct pp
{
int p.q；
} edge;
int g[100] [100]. u[100], v[100], vexnum:
edge p[100];//用于记录最小生成树的各条边
void input()〃读入图的邻接矩阵
(
int i. j. temp;
FILE *fp;
fp=fopen("pp5. txt", "r");
fscanf (fp. "%d". &vexnum);
for (i=1 ： i <=vexnwn: i ++)
I
printf("\n");
for (j=1; j<=vexniHn： j++)
{
fscanf (fp. "%d". &temp):
g[i] [j]=temp：
pr intf ("%d ", temp):
}
}
fclose(fp);
}
mainO
{
int i. j. k. m. n. ma. s=0;
inputO：//输入数据
for (i=1; i<=vexnum; i++)〃集合V中包含了所有顶点
v[i]=1;
u[1]=1：v[1]=0：//第1个节点加入至集合U中，并从集合V中去掉
for (i=1; i<=vexnum-1; i++)//最多需vexnum-1 条边
I
//以下找连接节点集U至节点集V的最小边
ma=1000;//ma存放最小边的权值
for (j=1：j<=i：j++)〃集合U中的第j个节点，其编号为u[j].每次增加一个, 共有i个for (k=1;k<=vexnum:k++)
/*v[k]!=0表示节点k在集合V中；g[u[j] [k]>0表示有边*/
if (v[k] !=0&&ma>g[u[j]] [k]&&g[u[j]J [k]>0)
{
ma=g[u[j]][k]：〃保存最小边值m=u[j];//最小边的始点编号n=k：//最
小边的终点编号
}
s=s+ma：// 求和
u[i+1]=n;v[n]=0：//ffi找到最小边的终点编号从V中去掉，并加入至U中p[i].p=m；
p[i].q=n;//«存最小边的始点编号与终点编号
printf ("\n");
for (i=1;i<=vexnum-1;i++)
printf C\n%d %d %d", p[i]. p. p[i]. q, g[p[i].p] [p[i]. ql): pr i ntf ("\nsum=%d\n\n", s);
实验2采用克鲁斯卡尔(kruskal)算法构造网络的最小生成树
1、实验目的：深入理解最小生成树的概念，熟练掌握克鲁斯E尔(kruskal)算法的工作过程，并
通过定义合适的数据结构.采用C语言程序实现。
2、实验内容：根据模板程序编制克魯斯卡你算法的程序，在计算机中进行调试，同时寻找两
个结点大于6的网络，利用文件读入其邻接矩阵，运行程序。
记录运行结果，并把运行结果与手工生成的结果进行比较，验证程序的正解性。
要求从文本文件中读入网络的邻接矩阵。
3、实验原理
①克鲁斯卡你算法的主要步骤
②数据表示
③算法实現细节
4、实验步骤与实验结果
①编写kruskal算法的C语言程序
②输入计算机进行调试
③准备两个顶点大于6的网络，把网络的邻接矩阵输入文本文件中，运行程序，记录程序的运行结果，根据结果画出最小生成树，并与手工生成的最小生成树进行比较。
实验结果：
①画出网络图，写出相应的邻接矩阵
②记录程序的运行结果，根据结果画出最小生成树并写出最小生成树的权值。
附录：程序模板
# i ncIude <stdio. h>
typedef struct pp//定义最小生成树连的结构
{
int p. q. r ;//顶点1,顶点2,权值
} edge：
int g[100] [100]. sort[100]. vexnum：//定义图的邻接矩阵，集合，顶点数edge p[100]. temp; void input()〃读入图的邻接矩阵
{
int i. j. temp;
FILE *fp;
fp=fopenCpp5. txt", "r"):
fscanf (fp. "%d", &vexnum);
for (i=1;i<=vexnum;i++)
I
printf("\n");
for (j=1;j<=vexnum:j++)
{
fscanf (fp. "%d". &temp);
g[i] [j]=temp;
pr intf ("%d temp):
}
}
fclose(fp);
}
ma i n ()
(
int i. j. k. I. m. sum=0;
l=0：
input () ；//从文件读入邻接矩阵
for (i=1：i<=vexnum;i++)〃初始时，每一顶点属于一个集合sort[i]=i;
for (i=1; i<=vexnum-1; i卄)//把边存入p 数组
for (j=i+1;j<=vexnum：j++)
if (g[i][j]>0)
I++；
p[l].p=i:p[l].q=j：p[U. r=g[i] [j]:
1
for (i=1;i<l;i++)//对边按权值进行排序
I
k=i;m=p[k]. r;
for (j=i+1：j<=l；j++)
if (m>p[jj. r)
{
m=p[j]. r;
k=j；
}
temp=p[i]；
p[i]=p[k]；
p[k]=temp;
k=1;i=1;
whi I e (k<vexnwn)
I
if(sort[p[i].p]!=sort[p[i].q])//同一条边的两个节点分别属于两个集合
{
l=sort[p[i].q]：//另一节点的集合号
printf C\n%d %d %d". p[i]. p. p[i]. q. p[i]. r) ：//选择这条边
sum=sum+p[i]. r;
for (j=1: j<=vexnum; j++)//把所有集合号为I的节点加于至第一个节点所在的集合中
if (sort[j]=l) sort[j]=sort[p[i]. p]:
k++;
}
pr i ntf ("\nsum=%d\n". sum):。