adt.h

利用克鲁斯卡尔算法求最小生成树

#include<stdlib.h>  //需要调用的头文件
#include<math.h>
#include <graphics.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include"Define.h"
# define pi 3.1416
# define MAX_VERTEX_NUM  30 //最大顶点个数   
typedef int TElemType;
typedef struct PTNode{   //双亲表示法结点结构
       TElemType data; 
       int  parent;
}PTNode;
typedef struct{        //双亲表示法树结构
       PTNode nodes[MAX_VERTEX_NUM];
       int  n;         //结点数
}PTree;
typedef PTree MFSet;
MFSet A;
typedef  struct Edge{//每条边的相关信息
       int  v;//每条边的两个顶点，无向图不区分始点和终点
       int  w; 
       int  weight;  //每条边的权值，不大于100
       int  flag;  //标记该边是否已经被遍历过
}Edge; 
typedef struct WebGraph{
Edge  E[100];  //边集
       int  V[MAX_VERTEX_NUM];  //顶点集
       int  m;  //边数
       int  n; //顶点数
}WebGraph;
WebGraph G,t;
void Initialization();
//系统初始化
int ReadCommand(int cmd);
//读入操作命令符,显示键入操作命令符的提示信息
void Interpret (int cmd);
//解释执行操作命令cmd
Status CreateWebGraph ( ); 
//构造一个无向网，并返回TRUE 
int  VisitWebGraph();
//遍历各个边，寻找其中权值最小的边。将该边的序号返回
WebGraph  K_MinTree();
//利用克鲁斯卡尔算法求最小生成树。将最小生成树返回
void OutputGraph(WebGraph T);
//将图G以图形的方式输出,返回TRUE
void OutputText(WebGraph T);
//将图G以以文本的方式输出,返回TRUE
Status Initial(MFSet *S,int v,int point[]);
//将n个顶点构造n个联通分量
int Find(MFSet S,int x);
//判断顶点x所在的连通分量并返回联通分量的值
Status Merge(MFSet *S,int i,int j);
//将两个连通分量合并。