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)。 
*/