学步园

 最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n－1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权最小!

头文件Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#define MAXVEX 12
#define INFINITY 65535
typedef char VertexType; //顶点数据类型
typedef int EdgeType; //边表的权值类型
typedef struct graph{
	VertexType data[MAXVEX]; //图的顶点
	EdgeType Edge[MAXVEX][MAXVEX]; //图的边表
	int NumVertex,NumEdge; //图的顶点数与边数
}Graph;
void CreateGraph(Graph *G); //创建图
void MiniSpanTree_Prim(Graph *G); //最小生成树普利姆算法
#endif //GRAPH_H

实现文件Graph.h

#include "Graph.h"
#include <stdio.h>
void CreateGraph(Graph *G) //创建图
{
	printf("请输入图的顶点数和边数:\n");
	scanf("%d%d",&G->NumVertex,&G->NumEdge);
	printf("请输入图的顶点信息:\n");
	for(int i = 0;i < G->NumVertex;++i)
	{
		fflush(stdin); //清空输入缓冲区，为了确保不影响后面的数据读取
		scanf("%c",&G->data[i]); //输入顶点的信息
	}
	for(int i = 0;i < G->NumVertex;++i)  //初始化图的权值为无限大
		for(int j = 0;j < G->NumEdge;++j)
			G->Edge[i][j] = INFINITY;
	for(int k = 0;k < G->NumEdge;++k)
	{
		int i,j,w;
		printf("请输入边的连接信息(vi,vj)和边的权值:\n");
		fflush(stdin);
		scanf("%d%d%d",&i,&j,&w);
		G->Edge[i][j] = w; //边的权值
		G->Edge[j][i] = G->Edge[i][j]; //无向图存在反向链接,边的权值相同
	}
}
void MiniSpanTree_Prim(Graph *G)
{
	int adjVex[MAXVEX]; //存放顶点的下标值
	EdgeType lowcost[MAXVEX]; //存放最小的权值
	adjVex[0] = 0; //选取下标为0的一个顶点
	lowcost[0] = 0; //表标此顶点已经被处理过
	for(int i = 1;i < G->NumVertex;++i)
	{
		lowcost[i] = G->Edge[0][i]; //将与下标为零的顶点邻接的边权值存放在lowcost中
		adjVex[i] = 0;   //全部初始化为零
	}
	for(int i = 1;i < G->NumVertex;++i)
	{
		int min = INFINITY; //初始化最小值为无限大
		int k = 0; //用于记录权值最小的顶点的下标值
		for(int j = 1;j < G->NumVertex;++j)
		{
			if(lowcost[j] != 0 && lowcost[j] < min) //如果顶点没有处理过而且权值小于最小值
			{
				min = lowcost[j]; //把权值赋给min
				k = j; //记录当前最小权值的顶点的下标
			}
		}
		lowcost[k] = 0; //下标为k的顶点已处理
		printf("(%d %d)\n",adjVex[k],k);
		for(int j = 1;j < G->NumVertex;++j) //循环所有顶点
		{
			if(lowcost[j] != 0 && G->Edge[k][j] < lowcost[j]) //如果当前顶点的权值小于此前未被加入生成树的顶点权值 
			{
				lowcost[j] = G->Edge[k][j]; //将较小的权值存入lowcost的相应位置
				adjVex[j] = k;		//记录下顶点的下标
			}
		}
	}
}

测试文件:main.cpp

#include "Graph.h"
int main()
{
	Graph G;
	CreateGraph(&G);
	MiniSpanTree_Prim(&G);
	return 0;
}