离散数学最小生成树实验
报告
The Standardization Office was revised on the afternoon of December 13, 2020
一、实验目的：掌握图的存储表示和以及图的最小生成树算法。
二、实验内容：
1.实现图的存储，并且读入图的内容。
2.利用克鲁斯卡尔算法求网络的最小生成树。
3.实现构造生成树过程中的连通分量抽象数据类型。
4.以文本形式输出对应图的最小生成树各条边及权值。
三、实验要求：
1．在上机前写出全部源程序；
2．能在机器上正确运行程序；
3．用户界面友好。
需求分析：
1、利用克鲁斯卡尔算法求网的最小生成树；
2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列；
3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩
阵以及按权排序后的边和最后得到的最小生成树；
克鲁斯卡尔算法：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有 n-1条边为止。
测试数据：
自行指定图进行运算
四、详细设计
源程序
#include<>
#include<>
#define M 20
#define MAX 20
typedef struct
{
int begin;
int end;
int weight;
}edge;
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;
void CreatGraph(MGraph *);
void sort(edge* ,MGraph *);
void MiniSpanTree(MGraph *);
int Find(int *, int );
void Swapn(edge *, int, int);
void CreatGraph(MGraph *G)
{
int i, j,n, m;
printf("请输入边数和顶点数:");
scanf("%d %d",&G->arcnum,&G->vexnum);
for (i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
for ( i = 1; i <= G->arcnum; i++)
{
printf("\n请输入有边的2个顶点");
scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) {
printf("输入的数字不符合要求请重新输入:");
scanf("%d%d",&n,&m);
}
G->arc[n][m].adj = G->arc[m][n].adj = 1;
getchar();
printf("\n请输入%d与%d之间的权值:", n, m);
scanf("%d",&G->arc[n][m].weight);
}
printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[],MGraph *G)
{
int i, j;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
void Swapn(edge *edges,int i, int j)
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void MiniSpanTree(MGraph *G)
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];
for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight; k++;
}
}
}
sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
int main(void)
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL)
{
printf("memory allcation failed,goodbye"); exit(1);
}
CreatGraph(G);
MiniSpanTree(G);
system("pause");
return 0;
}
运行结果:
五、实验总结（结果分析和体会）
在编程时，因为考虑的情况比较多，所以容易造成错误和遗漏，为了避免这些问题的出现，可以先用笔把所有的程序在纸上，然后再根据列表编写程序，这样不仅简单易懂，还避免了一些不必要的错误。
编写完程序后进行调试，发现有很多错误，其中也不乏一些基本的小错误，所以程序写完后进行静态检查是必不可少的，其次是逻辑上的错误，对于这些错误，只能再认真检查整个程序，这就要求我们在编程时考虑要周到，或者可以请其他同学帮忙检查。
通过这次对算术表达式求值的设计，让我自己对克鲁斯卡尔算法的运用更深刻，能够基本上很好的运用克鲁斯卡尔算法来解决一些问题。不过从中也发现了很多问题，那就是虽然课本知识的掌握还不错，但是上机编程的能力还有所匮乏，应该加强这方面的锻炼，通过上机的实践来提升对基础知识的理解。还有就是应该多和同学交流，比如一个相同的问题，我有我的编程思路，他有他的，通过相互的交流、讨教，可以获得更广的知识信息，开拓思维，自己不懂的通过咨询就可以掌握。