最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析).pdf

: .

定义。本程序可接受的最大顶点数为 20 个，没有连
接的点之间，用 100 表示其权值。
#include<iostream>
using namespace std;
#define MAX_VERTEX_NUM 20//最大顶点数
#define QM 100//最大值
#define OK 1
#define ERROR 0
int visited[MAX_VERTEX_NUM];
typedef int VertexType;
typedef int VRType;




2. 首先设计图的存储模块，即定义类型。本程序采用的图定义是无向图的定义
方式，存储模块采用邻接矩阵，便于查找。
typedef int VertexType;
typedef int VRType;

typedef struct ArcCell//邻接矩阵的值
{
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;




3. 在实现最小生成树算法时，定义辅助数组，进行判断遍历。
typedef struct
{VertexType adjvex;
VRType lowcost;
}closedge [MAX_VERTEX_NUM];




4. 最后生成最小生成树时，采用辅助数组进行结果的记录。
typedef struct
{
VertexType head;
VRType last;
int weight;
}result[MAX_VERTEX_NUM];




二：实现模块（函数）

1. 顶点查找函数，因为顶点的值和数组位置的下标不一定相等，所以加入顶
点查找函数，返回顶点的值，便于结果显示、区分指针与内容，使思路更
为清晰。
int LocateVex(MGraph &G,VertexType v)// 确定顶点位置
{
int k;
for(k=0;k<;k++)
{
if([k]==v)
return k;
}
return -1;// 没有这个顶点
}




2. 无向图的创建函数。
int CreateUDN(MGraph &G)// 创建无向图
{
int i,j,k;
int weight;VertexType v1,v2;
cout<<"输入无向图的顶点数和弧数:"<<endl;
cin>>>>;
for(i=0;i<;++i)
for(j=0;j<;++j)
G.