最小生成樹算法：Prim、Kruskal

Prim算法實作完整代碼：

#include<iostream>
using namespace std;
const int Max=;
class MGraph{
    public:
        MGraph(){

        }
        MGraph(int n,int e);
        ~MGraph(){

        }
    public:
    int arc[Max][Max];
    int vertexNum,arcNum;
};
MGraph::MGraph(int n,int e){
    int i,j;
    vertexNum=n;
    arcNum=e;
    for(int i=;i<n;i++)
    for(int j=;j<n;j++)
    arc[i][j]=;
    for(int k=;k<e;k++){
        cin>>i>>j;//輸入邊的兩個點下标及權值
        cin>>arc[i][j];
        arc[j][i]=arc[i][j];
    }
}
class A{
    public:
    int lowcost;
    int adjvex; 
};
int MinEdge(A shortEdge[],int n){
    int j;
    int p=;
    for(int i=;i<n;i++)
    for(int i=;i<n;i++)
    if(shortEdge[i].lowcost!=&&shortEdge[i].lowcost<p){
        p=shortEdge[i].lowcost;
        j=i;
    }
    return j;
}
void Prim(MGraph G){
    A shortEdge[Max];
    for(int i=;i<G.vertexNum;i++){
        shortEdge[i].lowcost=G.arc[][i];
        shortEdge[i].adjvex=;
    }
    shortEdge[].lowcost=;
    for(int i=;i<G.vertexNum;i++){
        int k=,j=;
        k=MinEdge(shortEdge,G.vertexNum);
        cout<<"("<<shortEdge[k].adjvex<<","<<k<<") "<<shortEdge[k].lowcost<<endl;
        shortEdge[k].lowcost=;
        for(j=;j<G.vertexNum;j++){
          if(shortEdge[j].lowcost!=){
            if(G.arc[k][j]<shortEdge[j].lowcost){
                shortEdge[j].lowcost=G.arc[k][j];
                shortEdge[j].adjvex=k;
            }
          } 
        }
    }
    int num=;
    for(int i=;i<G.vertexNum;i++)
    num+=G.arc[i][shortEdge[i].adjvex];
    cout<<"最大的權值為："<<num<<endl; 
}
int main(){
  int n,e;
  cin>>n>>e;//輸入頂點數、邊數
  MGraph G(n,e);
  Prim(G);
  return ;
}
           

Kruskal算法的基本思想是以邊為主導地位，始終都是選擇目前可用的最小權值的邊，步驟如下：

（1）設一個有n個頂點的連通網絡為G（V,E），最初先構造一個隻有n個頂點，沒有邊的非連通圖T{V,Ø}，圖中每個頂點自成一個連通分量；

（2）當在E中選擇一條具有最小權值的邊時，若該邊的兩個頂點落在不同的連通分量上，則将此邊加入到T中；否則，即這條邊的兩個頂點落在同一個連通分量上，則将此邊舍去（此後永不選用這條邊），重新選擇一條權值最小的邊；

（3）如此重複下去，直到所有頂點在同一個連通分量上為止。

Kruskal算法實作：

#include<iostream>
#include<algorithm>
using namespace std;
const int MaxVertex=;
const int MaxEdge=;
struct EdgeType{
    public:
    int from,to;
    int weight;
};
bool cmp(struct EdgeType a,struct EdgeType b){
    if(a.weight<b.weight){
        return true;
    }
    return false;
}
class EdgeGraph{
    public:
    EdgeType edge[MaxEdge];
    int vertexNum,edgeNum;
    EdgeGraph(int vertexNum,int edgeNum);
};
EdgeGraph::EdgeGraph(int vertexNum,int edgeNum){
    EdgeType edge1[edgeNum];
    for(int i=;i<edgeNum;i++)
    cin>>edge1[i].from>>edge1[i].to>>edge1[i].weight;//輸入邊的兩個點下标及權值 
    sort(edge1,edge1+edgeNum,cmp);
    for(int i=;i<edgeNum;i++)
    edge[i]=edge1[i];
    this->edgeNum=edgeNum;
    this->vertexNum=vertexNum;
}
int FindRoot(int parent[],int v){
    int t=v;
    while(parent[t]!=-)
    t=parent[t];
    return t;
} 
void Kruskal(EdgeGraph G){
    int parent[MaxVertex],vex1,vex2,num=,sum=;
    for(int i=;i<G.vertexNum;i++)
    parent[i]=-;
    for(int i=;i<G.edgeNum;i++){
        vex1=FindRoot(parent,G.edge[i].from);
        vex2=FindRoot(parent,G.edge[i].to);
        if(vex1!=vex2){
            parent[vex2]=vex1;
            num++;
            sum+=G.edge[i].weight;
            if(num==(G.vertexNum-))
            break;
        }
    }
    cout<<"最小的權值為："<<sum<<endl;
}
int main(){
    int vertexNum,edgeNum;
    cin>>vertexNum>>edgeNum;//輸入頂點數、邊數 
    EdgeGraph G(vertexNum,edgeNum);
    Kruskal(G);
    return ;
}
           

上面代碼如有錯誤，歡迎大家指出！