浙大データ構造練習問題ノート:Kruskalアルゴリズム

Kruskalアルゴリズム
PrimアルゴリズムよりもKruskalアルゴリズムの実現原理は簡単ですが、先行作業は複雑です(スタックを構築して調べると最小スタックを調べる)スタックを使用しない場合は、すべてのエッジをソートして、小さいから大きいまで求めて調べることができ、最小生成ツリーに検索することができます

#include
#include
#include
#include
#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<<"Enter num : "<<endl;
    for(Vertex i=1;i<=Nv;i++){
        cout<<MST[i].weight<<" ";
    }
    cout<<endl;
    cout<<"Total Weight :"<<sum<<endl;
    for(Vertex i=1;i<=Nv;i++){
        cout<<parent[i]<<" ";
    }
    cout<<endl;
}

int main()
{
    build();
    Kruskal();
    output();
    return 0;
}