数据结构-最小生成树 （C++代码）

解题思路:

        Prim 是最常用的一种生成树算法，具体算法分析博客上都有很多。实质也是贪心。

参考代码:

#include "iostream"
#include "algorithm"
#define Inf 0xFFFFFFF;
using namespace std;
const int mapSize = 101;

int  Map[mapSize][mapSize];
int  dis[mapSize];           /*  当前点对相连点的距离 */
bool Vis[mapSize];           /*        标记数组       */
int  point;

int prim() {
	/* - 从第 0 个顶点开始 - */
	Vis[0] = true;
	for (int i = 0; i < point; i++)
		dis[i] = Map[0][i] != 0 ? Map[0][i] : Inf;

	int length = 0;

	/*    因为 N 个点有 N - 1 条边   */
	for (int deg = 0; deg < point - 1; deg++) {
		int index, poi = Inf;

		for (int i = 0; i < point; i++)
			if (!Vis[i] && dis[i] < poi) {
				poi = dis[i];
				index = i;
			}
		/*  优先选距离最小的  */
		length += poi;
		Vis[index] = true;

		/*   更新当前已连接点与其他点的最小距离   */
		for (int i = 0; i < point; i++)
			dis[i] = Map[index][i] != 0 ? min(dis[i], Map[index][i]) : dis[i];
	}
	return length;
}

int main() {
	cin >> point;
	for (int i1 = 0; i1 < point; i1++)
		for (int i2 = 0; i2 < point; i2++)
			cin >> Map[i1][i2];

	cout << prim() << endl;
	return 0;
}