Prime&&Kruscal算法解决最小生成树问题(C++)

解题思路:这道题，我使用了Prime算法解决，以下是我的总结。

注意事项:二维数组不能开太大，1000足以，不然会爆掉

参考代码:

#include <bits/stdc++.h>
#define max 65535
#define size 1000
#define join 65534
#define ini 65532
using namespace std;

struct Edge
{
	// 顶点表
	int start;
	// 邻接矩阵
	int end;
	// 顶点数，边数
	int weight;
	Edge()
	{
		weight = max - 1;
	}
};
bool cmp(const Edge &a, const Edge b)
{
	return a.weight < b.weight;
}
Edge e[size];
int s = 0;
typedef struct
{
	// 顶点表
	int vex[size];
	// 邻接矩阵
	int arc[size][size];
	// 顶点数，边数
	int numvex, numedge;
} MGroup;
void createGroup(MGroup *G)
{
	int i, j, k, w;
	// 创建图的过程就是将顶点表填入相应数值
	//cout << "请输入顶点数和边数" << endl;
	cin >> G->numvex;
	//cout << "请输入顶点信息";
	for (i = 0; i < G->numvex; i++)
	{
		G->vex[i] = i;
	}

	for (int i = 0; i < G->numvex; i++) // 再设计最小生成树时，一定要初始化，不然容易弄混淆,或者定义一个参数作为生成树的标志
		fill(G->arc[i], G->arc[i] + (G->numvex), max);
	//cout << "请输入边信息，依次是行，列，权值" << endl;
	for (i = 0; i < G->numvex; i++)
	{
		for (int j = 0; j < G->numvex; j++)
		{
			int value;
			cin >>value;
			if (value)
			{
				G->numedge++;
				G->arc[i][j] = value;
				e[s].start = i;
				e[s].end = j;
				e[s].weight = value;
				s++;
				// 无向图是对称图
				G->arc[j][i] = value; // 若是有向图，不加，因为有向图可能不是对称图，但是无向图一定是
			}
		}
	}
}
int mintree_prime(MGroup *G)
{
	int result = 0;
	int min, i, j, k;
	int adjvex[size];
	int lowcost[size];
	lowcost[0] = join;
	adjvex[0] = 0;
	for (i = 1; i < G->numvex; i++)
	{
		lowcost[i] = G->arc[0][i]; // 按照邻接表的值进行赋值，此时的lowcost只有第一行的数值
		adjvex[i] = 0;
	}
	for (i = 1; i < G->numvex; i++)
	{
		min = max;
		j = 1;
		k = 0;				  // 存储最小顶点的下标
		while (j < G->numvex) // 遍历所有顶点
		{
			if (lowcost[j] != join && lowcost[j] < min)
			{
				min = lowcost[j]; // 此时的最小值则记录下来提供给下一次操作
				k = j;
			}
			j++;
		}								 // 遍历完后，就会得到此时最短路径
		//printf("(%d,%d)", adjvex[k], k); // 展示处此时连线，adjvex[K]表示当前最小顶点,表示所在图的行和列
		result += G->arc[adjvex[k]][k];
		lowcost[k] = join;				// 已纳入了最小生成树
		for (j = 1; j < G->numvex; j++) // 从0顶点开始了，所以不算0那个顶点，从1算起；
		{
			if (lowcost[j] != join && G->arc[k][j] < lowcost[j]) // 此时是第K行的值与65535比较
			{
				lowcost[j] = G->arc[k][j]; // 此时将lowcost数组刷新，然后多了一部分可遍历的点
				adjvex[j] = k;			   // 刷新起点为当前最小值
			}
		}
	}
	return result;
}

int find(int *parents, int f) // 找没有环路的最优解，不从起点回来
{
	while (parents[f]!=ini)//寻找是否有环，直到没有环为止,因为此时该点已经访问过，再用它必有一条回路
		f = parents[f];
	return f;//返回空闲位置
}
int Kruskal(MGroup *G)
{
	int parents[size]; // 生成树数组c++默认为零
		fill(parents, parents + G->numvex, ini);
	int i, j, result = 0, n, m;
	for (int i = 0; i < G->numedge; i++) // 遍历边集数组
	{
		n = find(parents, e[i].start);
		m = find(parents, e[i].end);
		if (n != m)
		{
			parents[n] = m;//表示将他们连在一起，标志访问
			//printf("(%d->%d)", e[i].start, e[i].end);
			result += e[i].weight;
		}
	}
	return result;
}
int main()
{
	MGroup *p = new MGroup();
	createGroup(p);
	sort(e, e + size - 100, cmp);
	cout << mintree_prime(p) << endl;
	cout << Kruskal(p);
	return 0;
}