資料結構 筆記：最小生成樹（Kruskal）

最小生成樹的特征：

-選取的邊是圖中權值較小的邊

-所有邊連接配接後不構成回路

既然最小生成樹關心的是如何選擇n-1條邊，那麼是否可以直接以邊為核心進行算法設計？

-由4個頂點構成圖，選擇3條權值最小的邊

如何判斷新選擇的邊與已選擇的邊是否構成回路？

技巧：前驅标記數組

-定義數組：Array<int> p(vCount());

-數組元素的意義：

·p[n]表示頂點n在邊的連接配接通路上的另一端頂點

最小生成樹算法的核心步驟（Kruskal）

-定義前驅标記數組：Array<int> p(vCount());

-擷取目前圖中的所有邊，并存儲于edges數組中

-對數組edges按照權值進行排序

-利用p數組在edges數組中選擇前n-1不構成回路的邊

 關鍵的find查找函數

int find(Array<int>& p,int v)
{
    while(p[v] != -1)
    {
        v = p[v];
    }
    return v;
}

SharedPointer<Array<Edge<E>>> kruskal(const bool MINMUN = true)
    {
        LinkQueue<Edge<E>> ret;
        SharedPointer <Array<Edge<E>>> edges = getUndirectedEdges();

        DynamicArray<int> p(vCount());

        for(int i = 0;i<p.length();i++)
        {
            p[i] = -1;
        }

        Sort::Shell(*edges,MINMUN );

        for(int i = 0;(i < edges->length()) && (ret.length() < (vCount() -1));i++)
        {
            int b = find(p,(*edges)[i].b);
            int e = find(p,(*edges)[i].e);

            if(b != e)
            {
                p[e] = b;

                ret.add((*edges)[i]);
            }
        }

        if(ret.length() != (vCount() -1))
        {
            //抛出異常
        }

        return toArray(ret);

    }
           

總結：

-Prim算法以頂點為核心尋找最小生成樹，不夠直接

-Kruskal算法以邊為核心尋找最小生成樹，直覺簡單

-Kruskal算法中的關鍵是前驅标記數組的使用

-前驅标記數組用于判斷選擇的邊是否會造成回路