天天看點
傳回

最小生成樹 Prim Kruskal

layout: post

title: 最小生成樹 Prim Kruskal

date: 2017-04-29

tag: 資料結構和算法

目錄

  • TOC

    {:toc}

最小生成樹Minimum Spanning Tree

  • 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。
  • 樹: 無回路，|V|個頂點，一定有|V|-1條邊
  • 生成樹: 包含全部頂點，|V|-1 條邊都在圖裡；邊權重和最小
  • 最小生成樹存在<--->圖聯通；向生成樹中任加一條邊都一定構成回路 
貪心算法

　　“貪”：每一步都要最好的

　　“好”：權重最小的邊

　　需要限制：

　　　　①隻能用圖裡有的邊

　　　　②隻能正好用掉|V|-1條邊

　　　　③不能有回路

Prim算法— 讓一棵小樹長大

思路

-該算法利用了貪心的思想，大體上與dijkstra算法類似，都需要對每一個頂點儲存一個距離值dv和pv，以及一個visit名額，标記是否已經過改點。pv則表示導緻dv改變的最後的頂點。算法有一點不同就是 **dv的定義不同： **dijkstra算法裡dv的定義是源點到各個點之間的最短距離，而prim算法裡的dv則是該樹的所有點到其所有鄰接點之間的最短距離。更新法則：在每一個頂點v被選取以後，檢查它的每一個鄰接點是否受影響，每一個鄰接點w，dw＝min(dw, Cw,v)

代碼描述如下：

步驟 

步驟	 
1	任意選取v1為頂點開始，并将v1收錄進MST
2	v1有三條邊，選取最短邊(v1,v4)為1，并将v4收錄進MST
3	MST={v1,v4}的邊中在選取最小的(v1,v2)為2，将v2收錄進MST
4	MST={v1,v4,v2}，選(v4,v3)為2，将v3收錄進MST
5	不能選(v4,v2)3，會構成回路。是以接着選(v4,v7)4，将v7收錄進MST
6	選(v7,v6)為1，将v6收錄進MST
7	(v7,v5)6，将v7收錄進MST
  • T = O(|V|^2) ---稠密圖合算 

/* 鄰接矩陣存儲 - Prim最小生成樹算法 */
 
Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 傳回未被收錄頂點中dist最小者 */
    Vertex MinV, V;
    WeightType MinDist = INFINITY;
 
    for (V=0; V<Graph->Nv; V++) {
        if ( dist[V]!=0 && dist[V]<MinDist) {
            /* 若V未被收錄，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距離 */
            MinV = V; /* 更新對應頂點 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 傳回對應的頂點下标 */
    else return ERROR;  /* 若這樣的頂點不存在，傳回-1作為标記 */
}
 
int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成樹儲存為鄰接表存儲的圖MST，傳回最小權重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;
     
    /* 初始化。預設初始點下标是0 */
       for (V=0; V<Graph->Nv; V++) {
        /* 這裡假設若V到W沒有直接的邊，則Graph->G[V][W]定義為INFINITY */
           dist[V] = Graph->G[0][V];
           parent[V] = 0; /* 暫且定義所有頂點的父結點都是初始點0 */ 
    }
    TotalWeight = 0; /* 初始化權重和     */
    VCount = 0;      /* 初始化收錄的頂點數 */
    /* 建立包含所有頂點但沒有邊的圖。注意用鄰接表版本 */
    MST = CreateGraph(Graph->Nv);
    E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的邊結點 */
            
    /* 将初始點0收錄進MST */
    dist[0] = 0;
    VCount ++;
    parent[0] = -1; /* 目前樹根是0 */
 
    while (1) {
        V = FindMinDist( Graph, dist );
        /* V = 未被收錄頂點中dist最小者 */
        if ( V==ERROR ) /* 若這樣的V不存在 */
            break;   /* 算法結束 */
             
        /* 将V及相應的邊<parent[V], V>收錄進MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        InsertEdge( MST, E );
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;
         
        for( W=0; W<Graph->Nv; W++ ) /* 對圖中的每個頂點W */
            if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
            /* 若W是V的鄰接點并且未被收錄 */
                if ( Graph->G[V][W] < dist[W] ) {
                /* 若收錄V使得dist[W]變小 */
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新樹 */
                }
            }
    } /* while結束*/
    if ( VCount < Graph->Nv ) /* MST中收的頂點不到|V|個 */
       TotalWeight = ERROR;
    return TotalWeight;   /* 算法執行完畢，傳回最小權重和或錯誤标記 */
}

Kruskal算法— 将森林合并成樹

  • 其思想就是直接了當的貪心，每次都将權值最短的邊收進來：可以将每個頂點都看成一棵樹，然後将權值最短的邊的頂點連接配接起來，在不構成回路的情況下，将這些森林合并成一棵樹。
  • 具體算法設計時我們應該考慮到效率問題，選取權值最小邊時應使用最小堆來存儲結構；還有一個難點就是怎麼判斷新加入一條邊後構不構成回路？這裡可以使用并查集。 
步驟	 
1	選取一條最小邊(v1,v4)為1
2	選取一條最小邊(v6,v7)為1
3	選取一條最小邊(v1,v2)為2
4	選取一條最小邊(v3,v4)為2
5	不能選取最小邊(v2,v4)3會構成回路
6	選取一條最小邊(v7,v4)為4
7	選取一條最小邊(v5,v7)為6
  • T= O(|E|log|E|)

代碼描述： 

/* 鄰接表存儲 - Kruskal最小生成樹算法 */
 
/*-------------------- 頂點并查集定義 --------------------*/
typedef Vertex ElementType; /* 預設元素可以用非負整數表示 */
typedef Vertex SetName;     /* 預設用根結點的下标作為集合名稱 */
typedef ElementType SetType[MaxVertexNum]; /* 假設集合元素下标從0開始 */
 
void InitializeVSet( SetType S, int N )
{ /* 初始化并查集 */
    ElementType X;
 
    for ( X=0; X<N; X++ ) S[X] = -1;
}
 
void Union( SetType S, SetName Root1, SetName Root2 )
{ /* 這裡預設Root1和Root2是不同集合的根結點 */
    /* 保證小集合并入大集合 */
    if ( S[Root2] < S[Root1] ) { /* 如果集合2比較大 */
        S[Root2] += S[Root1];     /* 集合1并入集合2  */
        S[Root1] = Root2;
    }
    else {                         /* 如果集合1比較大 */
        S[Root1] += S[Root2];     /* 集合2并入集合1  */
        S[Root2] = Root1;
    }
}
 
SetName Find( SetType S, ElementType X )
{ /* 預設集合元素全部初始化為-1 */
    if ( S[X] < 0 ) /* 找到集合的根 */
        return X;
    else
        return S[X] = Find( S, S[X] ); /* 路徑壓縮 */
}
 
bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 )
{ /* 檢查連接配接V1和V2的邊是否在現有的最小生成樹子集中構成回路 */
    Vertex Root1, Root2;
 
    Root1 = Find( VSet, V1 ); /* 得到V1所屬的連通集名稱 */
    Root2 = Find( VSet, V2 ); /* 得到V2所屬的連通集名稱 */
 
    if( Root1==Root2 ) /* 若V1和V2已經連通，則該邊不能要 */
        return false;
    else { /* 否則該邊可以被收集，同時将V1和V2并入同一連通集 */
        Union( VSet, Root1, Root2 );
        return true;
    }
}
/*-------------------- 并查集定義結束 --------------------*/
 
/*-------------------- 邊的最小堆定義 --------------------*/
void PercDown( Edge ESet, int p, int N )
{ /* 改編代碼4.24的PercDown( MaxHeap H, int p )    */
  /* 将N個元素的邊數組中以ESet[p]為根的子堆調整為關于Weight的最小堆 */
    int Parent, Child;
    struct ENode X;
 
    X = ESet[p]; /* 取出根結點存放的值 */
    for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
        Child = Parent * 2 + 1;
        if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) )
            Child++;  /* Child指向左右子結點的較小者 */
        if( X.Weight <= ESet[Child].Weight ) break; /* 找到了合适位置 */
        else  /* 下濾X */
            ESet[Parent] = ESet[Child];
    }
    ESet[Parent] = X;
}
 
void InitializeESet( LGraph Graph, Edge ESet )
{ /* 将圖的邊存入數組ESet，并且初始化為最小堆 */
    Vertex V;
    PtrToAdjVNode W;
    int ECount;
 
    /* 将圖的邊存入數組ESet */
    ECount = 0;
    for ( V=0; V<Graph->Nv; V++ )
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
            if ( V < W->AdjV ) { /* 避免重複錄入無向圖的邊，隻收V1<V2的邊 */
                ESet[ECount].V1 = V;
                ESet[ECount].V2 = W->AdjV;
                ESet[ECount++].Weight = W->Weight;
            }
    /* 初始化為最小堆 */
    for ( ECount=Graph->Ne/2; ECount>=0; ECount-- )
        PercDown( ESet, ECount, Graph->Ne );
}
 
int GetEdge( Edge ESet, int CurrentSize )
{ /* 給定目前堆的大小CurrentSize，将目前最小邊位置彈出并調整堆 */
 
    /* 将最小邊與目前堆的最後一個位置的邊交換 */
    Swap( &ESet[0], &ESet[CurrentSize-1]);
    /* 将剩下的邊繼續調整成最小堆 */
    PercDown( ESet, 0, CurrentSize-1 );
 
    return CurrentSize-1; /* 傳回最小邊所在位置 */
}
/*-------------------- 最小堆定義結束 --------------------*/
 
 
int Kruskal( LGraph Graph, LGraph MST )
{ /* 将最小生成樹儲存為鄰接表存儲的圖MST，傳回最小權重和 */
    WeightType TotalWeight;
    int ECount, NextEdge;
    SetType VSet; /* 頂點數組 */
    Edge ESet;    /* 邊數組 */
 
    InitializeVSet( VSet, Graph->Nv ); /* 初始化頂點并查集 */
    ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne );
    InitializeESet( Graph, ESet ); /* 初始化邊的最小堆 */
    /* 建立包含所有頂點但沒有邊的圖。注意用鄰接表版本 */
    MST = CreateGraph(Graph->Nv);
    TotalWeight = 0; /* 初始化權重和     */
    ECount = 0;      /* 初始化收錄的邊數 */
 
    NextEdge = Graph->Ne; /* 原始邊集的規模 */
    while ( ECount < Graph->Nv-1 ) {  /* 當收集的邊不足以構成樹時 */
        NextEdge = GetEdge( ESet, NextEdge ); /* 從邊集中得到最小邊的位置 */
        if (NextEdge < 0) /* 邊集已空 */
            break;
        /* 如果該邊的加入不構成回路，即兩端結點不屬于同一連通集 */
        if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true ) {
            /* 将該邊插入MST */
            InsertEdge( MST, ESet+NextEdge );
            TotalWeight += ESet[NextEdge].Weight; /* 累計權重 */
            ECount++; /* 生成樹中邊數加1 */
        }
    }
    if ( ECount < Graph->Nv-1 )
        TotalWeight = -1; /* 設定錯誤标記，表示生成樹不存在 */
 
    return TotalWeight;
}

Reference

  • 資料結構學習筆記05圖(最小生成樹 Prim Kruskal)
  • 資料結構學習筆記（十）－圖的最小生成樹與拓撲排序 (其他筆記也學習)
  • 資料結構和算法學習筆記：圖論 (個人網站，筆記不錯)
  • 最小生成樹之kruskal算法
  • 最小生成樹之prim算法

C/C++基本文法學習

STL

C++ primer

中國大學MOOC-陳越、何欽銘-資料結構-2017春 資料結構 圖
上一篇: 拓撲排序
下一篇: 使用 kind 部署單機版 Kubernetes 叢集

繼續閱讀