一個最小生成樹算法的C++實(shí)現(xiàn)

最近在跟同事們聊到圖論的最小生成樹問題，以及如何編寫算法，用于工程中解決實(shí)際問題，這里我也就順便簡單寫幾句。

什么是最小生成樹？

現(xiàn)在假設(shè)有一個很實(shí)際的問題：我們要在n個城市中建立一個通信網(wǎng)絡(luò)，則連通這n個城市需要布置n-1條通信線路，這個時(shí)候我們需要考慮如何在成本最低的情況下建立這個通信網(wǎng)？
于是我們就可以引入連通圖來解決我們遇到的問題，n個城市就是圖上的n個頂點(diǎn)，然后，邊表示兩個城市的通信線路，每條邊上的權(quán)重就是我們搭建這條線路所需要的成本，所以現(xiàn)在我們有n個頂點(diǎn)的連通網(wǎng)可以建立不同的生成樹，每一顆生成樹都可以作為一個通信網(wǎng)，當(dāng)我們構(gòu)造這個連通網(wǎng)所花的成本最小時(shí)，搭建該連通網(wǎng)的生成樹，就稱為最小生成樹。

普里姆算法

構(gòu)造最小生成樹有很多算法，但是他們都是利用了最小生成樹的同一種性質(zhì)：MST性質(zhì)（假設(shè)N=(V,{E})是一個連通網(wǎng)，U是頂點(diǎn)集V的一個非空子集，如果（u，v）是一條具有最小權(quán)值的邊，其中u屬于U，v屬于V-U，則必定存在一顆包含邊（u，v）的最小生成樹），下面就介紹使用MST性質(zhì)生成最小生成樹的算法：普里姆算法。

算法思路：首先從圖中的一個起點(diǎn)a開始，把a(bǔ)加入U(xiǎn)集合，然后，尋找從與a有關(guān)聯(lián)的邊中，權(quán)重最小的那條邊并且該邊的終點(diǎn)b在頂點(diǎn)集合：（V-U）中，我們也把b加入到集合U中，并且輸出邊（a，b）的信息，這樣我們的集合U就有：{a,b}，然后，我們尋找與a關(guān)聯(lián)和b關(guān)聯(lián)的邊中，權(quán)重最小的那條邊并且該邊的終點(diǎn)在集合：（V-U）中，我們把c加入到集合U中，并且輸出對應(yīng)的那條邊的信息，這樣我們的集合U就有：{a,b,c}這三個元素了，一次類推，直到所有頂點(diǎn)都加入到了集合U。

例如存在下面的連通圖：


image.png

假如我們先選擇V0做為開始頂點(diǎn)，如上圖所示，與V0直接相連的有V1、V5、V6，其中V6的權(quán)重最小，我們選擇所V6加入到生成樹集合中。接下來觀察V0和V6，繼續(xù)尋找一條到其他頂點(diǎn)的權(quán)重最小的邊，可以看到V6->V1的權(quán)重最小，把V1加入到生成樹中。以此類推，直到所有頂點(diǎn)完成選擇。

一個C++算法實(shí)現(xiàn)

拿前面的圖做為例子，具體實(shí)現(xiàn)下面的代碼：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#include <string>
#include <vector>
#include <set>
#include <map>

// 鄰邊
struct SEdge
{
    std::string strVertexFrom;
    std::string strVertexTo;
    int nEdgeWeight;

    SEdge(const std::string& strFrom = "", const std::string& strTo = "", int nWeight = 0)
    {
        strVertexFrom = strFrom;
        strVertexTo = strTo;
        nEdgeWeight = nWeight;
    }
};

// 鄰接矩陣
class CThroughMatrix
{
    // 頂點(diǎn)集合
    std::set<std::string> m_setVertex;

    // 鄰邊集合
    typedef std::map<std::string, int> MAP_TOVERTEX_WEIGHT_t;
    std::map<std::string, MAP_TOVERTEX_WEIGHT_t> m_mapEdge;

public:
    CThroughMatrix()
    {
    }
    ~CThroughMatrix()
    {
    }

    // 新增頂點(diǎn)名稱
    void addVertex(const std::string& strVertex)
    {
        if (m_setVertex.find(strVertex) == m_setVertex.end())
        {
            m_setVertex.insert(strVertex);

            printf("add vertex:[%s] \n", strVertex.c_str());
        }
    }

    // 移除指定頂點(diǎn)
    void delVertex(const std::string& strVertex)
    {
        if (m_setVertex.find(strVertex) == m_setVertex.end())
            return;

        // 找該頂點(diǎn)的入度，刪除鄰邊
        for (auto iter = m_mapEdge.begin(); iter != m_mapEdge.end(); ++iter)
        {
            MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;

            auto iterEdge = mapToVertexWeight.find(strVertex);
            if (iterEdge != mapToVertexWeight.end())
            {
                printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);

                mapToVertexWeight.erase(iterEdge);
                if (mapToVertexWeight.empty())
                {
                    m_mapEdge.erase(iter);
                }
            }
        }
        
        // 找該頂點(diǎn)的出度，刪除鄰邊
        auto iter = m_mapEdge.find(strVertex);
        if (iter != m_mapEdge.end())
        {
            MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;

            for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
            {
                printf("delete edge:[%s -> %s] weight:[%d] \n", iter->first.c_str(), iterEdge->first.c_str(), iterEdge->second);
            }

            m_mapEdge.erase(iter);
        }

        // 刪除頂點(diǎn)
        m_setVertex.erase(strVertex);
    }

    // 增加鄰邊
    void addEdge(const std::string& strVertex1, const std::string& strVertex2, int nWeight)
    {
        // 檢查頂點(diǎn)是否存在
        if (m_setVertex.find(strVertex1) == m_setVertex.end())
            return;
        if (m_setVertex.find(strVertex2) == m_setVertex.end())
            return;

        // 添加 strVertex1 -> strVertex2
        {
            MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex1];
            auto iterEdge = mapToVertexWeight.find(strVertex2);
            if (iterEdge != mapToVertexWeight.end())
            {
                iterEdge->second = nWeight;

                printf("update edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
            }
            else
            {
                 mapToVertexWeight.insert( std::make_pair(strVertex2, nWeight) );

                 printf("add edge:[%s -> %s] weight:[%d] \n", strVertex1.c_str(), strVertex2.c_str(), nWeight);
            }
        }

        // 添加 strVertex2 -> strVertex1
        {
            MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = m_mapEdge[strVertex2];
            auto iterEdge = mapToVertexWeight.find(strVertex1);
            if (iterEdge != mapToVertexWeight.end())
            {
                iterEdge->second = nWeight;

                printf("update edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
            }
            else
            {
                 mapToVertexWeight.insert( std::make_pair(strVertex1, nWeight) );

                 printf("add edge:[%s -> %s] weight:[%d] \n", strVertex2.c_str(), strVertex1.c_str(), nWeight);
            }
        }
    }

    // 刪除鄰邊
    void delEdge(const std::string& strVertex1, const std::string& strVertex2)
    {
        // 檢查頂點(diǎn)是否存在
        if (m_setVertex.find(strVertex1) == m_setVertex.end())
            return;
        if (m_setVertex.find(strVertex2) == m_setVertex.end())
            return;

        // 刪除 strVertex1 -> strVertex2
        {
            auto iter = m_mapEdge.find(strVertex1);
            if (iter != m_mapEdge.end())
            {
                MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;

                auto iterEdge = mapToVertexWeight.find(strVertex2);
                if (iterEdge != mapToVertexWeight.end())
                {
                    mapToVertexWeight.erase(iterEdge);
                    if (mapToVertexWeight.empty())
                    {
                        m_mapEdge.erase(strVertex1);
                    }

                    printf("delete edge:[%s -> %s] \n", strVertex1.c_str(), strVertex2.c_str());
                }
            }
        }

        // 刪除 strVertex2 -> strVertex1
        {
            auto iter = m_mapEdge.find(strVertex2);
            if (iter != m_mapEdge.end())
            {
                MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;

                auto iterEdge = mapToVertexWeight.find(strVertex1);
                if (iterEdge != mapToVertexWeight.end())
                {
                    mapToVertexWeight.erase(iterEdge);
                    if (mapToVertexWeight.empty())
                    {
                        m_mapEdge.erase(strVertex1);
                    }

                    printf("delete edge:[%s -> %s] \n", strVertex2.c_str(), strVertex1.c_str());
                }
            }
        }
    }

    
    // 計(jì)算最小生成樹
    void calcMinWeightTreeByPrim(std::vector<SEdge>& vecEdge) const
    {
        std::set<std::string> setVertexLeft, setVertexRight = m_setVertex;

        if (setVertexRight.empty())
        {
            printf("no vertex! \n");
            return;
        }

        // 初使合左右頂點(diǎn)集合
        const std::string& strVertex = *setVertexRight.begin();
        setVertexLeft.insert(strVertex);
        setVertexRight.erase(strVertex);

        while (!setVertexRight.empty())
        {
            // 尋找從左邊頂點(diǎn)到右邊頂點(diǎn)的最小鄰邊

            std::string strFrom = "", strTo = "";
            int nMinWeight = -1;

            for (auto iterLeft = setVertexLeft.begin(); iterLeft != setVertexLeft.end(); ++iterLeft)
            {
                const std::string& strLeft = (*iterLeft);

                auto iter = m_mapEdge.find(strLeft);
                if (iter == m_mapEdge.end())
                {
                    printf("vertex:[%s] no edge! \n", strLeft.c_str());
                    return;
                }

                const MAP_TOVERTEX_WEIGHT_t& mapToVertexWeight = iter->second;

                for (auto iterEdge = mapToVertexWeight.begin(); iterEdge != mapToVertexWeight.end(); ++iterEdge)
                {
                    const std::string& strRight = iterEdge->first;

                    // 只檢查到右邊頂點(diǎn)的邊
                    if (setVertexRight.find(strRight) == setVertexRight.end())
                        continue;

                    if (nMinWeight < 0 || iterEdge->second < nMinWeight)
                    {
                        strFrom = strLeft;
                        strTo = strRight;
                        nMinWeight = iterEdge->second;
                    }
                }
            }

            if (strTo != "")
            {
                SEdge stEdge(strFrom, strTo, nMinWeight);
                vecEdge.push_back(stEdge);

                setVertexLeft.insert(strTo);
                setVertexRight.erase(strTo);
            }
        }
    }
};

int main(int argc, char* argv[])
{
    CThroughMatrix throughMatrix;    
    
    throughMatrix.addVertex("V0");
    throughMatrix.addVertex("V1");
    throughMatrix.addVertex("V2");
    throughMatrix.addVertex("V3");
    throughMatrix.addVertex("V4");
    throughMatrix.addVertex("V5");
    throughMatrix.addVertex("V6");

    throughMatrix.addEdge("V0", "V1", 4);
    throughMatrix.addEdge("V0", "V5", 5);
    throughMatrix.addEdge("V0", "V6", 2);
   
    throughMatrix.addEdge("V1", "V0", 4);
    throughMatrix.addEdge("V1", "V2", 2);
    throughMatrix.addEdge("V1", "V6", 1);
   
    throughMatrix.addEdge("V2", "V1", 2);
    throughMatrix.addEdge("V2", "V3", 10);
    throughMatrix.addEdge("V2", "V6", 3);

    throughMatrix.addEdge("V3", "V2", 10);
    throughMatrix.addEdge("V3", "V4", 6);
    throughMatrix.addEdge("V3", "V6", 7);

    throughMatrix.addEdge("V4", "V3", 6);
    throughMatrix.addEdge("V4", "V5", 1);
    throughMatrix.addEdge("V4", "V6", 4);

    throughMatrix.addEdge("V5", "V0", 5);
    throughMatrix.addEdge("V5", "V4", 1);
    throughMatrix.addEdge("V5", "V6", 8);

    throughMatrix.addEdge("V6", "V0", 2);
    throughMatrix.addEdge("V6", "V1", 1);
    throughMatrix.addEdge("V6", "V2", 3);
    throughMatrix.addEdge("V6", "V3", 7);
    throughMatrix.addEdge("V6", "V4", 4);
    throughMatrix.addEdge("V6", "V5", 8);

    std::vector<SEdge> vecEdge;
    throughMatrix.calcMinWeightTreeByPrim(vecEdge);

    for (auto iterEdge = vecEdge.begin(); iterEdge != vecEdge.end(); ++iterEdge)
    {
        SEdge& stEdge = (*iterEdge);

        printf("edge[%s -> %s] weight:[%d] \n", stEdge.strVertexFrom.c_str(), stEdge.strVertexTo.c_str(), stEdge.nEdgeWeight);
    }

    return 0;
}

編譯：
g++ -o testprim testprim.cpp -std=c++11

運(yùn)行結(jié)果如下：

add vertex:[V0] 
add vertex:[V1] 
add vertex:[V2] 
add vertex:[V3] 
add vertex:[V4] 
add vertex:[V5] 
add vertex:[V6] 
add edge:[V0 -> V1] weight:[4] 
add edge:[V1 -> V0] weight:[4] 
add edge:[V0 -> V5] weight:[5] 
add edge:[V5 -> V0] weight:[5] 
add edge:[V0 -> V6] weight:[2] 
add edge:[V6 -> V0] weight:[2] 
update edge:[V1 -> V0] weight:[4] 
update edge:[V0 -> V1] weight:[4] 
add edge:[V1 -> V2] weight:[2] 
add edge:[V2 -> V1] weight:[2] 
add edge:[V1 -> V6] weight:[1] 
add edge:[V6 -> V1] weight:[1] 
update edge:[V2 -> V1] weight:[2] 
update edge:[V1 -> V2] weight:[2] 
add edge:[V2 -> V3] weight:[10] 
add edge:[V3 -> V2] weight:[10] 
add edge:[V2 -> V6] weight:[3] 
add edge:[V6 -> V2] weight:[3] 
update edge:[V3 -> V2] weight:[10] 
update edge:[V2 -> V3] weight:[10] 
add edge:[V3 -> V4] weight:[6] 
add edge:[V4 -> V3] weight:[6] 
add edge:[V3 -> V6] weight:[7] 
add edge:[V6 -> V3] weight:[7] 
update edge:[V4 -> V3] weight:[6] 
update edge:[V3 -> V4] weight:[6] 
add edge:[V4 -> V5] weight:[1] 
add edge:[V5 -> V4] weight:[1] 
add edge:[V4 -> V6] weight:[4] 
add edge:[V6 -> V4] weight:[4] 
update edge:[V5 -> V0] weight:[5] 
update edge:[V0 -> V5] weight:[5] 
update edge:[V5 -> V4] weight:[1] 
update edge:[V4 -> V5] weight:[1] 
add edge:[V5 -> V6] weight:[8] 
add edge:[V6 -> V5] weight:[8] 
update edge:[V6 -> V0] weight:[2] 
update edge:[V0 -> V6] weight:[2] 
update edge:[V6 -> V1] weight:[1] 
update edge:[V1 -> V6] weight:[1] 
update edge:[V6 -> V2] weight:[3] 
update edge:[V2 -> V6] weight:[3] 
update edge:[V6 -> V3] weight:[7] 
update edge:[V3 -> V6] weight:[7] 
update edge:[V6 -> V4] weight:[4] 
update edge:[V4 -> V6] weight:[4] 
update edge:[V6 -> V5] weight:[8] 
update edge:[V5 -> V6] weight:[8] 
edge[V0 -> V6] weight:[2] 
edge[V6 -> V1] weight:[1] 
edge[V1 -> V2] weight:[2] 
edge[V6 -> V4] weight:[4] 
edge[V4 -> V5] weight:[1] 
edge[V4 -> V3] weight:[6]

可以看到最小生成樹的生成過程為：
edge[V0 -> V6] weight:[2]
edge[V6 -> V1] weight:[1]
edge[V1 -> V2] weight:[2]
edge[V6 -> V4] weight:[4]
edge[V4 -> V5] weight:[1]
edge[V4 -> V3] weight:[6]

即如下的圖：


image.png
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容