离散数学--最小生成树实验报告 

一、实验目的：掌握图的存储表示和以及图的最小生成树算法。

二、实验内容：

1. 实现图的存储，并且读入图的内容。 2. 利用克鲁斯卡尔算法求网络的最小生成树。 3. 实现构造生成树过程中的连通分量抽象数据类型。 4. 以文本形式输出对应图的最小生成树各条边及权值。

三、实验要求：

1． 在上机前写出全部源程序； 2． 能在机器上正确运行程序； 3． 用户界面友好。

需求分析：

1、利用克鲁斯卡尔算法求网的最小生成树；

2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩阵以及按权排序后的边和最后得到的最小生成树；

克鲁斯卡尔算法：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，按

照构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有 n-1条边为止。 测试数据：

自行指定图进行运算

- 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) {

- 2 -

int i, j,n, m;

printf(\请输入边数和顶点数:\

scanf(\

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(\请输入有边的2个顶点\ scanf(\

while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) {

printf(\输入的数字不符合要求 请重新输入:\ scanf(\ }

G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar();

printf(\请输入%d与%d之间的权值:\ scanf(\ }

printf(\邻接矩阵为:\\n\

for ( i = 1; i <= G->vexnum; i++) {

for ( j = 1; j <= G->vexnum; j++)

- 3 -

{

printf(\ }

printf(\ } }

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].end, edges[i].weight);

} }

void Swapn(edge *edges,int i, int j) {

- 4 -

edges[i].begin,

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++; }

- 5 -