prim求最小生成树

Posted on | In |

flag[i]=true表明 顶点i 已加入最小生成树
close 存放最后的相关的最小权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<stack>
#include <iostream>
#include <vector>
#include <queue>
#define MAX 100
#define INF 1e6
using namespace std;
bool flag[MAX];
int close[MAX];
int p[MAX];
int c[MAX][MAX];
int n;
void prim(int u){
	for(int i=1;i<=n;i++){
		if(c[u][i]!=INF){
			close[i]=c[u][i];
		}
		else close[i]=INF;
	}

	close[u]=0;
	flag[u]=true;
	for(int k=1;k<=n;k++)
	{	

	int tmp=INF,t=u;
	for(int i=1;i<=n;i++){
		
		if(!flag[i]&&close[i]<tmp){
			tmp=close[i];
			t=i;
		}
	}
	if(t==u) return;
	flag[t]=true;
	for(int j=1;j<=n;j++){
		if(!flag[j]&&c[t][j]<close[j]){
			close[j]=c[t][j];
			p[j]=t;
		}
	}
	
	}
}
void findPath(int u){
	stack<int> s;

	for(int i=1;i<=n;i++){
			s.push(i);
		int x=p[i];
		
		while(x!=-1){
			s.push(x);
			x=p[x];
		}
		cout<<u<<"到"<<i<<"的路径为:"<<endl; 
		while(!s.empty()){
			cout<<s.top()<<" "; 
			s.pop();
		}
		cout<<endl;
		
	} 
	
	
} 
int main(){
	int cases,src,u,v,w;
	freopen("12-2.txt","r",stdin);
	cin>>n>>cases;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			c[i][j]=INF; 
	 
		
	}
	for(int i=cases;i>0;i--){
		cin>>u>>v>>w;
		c[u][v]=w;
		c[v][u]=w;
		
	}
	
	cin>>src;
	p[src]=-1; 
			for(int i=1;i<=n;i++) 
	{
	if(i!=src)	{
	flag[i]=false;
	p[i]=src;
	}
	}
	int low=0;
	prim(src);//!!
    cout<<"数组Lowercost内容"<<endl; 
	for(int i=1;i<=n;i++)
		cout<<close[i]<<" ";
	cout<<endl;
	for(int i=1;i<=n;i++){
		
		if(i!=src) {
			low+=close[i];
		}
	} 

	cout<<"最小花费为:"<<low<<endl;
	
		findPath(src);
}

image
image