最小生成树

来源：百度知道 编辑：UC知道 时间：2024/05/27 13:31:41
在n各城市间建设通讯网络，用最小成本架设线路。
要求建立N个城市间通信网络；
增加删除城市节点；
遍历通信网络中的各个城市节点；
求最小生成树，输出各节点及边上的权值。

tt

//课设题目：最小生成树--克鲁斯卡尔算法的实现
#include <stdio.h>
#include<iostream.h>
#define MAX_VERTEX_NUM 10 //图的顶点数，应由用户定义
#define INFINITY 1000 /*设无穷大为1000*/

typedef struct Edge
{
int weight;
}Edge, EdgeMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//连通网的带权邻接矩阵,作为kruskal算法的输入

typedef struct MGraph //存放G的最小生成树，作为Prim算法的输出
{
EdgeMatrix edges;
int vexnum;
int edgenum;
}MGraph;

typedef struct VexGroup
{
int vertex;
int group;
}VexGroup;

typedef struct EdgeMuster
{
int tail; //边的起点和终点
int head;
int weight; //边上的权
bool used;
}EdgeMuster;

void InitializeMG(MGraph &G)
{
G.edgenum = G.vexnum = 0;
for(int i = 0; i < MAX_VERTEX_NUM; ++i)
for(int j = 0; j < MAX_VERTEX_NUM; ++j)
G.edges