Kruskal最小生成树-白红宇

Kruskal最小生成树

阅读量：359 次

发布时间：2019-03-04

本文共 6587 字，大约阅读时间需要 21 分钟。

城市间道路铺设问题实验

#define _CRT_SECURE_NO_WARNINGS#include
   
    #include
    
     //图的邻接矩阵表示法#define MaxVertexNum 100 /*最大顶点个数设为100*/#define INFINITY 65535 /*∞设为双字节无符号整数的最大值65535*/typedef int Vertex;//用顶点下标表示顶点为整型typedef int WeightType;//边的权值设为整型typedef char DataType;//顶点存储的数据类型设为字符型//边的定义typedef struct ENode* PtrToENode;struct ENode {   	Vertex V1;	Vertex V2;//有向边
     
      	WeightType Weight;};typedef PtrToENode Edge;//图的邻接表示表示法typedef struct AdjVNode* PtrToAdjVNode;struct AdjVNode {   	Vertex AdjV;//邻接点下标	WeightType Weight;//边权重	PtrToAdjVNode Next;//指向下一个邻接点的指针};//顶点表头结点的定义typedef struct VNode* AdjList;//AdjList是邻接表类型struct VNode {   	PtrToAdjVNode FirstEdge;//边表头指针	DataType Data;//存顶点的数据	//注意：很多情况下，顶点无数据，};//图结点的定义typedef struct GNode2* PtrToGNode2;struct GNode2 {   	int Nv;//顶点数	int Ne;//边数	AdjList G;//邻接表};typedef PtrToGNode2 LGraph;//以邻接表方式存储的图类型typedef Vertex ElementType;typedef Vertex SetName;typedef ElementType* SetType;//并查集中，下标是根结点序号的元素会记录成负数，其绝对值是整个集合包含元素的个数										//下标记录该结点序号，值记录父结点的序号void InitializeVSet(SetType S, int N);//将集合初始化为-1void Union(SetType S, SetName Root1, SetName Root2);//并集SetName Find(SetType S, ElementType X);//查集int CheckCycle(SetType VSet, Vertex V1, Vertex V2);//检查是否发生了连通情况void PercDown(Edge ESet, int p, int N);//以p位置为堆顶将此堆顶以下转换成为小顶堆void InitializeESet(LGraph Graph, Edge ESet);//将边数组制作成小顶堆int GetEdge(Edge ESet, int CurrentSize);//取出小顶堆中堆顶，将剩余的堆重新制成小顶堆int Kruskal(LGraph Graph);//最小生成树算法LGraph CreateGraph2(int VertexNum);//创建一个空邻接表void InsertEdge2(LGraph Graph, Edge E);//将边插入领接表LGraph BuidGraph2(void);//根据输入数据制作一个领接表void Print_LGraph(LGraph G);//将邻接表输出int main(void){   	LGraph Graph;	int TotalWeight;	Graph = BuidGraph2();//建立一个图	TotalWeight = Kruskal(Graph);//建立一个最小生成树，并在Kruskal树输出	printf("\n总权重为%d", TotalWeight);	return 0;}//创建图LGraph CreateGraph2(int VertexNum){   	//初始化一个有VertexNum个顶点的但没有边的图	Vertex V;	LGraph Graph;	Graph = (LGraph)malloc(sizeof(struct GNode2));	Graph->Nv = VertexNum;	Graph->Ne = 0;	Graph->G = (AdjList)malloc(sizeof(struct VNode) * MaxVertexNum);	//初始化邻接表头指针	//注意：这里默认的顶点的编号从0开始，到（Gragh->Nv-1)	for (V = 0; V < Graph->Nv; V++)		Graph->G[V].FirstEdge = NULL;	return Graph;}void InsertEdge2(LGraph Graph, Edge E){   	PtrToAdjVNode NewNode;	//插入边（V1，V2）	//为V2建立一个新的邻接点	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));	NewNode->AdjV = E->V1;	NewNode->Weight = E->Weight;	//将V2插入V1的表头	NewNode->Next = Graph->G[E->V2].FirstEdge;	Graph->G[E->V2].FirstEdge = NewNode;	//若是无向图，还要插入边
      
       	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));	NewNode->AdjV = E->V2;	NewNode->Weight = E->Weight;	//将V1插入V2的表头	NewNode->Next = Graph->G[E->V1].FirstEdge;	Graph->G[E->V1].FirstEdge = NewNode;}LGraph BuidGraph2(void){   	LGraph Graph;	Edge E;	int Nv;	int i;	printf("输入顶点个数\n");	scanf("%d", &Nv);//读入顶点个数	Graph = CreateGraph2(Nv);//初始化有Nv个顶点但是没有边的图	printf("输入边数\n");	scanf("%d", &(Graph->Ne));//读入边数	if (Graph->Ne != 0) {   		E = (Edge)malloc(sizeof(struct ENode));//建立边结点		//读入边，格式为 起点，终点，权重，插入邻接表		for (i = 0; i < Graph->Ne; i++) {   			printf("输入起点 终点 权重\n");			scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);			//注意，如果权重不是整型，Weight的读入格式要改			InsertEdge2(Graph, E);		}	}	//如果顶点有数据的话，读入数据	//for (V = 0; V < Graph->Nv; V++)		//scanf("%c", &(Graph->G[V].Data));	return Graph;}void InitializeVSet(SetType S, int N){   	//初始化并查集	ElementType X;	for (X = 0; X < N; X++)		S[X] = -1;}void Union(SetType S, SetName Root1, SetName Root2){   	//这里默认Root1和Root2是不同的集合的根结点	//保证小集合并入大集合	if (S[Root2] < S[Root1]) {   //如果集合2比较大		S[Root2] += S[Root1];		S[Root1] = Root2;	}	else {   		S[Root1] += S[Root2];		S[Root2] = Root1;	}}SetName Find(SetType S, ElementType X)//会返回X所在集合的根结点{   	//默认集合元素全部初始化为-1	if (S[X] < 0)//找到集合的根		return X;	else//将所有属于这个根结点所有子结点都直接指向根结点		return S[X] = Find(S, S[X]);//路径压缩，S[X]是X的父结点；递归的意义为，若S[X]找到的尚且不是根结点则，去找S[X]的父结点}int CheckCycle(SetType VSet, Vertex V1, Vertex V2){   	//检查连接V1，和V2的边是否在现有的最小生成树子集中构成回路	Vertex Root1;	Vertex Root2;	Root1 = Find(VSet, V1);	Root2 = Find(VSet, V2);	if (Root1 == Root2)//若V1和V2已经连通，则该边不能要		return 0;	else {   //否则改变可以被收集，同时将V1，V2并入同一连通集		Union(VSet, Root1, Root2);		return 1;	}}//边的最小堆定义void PercDown(Edge ESet, int p, int N){   	//将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆	int Parent;	int Child;	struct ENode X;	X = ESet[p];//取出根结点存放的值	for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {   		Child = Parent * 2 + 1;		if ((Child != N - 1) && (ESet[Child].Weight > ESet[Child + 1].Weight))			Child++;		if (X.Weight <= ESet[Child].Weight)			break;//找到了合适的位置		else//下滤			ESet[Parent] = ESet[Child];	}	ESet[Parent] = X;}void InitializeESet(LGraph Graph, Edge ESet){   	//将图的边存入数组ESet,并且初始化最小堆	Vertex V;	PtrToAdjVNode W;	int ECount;	//将图的边存入数组ESet	ECount = 0;	for (V = 0; V < Graph->Nv; V++) {   		for (W = Graph->G[V].FirstEdge; W; W = W->Next)			if (V < W->AdjV) {   //避免重复录入无向图的边，只收V1
       
        AdjV;				ESet[ECount++].Weight = W->Weight;			}		//初始化为最小堆	}	for (ECount = Graph->Ne / 2; ECount >= 0; ECount--)		PercDown(ESet, ECount, Graph->Ne);}void Swap(Edge a, Edge b){   	struct ENode Temp;	Temp = *a;	*a = *b;	*b = Temp;}int GetEdge(Edge ESet, int CurrentSize){   	//给定当前堆的大小CurrentSize,将当前最小边位置弹出并调整堆	//将最小边与当前堆的最后一个位置的边交换	Swap(&ESet[0], &ESet[CurrentSize - 1]);	//将剩下的边继续调整成最小堆	PercDown(ESet, 0, CurrentSize - 1);	return CurrentSize - 1;//返回最小边所在位置}//最小堆定义结束void Print_LGraph(LGraph Graph){   	PtrToAdjVNode P;	for (int i = 0; i < Graph->Nv; i++) {   		printf("与%d相连的顶点有", i);		for (P = Graph->G[i].FirstEdge; P != NULL; P = P->Next) {   			printf("-%d->%d", P->Weight, P->AdjV);		}		printf("\n");	}}int Kruskal(LGraph Graph){   	//将最小生成树保存为邻接表存储的图MST，返回最小的权重和	WeightType TotalWeight;	int ECount;	int NextEdge;	SetType VSet;//顶点数组	Edge ESet;	LGraph MST;	VSet = (SetType)malloc(sizeof(ElementType) * MaxVertexNum);	InitializeVSet(VSet, Graph->Nv);//初始化顶点并查集	ESet = (Edge)malloc(sizeof(struct ENode) * Graph->Ne);	InitializeESet(Graph, ESet);//初始化边的最小堆	//创建包含所有顶点但是没有边的图，注意用邻接表版本	MST = CreateGraph2(Graph->Nv);	TotalWeight = 0;//初始化权重和	ECount = 0;//初始化收录的边数	NextEdge = Graph->Ne;//原始边集的规模	while (ECount < Graph->Nv - 1) {   //当收集的边不足以构成最小生成树时		NextEdge = GetEdge(ESet, NextEdge);//从边长中得到最小边的位置		if (NextEdge < 0)//边集已空			break;		//如果该边的加入不构成回路，即两端结点不属于同一连通集		if (CheckCycle(VSet, ESet[NextEdge].V1, ESet[NextEdge].V2)) {   			//将该边的插入MST			InsertEdge2(MST, &ESet[NextEdge]);			TotalWeight += ESet[NextEdge].Weight;//累计权重			ECount++;//生成树中边数加1		}	}	if (ECount < Graph->Nv - 1)		TotalWeight = -1;//设置错误标记，表示生成树不存在	Print_LGraph(MST);	return TotalWeight;}