8.2镖局运镖-------图的最小生成树 无向图 有权重 Prim算法

Prim算法流程：

1、从任意一个顶点开始构造生成树，假设从1号顶点开始。首先将顶点1加入生成树中，用一个数组book来标记哪些顶点已经加入了生成树

2、 用数组dis记录生成树中各个顶点的距离。最初生成树中只有1号顶点，有直连边时，数组dis中存储的就是1号顶点到该顶点的边的权值，没有直连边的时候就是无穷大，即初始化dis数组

3、从数组dis中选出离生成树最近的顶点（假设这个顶点为j）加入到生成树中（即在数组dis中找最小值）。再以j为中间点，更新生成树到每一个非树顶点的距离（就是松弛），即如果dis[k]>map[j][k]，则更新dis[k]=map[j][k]。

4、重复第3步，直到生成树中有n个顶点为止。

// prim.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>

#define Max 1000
using namespace std;

int n, m;//n个点，m条边

int map[Max][Max];

int dis[Max];

int book[Max] = {0};

int t1, t2, t3;

int inf = 99999999;//正无穷大

int cnt=0;//用来记录生成树中顶点的个数
int sum = 0;//用来存储路径之和

int _tmain(int argc, _TCHAR* argv[])
{

	int min;

	cout << "请输入n个顶点，m条边的无向图" << endl;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == j)
				map[i][j] = 0;
			else
				map[i][j]=inf;
		}
	}

	//开始读入边
	for (int i = 1; i <= m; i++)
	{
		cin >> t1 >> t2 >> t3;
		map[t1][t2] = t3;
		map[t2][t1] = t3;
	}

	//初始化dis数组，这里是1号顶点到各个顶点的初始距离，因为
	//当前生成树中只有1号顶点
	for (int i = 1; i <= n; i++)
	{
		dis[i] = map[1][i];
	}

	//prim核心部分
	book[1] = 1;//这里用book来标记一个顶点是否已经加入生成树
	cnt++;

	while (cnt<n)
	{
		int i, j;
		min = inf;
		for (i = 1; i <= n; i++)
		{
			if (book[i] == 0 && dis[i] < min)
			{
				min = dis[i];
				j = i;
			}
		}
		book[j] = 1;
		cnt++;
		sum = sum + dis[j];

		//扫描当前顶点j所有的边，再以j为中间点，更新生成树到每一个非树顶点的距离
		for (int k = 1; k <= n; k++)
		{
			if (book[k] == 0 && dis[k] > map[j][k])
				dis[k] = map[j][k];
		}
	}

	cout << sum << endl;

	system("pause");

	return 0;
}