8.2.2再谈最小生成树//用数组

#include<iostream>
using namespace std;
int main(){
	int n,m,i,j,k,min,b1,b2,z3;
	int e[7][7],dis[7],book[7]={0};//这里对book数组进行了初始化
	int inf=99999999;
	int count=0,sum=0;//count用来记录生成树中顶点的个数,sum用来存储路径之和
	
	//读入n和m,n表示顶点个数,m表示边的条数
	cout<<"请分别输入原图顶点个数n,边的条数m："<<endl;
	cin>>n>>m;

	//初始化
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j){
				e[i][j]=0;
			}
			else
				e[i][j]=inf;
		}
	} 
 	
	//读入边 
	cout<<"请依次输入m条边，每条边起点为b1，终点为b2，权重为z3。即b1->b2(z3)："<<endl; 
	for(i=1;i<=m;i++){
		//读入每一条边 
		cin>>b1>>b2>>z3;
		//这里是无向图,所以需要将边反向再存储一遍 
		e[b1][b2]=z3;
		e[b2][b1]=z3;
	}
	
	//初始化dis数组，这里是1号顶点到其余各个顶点的初始距离,因为当前生成树中只有1号顶点 
	for(i=1;i<=n;i++){
		dis[i]=e[1][i];
	}
	
	//Prim核心部分开始
	//将1号顶点加入生成树
	book[1]=1;//这里用book来标记一个顶点是否已经加入生成树
	count++;
	while(count<n){
		min=inf;
		for(i=1;i<=n;i++){
			if(book[i]==0&&dis[i]<min){
				min=dis[i];
				j=i;
			} 
		}
		book[j]=1;
		count++;
		sum+=dis[j];
		
		//扫描当前顶点j所有的边,再以j为中间点,更新生成树到每一个非树顶点的距离
		for(k=1;k<=n;k++){
			if(book[k]==0&&dis[k]>e[j][k]){
				dis[k]=e[j][k];
			}
		} 
	} 
	
	cout<<"该图的最小生成树的边的总长度之和最短为: "<<sum;//打印结果
	getchar();
	return 0; 
	 
}

/*

Prim算法流程:

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

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

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

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

5、该算法时间复杂度为O(logM)。 
*/