编写程序输出该无向网络的最小生成树以及该最小生成树的所有边。

编写程序输出该无向网络的最小生成树以及该最小生成树的所有边。

#include
#define MaxInt 1000			//定义无穷大，这里设置一个比所有边的权值都大的数9
#define MVNum 100
typedef char VerTexType;    //顶点类型
typedef int ArcType;		//边权值类型

//邻接矩阵的存储结构
typedef struct Graph
{
	VerTexType vexs[MVNum];				//顶点表
	ArcType arcs[MVNum][MVNum];			//邻接矩阵
	int vexnum, arcnum;					//图的当前点数和边数
}AMGraph;

//最小生成树普里姆算法定义
//辅助数组
typedef struct closeg
{
	VerTexType adjvex;
	ArcType lowcost;
}closedge[MVNum];

//函数声明
void printGraph(AMGraph G);
int LocateVex(AMGraph G, char v);
int Min(closedge C, AMGraph G);


//创建无向网
void CreateUDN(AMGraph &G)
{
	G.vexnum = 7;						//输入总顶点数和边数
	G.arcnum = 9;
	G.vexs[0] = 'v0';					//输入顶点信息
	G.vexs[1] = 'v1';
	G.vexs[2] = 'v2';
	G.vexs[3] = 'v3';
	G.vexs[4] = 'v4';
	G.vexs[5] = 'v5';
	G.vexs[6] = 'v6';

	//初始化邻接矩阵为极大值
	for (int i = 0; i < G.vexnum; i++)			
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = MaxInt;
		}
	}

	//建立边
	int i, j;
	i = LocateVex(G, 'v0');
	j = LocateVex(G, 'v1');
	G.arcs[i][j] = G.arcs[j][i] = 8;
	i = LocateVex(G, 'v0');
	j = LocateVex(G, 'v3');
	G.arcs[i][j] = G.arcs[j][i] = 3;
	i = LocateVex(G, 'v1');
	j = LocateVex(G, 'v3');
	G.arcs[i][j] = G.arcs[j][i] = 3;
	i = LocateVex(G, 'v1');
	j = LocateVex(G, 'v2');
	G.arcs[i][j] = G.arcs[j][i] = 12;
	i = LocateVex(G, 'v1');
	j = LocateVex(G, 'v4');
	G.arcs[i][j] = G.arcs[j][i] = 10;
	i = LocateVex(G, 'v2');
	j = LocateVex(G, 'v4');
	G.arcs[i][j] = G.arcs[j][i] = 6;
	i = LocateVex(G, 'v2');
	j = LocateVex(G, 'v5');
	G.arcs[i][j] = G.arcs[j][i] = 2;
	i = LocateVex(G, 'v3');
	j = LocateVex(G, 'v6');
	G.arcs[i][j] = G.arcs[j][i] = 15;
	i = LocateVex(G, 'v3');
	j = LocateVex(G, 'v5');
	G.arcs[i][j] = G.arcs[j][i] = 7;
	i = LocateVex(G, 'v4');
	j = LocateVex(G, 'v5');
	G.arcs[i][j] = G.arcs[j][i] = 9;
	printGraph(G);
}


//查找指定顶点的数组下标，并返回
int LocateVex(AMGraph G, char v)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (G.vexs[i] == v)
		{
			return i;
		}
	}
}

//打印输出图
void printGraph(AMGraph G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		printf("v%d :", i + 1);

		for (int j = 0; j < G.vexnum; j++)
		{
			printf("%d ", G.arcs[i][j]);
		}
		printf("n");
	}
}


//邻接矩阵深度优先遍历
bool visited[MVNum];
void DFS_AM(AMGraph G, int v)
{
	printf("v%c->", G.vexs[v]);
	visited[v] = true;
	for (int w = 0; w < G.vexnum; w++)
	{
		if ((G.arcs[v][w]) != 0 && (!visited[w]))
		{
			DFS_AM(G, w);
		}
	}
}

//最小生成树普里姆算法
void MiniSpanTree_Prim(AMGraph G, VerTexType u, closedge C)
{
	int k = LocateVex(G, u);			//获取起始顶点的数组下标
	for (int j = 0; j < G.vexnum; ++j)	//初始化普里姆算法的辅助数组
	{
		if (j != k)
		{
			C[j].adjvex = u;					//顶点
			C[j].lowcost = G.arcs[k][j];		//该顶点到各顶点的权值
		}
	}
	C[k].lowcost = 0;							//把已加入点集合的权值置为0
	printf("n======================n");
	printf("最小生成树构造顺序：");

	for (int i = 1; i < G.vexnum; ++i)
	{
		k = Min(C, G);			//选择最小的权值的顶点，并返回下标存入k中

		char u0 = C[k].adjvex;	//之前加入的顶点
		char v0 = G.vexs[k];	//要加入的顶点
		printf("nv%c -> v%c", u0, v0);	//输出选择
		C[k].lowcost = 0;

		//如果新加入的顶点到某个顶点的权值有比之前更小的，则更新辅助数组
		for (int j = 0; j < G.vexnum; ++j)
		{
			if (G.arcs[k][j]					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691000.html