实验七 克鲁斯卡算法生成最小树.doc

实验七图的应用---最小生成树问题
-----克鲁斯卡尔算法
一、实验目的
1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、掌握如何应用图解决各种实际问题。
[问题描述]
若要在n个城市之间建设通信网络,只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题。
[基本要求]
。
。
1
4
6 1
2
3

5
2
3 4
6
5
二、测试结果
最小生成树
1
4
1
2
3

5
2
3 4
6
5
程序代码
#include<>
#include<>
#define MAX_VERTEX_NUM 20
typedef int VertexType;
typedef int QElemType;
typedef int InfoType;
/****************************** 结构体部分****************************/
typedef struct ode
{
int adjvex; //该弧指向的顶点的位置
struct ode *nextarc; //指向下一条弧的指针
InfoType *info; //该弧相关信息指针
}ode;
typedef struct VNode
{
VertexType data; //顶点信息
ode *firstarc; //指向第一条依附于该顶点的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,um; //弧的顶点数和弧数
int kind; //弧的类型
}ALGraph;
typedef int VRType;
typedef struct
{
int begin,end;
VRType cost;
}EDGE;
/****************************** 函数操作部分****************************/
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].cost;
edges[i].cost=edges[j].cost;
edges[j].cost=temp;
}
void Sort(EDGE *edges,ALGraph G)
{
int i,j;
for(i=1;i<=;++i)
for(j=i;j<=