最小生成樹MST（Prim/Kruskal模版）

生成樹：如果連通圖G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。生成樹不唯一，不同起點周遊所得生成樹不同。

最小生成樹：邊權最小的生成樹。

最小邊原則：圖中權值最小的邊(如果唯一的話)一定在最小生成樹上。

唯一性：一棵生成樹上，如果各邊的權都不相同，則最小生成樹是唯一的。反之不然。

生成樹一定是無向圖。

Prim

基礎是兩個屬性：

環屬性：一棵生成樹上，增加一條邊e，再删除e所在環上的最大邊，會得到另一棵“更好”的生成樹(如果e不是最大邊)

剪切屬性：在圖中，剪切将頂點劃分成兩個不相交集合。交叉邊為這些頂點在兩個不同集合的邊。對于任何一個剪切，各條最小的交叉邊都屬于某個MST，且每個MST中都包含一條最小交叉邊。

簡述：MST_Prim(G, r)

(1)将G剪切成兩個集合A、B，A中隻有一個點r

(2)取最小權的交叉邊(x,y)，x∈A, y∈B

(3)将y加入A并更新

(4)如果已經加了n-1條邊，結束。否則，轉 (3)

示例：

模版：

int flag[maxm]={};//是否在A中。
int dis[maxm];//集合A與i點的交叉邊權值，如果flag[i]==1，那麼dis[i]無意義。
int sum=;//MST邊權總和。

void prim()
{
    flag[]=;//從任意一點出發均可，此處用第一個點。第一個點已被選入集合A。
    for(int i=;i<=n;i++) dis[i]=a[][i];//初始化。
    dis[]=; //已在A中，無交叉邊。
    for(int i=;i<n;i++)
    {
        int minn=;
        int k=;
        for(int j=;j<=n;j++)
            if(!flag[j]&&dis[j]<minn) minn=dis[j],k=j;//在現有的交叉邊中找到最小的。
        flag[k]=;//将其加入A。
        sum+=dis[k];
        if(k==) break;//同dijkstra，非聯通圖的情況。
        for(int j=;j<=n;j++)
            if(!flag[j]&&dis[j]>a[k][j]) dis[j]=a[k][j];//利用新加入的點更新集合A與B的交叉邊。
    }
    return; 
}
           

基于點的疊代，穩定O（n^2）。

堆優化後：O((|E|+|V|)*log|V|) ，适合稀疏圖。

Kruskal

簡述：MST_Kruskal(G)

(1)将G所有條邊按權從小到大排序；圖mst開始為空

(2)從小到大次序取邊(x,y)

(3)若加入邊(x,y)，mst就有環，則放棄此邊，轉(2)

(4)将邊(x,y)加入mst，如果已經加了n-1條邊，結束。否則，轉 (2)

判環即利用并查集，改日另寫。

int n,m,summ=;
struct edge
{
    int q,w,v;
}e[maxm];//邊表。
int fa[maxn]={};//根節點。

sort(e+,e+m+,mycmp);//升序排序。

for(int i=;i<=n;++i) fa[i]=i;//根節點初始化。

inline int find(int x)
{
    if(fa[x]==x) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}//找爸爸。

/*或者另一種裝13的找爸爸寫法：
inline int find(int x)
{
    return(fa[x]==x?x:fa[x]=find(fa[x]));
}*/

void kru()
{
    int flag=;//邊數計數器。
    for(int i=;i<=m;i++)
    {
        int x=find(e[i].q);
        int y=find(e[i].w);
        if(x!=y)//如果它們不是同一個爸爸生的，即加入它們不會形成一個環。
        {
            fa[x]=y;//合并。
            flag++;//計數。
            summ+=e[i].v;
            if(flag==n-) return;//如果邊已達到n-1條，結束。
        }
    }
    return;
}

           

基于邊的疊代，适合稀疏圖，O(|E|*log|E| +|N|*A(|V|))。O(|E|*log|E| )用于排序。

最大生成樹可把資料全部取負再操作。注意初始化問題。