kruskal.h

kruskal算法

#ifndef KRUSKAL_H
#define KRUSKAL_H
#include <iostream>
#include <string>
#include "binaryheap.h"
#include <malloc.h>
using namespace std;

typedef struct
{
	int adj;
	int time;
}adjmatrix ;//邻接矩阵

typedef struct
{
	adjmatrix **arc;
	int vexnum;  //所有顶点数
	int arcnum;  //所有边数
}Graph;//图
Graph* GraphInit(Graph *);//初始化图

long int MiniSpanTree(Graph *);//最小生成树函数

int  Parent(int *, int );//找到母节点


Graph* GraphInit(Graph *graph)
{
	int p,q;//p为已连接道路数，q为未连接道路数
	int x ,y,t;//x,y,t声明与作业安排上要求一致


	cin>>graph->vexnum>>p>>q;
	graph->arcnum = p + q ;

	graph->arc = new adjmatrix* [6500];
	for(int i = 0 ; i < 6500; i ++)
		graph->arc[i] = new adjmatrix[6500];

	for (int i = 1; i <= graph->vexnum; i++)//初始化图
	{
		for (int  j = 1; j <= graph->vexnum; j++)
		{
			graph->arc[i][j].adj = 0;
		}
	}

	for (int  i = 1; i <= p; i++)//输入各个点以及两点之间修路所需时间，已修好路算作时间为0
	{
		cin >> x >> y;
		graph->arc[x][y].adj = graph->arc[y][x].adj = 1;
		graph->arc[x][y].time = graph->arc[y][x].time = 0; //已有路初始化时间为0
	}
	for (int i = 1; i <= q ; i ++)
	{
		cin >> x >> y >> t;
		graph->arc[x][y].adj = graph->arc[y][x].adj = 1;
		graph->arc[x][y].time = graph->arc[y][x].time = t;	//未修路初始化为相应时间
	}
	return graph;
}



long int MiniSpanTree(Graph *graph)//生成最小生成树 
{
	int i;//计数横坐标
	int j;//计数纵坐标
	int n;//储存第一个点的母节点
	int m;//储存最后一个点的母节点，如果m != n 说明他们之间的边是最小生成树的边
	int k = 1;
	HEAP heap;
	int *parent = (int *)malloc(1000000* sizeof(int ));
	num  edge;
	num  de_edge;
	long int total_time = 0;
	heap.element = (num *)malloc(1000000 * sizeof(num));
	heap.size = 0;
	for (int l = 0 ;l < 1000000; l ++)
	{
		heap.element->time = 0;//对堆进行初始化
	}
	for (i = 1; i <= graph->arcnum; i++)//对所有元素母节点进行初始化
	{
		parent[i] = 0;
	}

	//先进行排序
	for ( i = 1; i < graph->vexnum; i++)
		for (j = i + 1; j <= graph->vexnum; j++)
			if (graph->arc[i][j].adj == 1)//找到在邻接矩阵中相关联的点并将其插入堆中
			{
				edge.firstvex = i;
				edge.lastvex  = j;
				edge.time     = graph->arc[i][j].time;
				heapinsert(heap,edge);
			}

			for (i = 1; i <= graph->arcnum; i++) 
			{
				de_edge = heapdelete(heap);//取出堆中时间最小的边
				n = Parent(parent, de_edge.firstvex );
				m = Parent(parent, de_edge.lastvex );
				if (n != m)//如果边的两个点的母节点并不相同，说明边为最小生成树的一条，将其时间算入总时间之中
				{
					total_time += de_edge.time;
					parent[n] = m;
				}
			}
			free(heap.element);//释放内存
			free(parent);
			return total_time;
}

int Parent(int *parent, int vex)//寻找母节点
{
	while ( parent[vex] > 0)
	{
		vex = parent[vex];
	}
	return vex;
}

#endif