数据结构（十五）最小生成树

梦里梦外; 2022-04-16 06:19 185阅读 0赞

## 最小生成树问题 ##

### 1. 什么是最小生成树 ###

*  是一棵**树**
    
     *  无回路
     *  |V|个顶点一定有 |V|-1 条边
 *  是**生成**树
    
     *  不唯一
     *  包含全部顶点
     *  |V|-1 条边都在图里
 *  边的权值和**最小**

### 2. 贪心算法 ###

*  什么是 “贪”：每一步都是最好的
 *  什么是 “好”：权重最小的边
 *  需要约束：
    
     *  只能用图里有的边
     *  只能正好用掉 |V|-1 条边
     *  不能有回路

#### 1. Prim 算法 ####

![20181118171739821.gif][]

void Prim(){
        
        MST = {
        s};  // parent[s] = -1
        while(1){
        
            V = 未收录顶点中dist最小者;   // dist[V] = E<V,W> 或 正无穷
            if ( 这样的V不存在 )
                break;
            dist[V] = 0;  // 将V收录进MST
            for ( V 的每个邻接点 W )
                if ( dist[W]!= 0)
                    if ( E<V,W> < dist[w] ){
        
                        dist[W] = E<V,W>;
                        parent[W] = V;
                    }
        }
        if ( MST 中收的顶点不到|V|个)
            Error ( "图不连通" );
    }

时间复杂度：T = O(|V| 2 ^2 2) —— 稠密图合算

#include<iostream>
    #include<vector>
    #define INF 100000
    #define MaxVertex 105
    typedef int Vertex; 
    int G[MaxVertex][MaxVertex];
    int parent[MaxVertex];   // 并查集 
    int dist[MaxVertex]; // 距离 
    int Nv;    // 结点 
    int Ne;    // 边 
    int sum;  // 权重和 
    using namespace std; 
    vector<Vertex> MST;  // 最小生成树 
    
    // 初始化图信息 
    void build(){
        
    	Vertex v1,v2;
    	int w;
    	cin>>Nv>>Ne;
    	for(int i=1;i<=Nv;i++){
        
    		for(int j=1;j<=Nv;j++)
    			G[i][j] = 0;  // 初始化图 
    		dist[i] = INF;   // 初始化距离
    		parent[i] = -1;  // 初始化并查集 
    	}
    	// 初始化点
    	for(int i=0;i<Ne;i++){
        
    		cin>>v1>>v2>>w;
    		G[v1][v2] = w;
    		G[v2][v1] = w;
    	}
    }
    
    // Prim算法前的初始化 
    void IniPrim(Vertex s){
        
    	dist[s] = 0;
    	MST.push_back(s);
    	for(Vertex i =1;i<=Nv;i++)
    		if(G[s][i]){
        
    			dist[i] = G[s][i];
    			parent[i] = s;
    		} 
    }
    
    // 查找未收录中dist最小的点 
    Vertex FindMin(){
        
    	int min = INF;
    	Vertex xb = -1;
    	for(Vertex i=1;i<=Nv;i++)
    		if(dist[i] && dist[i] < min){
         
    			min = dist[i];
    			xb = i;
    		}
    	return xb;
    }
    
    void output(){
        
    	cout<<"被收录顺序："<<endl; 
    	for(Vertex i=1;i<=Nv;i++)
    		cout<<MST[i]<<" ";
    	cout<<"权重和为："<<sum<<endl; 
    	cout<<"该生成树为："<<endl; 
    	for(Vertex i=1;i<=Nv;i++)
    		cout<<parent[i]<<" ";
    }
    
    void Prim(Vertex s){
        
    	IniPrim(s);
    	while(1){
        
    		Vertex v = FindMin();
    		if(v == -1)
    			break;
    		sum += dist[v];
    		dist[v] = 0;
    		MST.push_back(v);
    		for(Vertex w=1;w<=Nv;w++)
    			if(G[v][w] && dist[w])
    				if(G[v][w] < dist[w]){
        
    					dist[w] = G[v][w];
    					parent[w] = v;
    				}
    	}
    }
    
    
    int main(){
        
    	build();
    	Prim(1);
    	output();
    	return 0;
    }

#### 2. Kruskal 算法 ####

![20181118171601539.gif][]

void Kruskal ( Graph G ){
        
        MST = {
         };
        while ( MST 中不到|V|-1条边 &&  E中还有边 ) {
        
            从 E 中取一条权重最小的边 E<V,W>;    // 最小堆
            将 E<V,W> 从 E 中删除;
            if ( E<V,W> 不在 MST 中构成回路 )  // 并查集
                将 E<V,W> 加入MST;
            else
                彻底无视 E<V,W>;
        }
        if ( MST 中不到|V|-1条边 )
            Error("图不连通");
    }

时间复杂度：T = O(|E|log|E|) —— 稀疏图合算

#include<iostream>
    #include<string>
    #include<vector>
    #include<queue>
    #define INF 100000
    #define MaxVertex 105
    typedef int Vertex; 
    int G[MaxVertex][MaxVertex];
    int parent[MaxVertex];   // 并查集最小生成树 
    int Nv;    // 结点 
    int Ne;    // 边 
    int sum;  // 权重和 
    using namespace std; 
    struct Node{
        
    	Vertex v1;
    	Vertex v2;
    	int weight; // 权重 
    	// 重载运算符成最大堆 
    	bool operator < (const Node &a) const
    	{
        
    		return weight>a.weight;
    	}
    };
    vector<Node> MST;  // 最小生成树 
    priority_queue<Node> q;   // 最小堆 
    
    // 初始化图信息 
    void build(){
        
    	Vertex v1,v2;
    	int w;
    	cin>>Nv>>Ne;
    	for(int i=1;i<=Nv;i++){
        
    		for(int j=1;j<=Nv;j++)
    			G[i][j] = 0;  // 初始化图
    		parent[i] = -1;
    	}
    	// 初始化点
    	for(int i=0;i<Ne;i++){
        
    		cin>>v1>>v2>>w;
    		struct Node tmpE;
    		tmpE.v1 = v1;
    		tmpE.v2 = v2;
    		tmpE.weight = w;
    		q.push(tmpE); 
    	}
    }
    
    //  路径压缩查找 
    int Find(int x){
        
    	if(parent[x] < 0)
    		return x;
    	else
    		return parent[x] = Find(parent[x]);
    } 
    
    //  按秩归并 
    void Union(int x1,int x2){
        
        x1 = Find(x1);
        x2 = Find(x2);
    	if(parent[x1] < parent[x2]){
        
    		parent[x1] += parent[x2];
    		parent[x2] = x1;
    	}else{
        
    		parent[x2] += parent[x1];
    		parent[x1] = x2;
    	}
    } 
    
    void Kruskal(){
        
    	// 最小生成树的边不到 Nv-1 条且还有边 
    	while(MST.size()!= Nv-1 && !q.empty()){
        
    		Node E = q.top();  // 从最小堆取出一条权重最小的边
    		q.pop(); // 出队这条边 
    		if(Find(E.v1) != Find(E.v2)){
          // 检测两条边是否在同一集合 
    			sum += E.weight; 
    			Union(E.v1,E.v2);     // 并起来 
    			MST.push_back(E);
    		}
    	}
    	
    } 
    
    
    void output(){
        
    	cout<<"被收录顺序："<<endl; 
    	for(Vertex i=0;i<Nv;i++)
    		cout<<MST[i].weight<<" ";
    	cout<<"权重和为："<<sum<<endl; 
    	for(Vertex i=1;i<=Nv;i++)
    		cout<<parent[i]<<" ";
    	cout<<endl;
    }
    
    
    int main(){
        
    	build();
    	Kruskal();
    	output();
    	return 0;
    }

[20181118171739821.gif]: /images/20220416/cc4df3b55257477bbf058e150aded285.png
[20181118171601539.gif]: /images/20220416/d7d4509da55b40d9bba8afcda01b91f9.png