最小生成ツリーの2つのアルゴリズム:PrimとKruskalアルゴリズム

ますます1つの道理を理解しました:あなたがコードを書けない原因はただ1つで、それはあなたがこのアルゴリズムの思想を徹底的に理解していないことです!!
以前は最小生成木を書いたことがありますが、水でいくつかの問題を解いた後、しばらくすると、忘れてしまい、少しも書けなくなります.原因は一つしかないかもしれませんが、それは私がこの2つのアルゴリズムを完全に理解していないことです.
トピック:
実は、最小生成ツリーを求めるには2つのポイントがあります.1つは重み値が最小で、もう1つはこの図がツリーでなければなりません.一方、PrimとKruskalの違いは、両者が選択した変数が異なることであり、Primは常に重み値を最小限に保ち、1つのポイントごとに木を構築することを選択します.Kruskalは常に1本の木であることを保証し(構築中は必ずしも本当の木ではないが、結果が1本の木であることを保証するために採集された判環を調べて理解することができる)、それから1本ずつエッジを加えて、重み値を最小限に抑える.
上記の2つの考えを知ってから、コードの実現について話します(いずれも貪欲に基づいています).
Prim:(ここでは重み値を距離として理解する)確定した点の集合がSであると仮定すると、まだ確定していない点は1−Sと記すことができ、私たちは未確定の点集合1−Sのたびに、集合Sの中の点から直接接続され、重み値が最小(欲張り)の点をSに加えることを選択し、この点をtとしてもよい.Sと1−Sは変化する:tがS中の点になったため、1−S中のtに接続された点の距離は実際にはこの点とSの距離になった.初期化時に既にフラグが1つあるので、N-1回だけループすれば十分で、N-1回しかループできません.そうしないとエラー(INFによって異なります)が発生する可能性があります.これがPrimアルゴリズムです.
Kruskal:このアルゴリズムはPrimに比べてよく理解されています.重みが最も小さい(欲張り)エッジを選択するたびに、そのエッジの2つの点が木と矛盾しているかどうかを見て(セットで判断すればいい)、エッジを付ける過程で有効点の数を記録し、N個に達すると終了し、各エッジを考慮する必要はありません.
添付:HDU 1233はやはり開通工事の2種類のアルゴリズムのコードで、理解を助けます:
Prime:

#include
#include
#include
#include
#define INF 0x7fffffff

using namespace std;

int Map[110][110],dis[110],vis[110];
int N,M;

void prime(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=N;i++) dis[i]=Map[1][i];//         ，      
    int sum=0;vis[1]=1;//  1     ，     
    for(int p=1;p<=N-1;p++){//  N-1   ，     N-1  
        int t,Min=INF;
        for(int i=1;i<=N;i++) if(!vis[i] && dis[i]Map[t][i])//   t    1-S      S   
            dis[i]=Map[t][i];
    }
    cout<>N && N){
        for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) Map[i][j]=INF;
        M=(N-1)*N/2;
        int a,b,c;
        for(int i=0;i

Kruskal:

#include
#include
#include

using namespace std;
struct edge{
    int u,v,w;
    bool operator>N && N){
        M=N*(N-1)/2;
        for(int i=0;i