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 1000using 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;}