【1】什么是最小生成树？

对于连通的带权图(连通网)G，其生成树也是带权的。

生成树T各边的权值总和称为该树的权。

权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。简记为MST。

注意：最小是指权值最小

一个连通图的生成树是一个极小的连通子图，它包含全部的顶点，但只有足以构成一棵树的n-1条边。

求最小生成树有两种算法：普里姆算法和克鲁斯卡尔算法

不好理解？看不懂？能通俗点不？看个实例哈：

假设你是电信实施工程师，需要为一个镇的九个村庄架设通信网络做设计。

村庄位置大致如下图，之间连线的数字表示村与村间的可通达直线距离。

你们领导要求你必须用最小的成本完成这次任务。你说怎么办？

好，这就是很现实的一个最小生成树案例。且听下面详解。

【2】普里姆算法

利用 普里姆算法 要解决如上问题，首先我们构造图的邻接矩阵。如下图所示：

注意：实际中我们用65535来代表无穷大。

关于普里姆算法以及讲解如下图：

针对上面我们遇到的实际案例，普里姆算法执行循环过程如下图：

每次所选最小边分别如 图1-图8 所示：

最后用所有边把各个顶点连通也就是所谓的最小生成树。

【3】普里姆算法的实现

实现代码如下：

#include 
     
      #include "SeqList.h"#include 
      
       using namespace std;#define  INFINITY  65535template
       
        class Graph{private:    SeqList
        
          Vertices;    DistType **Edges;    int nVer, nEdges;public:    Graph()         : Edges(NULL)        , nEdges(0)        , nVer(0)    {}    ~Graph()    {}public:    istream & operator>>(istream &in)    {        int v, u, value;        int i, j;        NameType item;        cout << "请输入顶点的个数: " << endl;        in >> nVer;        cout << "请输入顶点的数据信息: " << endl;        for (i = 0; i < nVer; ++i)        {            in >> item;            Vertices.push_back(item);    // 保存全部顶点        }        /二维数组的创建并初始化        Edges = new DistType*[nVer]; // DistType *ar[10];        for (i = 0; i < nVer; ++i)        {            Edges[i] = new DistType[nVer];            for (j = 0; j < nVer; ++j)            {                Edges[i][j] = 0;            }        }        cout << "请输入边的个数: " << endl;        in >> nEdges;        cout << "请输入边的信息：" << endl;        for (i = 0; i < nEdges; ++i)        {            in >> v >> u >> value;            Edges[v][u] = value;            Edges[u][v] = value;        }        return in;    }    ostream & operator<<(ostream &out) const    {        int i, j;        out << "顶点信息 " << endl;        for (i = 1; i <= nVer; ++i)        {            out << Vertices[i] << setw(5);        }        out << endl;        out << "矩阵信息：" << endl;        out << setw(10);        for (i = 1; i <= nVer; ++i)        {            out << Vertices[i] << setw(5);        }        out << endl;        for (i = 0; i < nVer; ++i)        {            out << Vertices[i+1] << setw(5);            for (j = 0; j < nVer; ++j)            {                if (0 == Edges[i][j] && i != j)                    Edges[i][j] = INFINITY;                cout << Edges[i][j] << setw(5);            }            out << endl;        }        out << endl;        return out;    }    //  图采用邻接矩阵存储  最小生成树 普里姆算法    void MiniSpanTree()      {          int min = 0, i = 0, j = 0, k = 0;        int* adjvex = new  int[nVer];    // 保存相关顶点下标          int* lowcost = new int[nVer];    // 保存相关顶点间边的权值          lowcost[0] = 0;         // 初始化第一个权值为0，即V0已加入生成树        //lowcost的值为0，在这里就是此下标的顶点已经加入生成树            adjvex[0] = 0;          // 初始化第一个顶点下标为0          for (i = 1; i < nVer; ++i)  //循环除过下标为0外的全部顶点        {              lowcost[i] = Edges[0][i];  // 将v0顶点与之有边的权值存入数组             adjvex[i] = 0;             // 并初始化都为v0的下标        }          for (i = 1; i < nVer; ++i)         {              min = INFINITY;  // 初始化最小权值为常数，通常设置为不可能到达的数值            k = 0;    // 复位            for (j = 1; j < nVer; ++j)              {                  // 如果两个顶点之间存在边有权值，不为0并且小于min                  if (lowcost[j] != 0 && lowcost[j] < min)                  {                      min = lowcost[j];  // 缓存最小值                    k = j;    // 将当前最小值的下标缓存入k                }            }              cout << "("<< adjvex[k] << "," << k << ")" << endl;   //打印当前顶点边中权值最小的边              lowcost[k] = 0;                     // 将当前顶点的权值设为0，表示此顶点已经完成任务              for (j = 1; j < nVer; ++j)  // 循环所有节点            {                  if (lowcost[j] != 0 && Edges[k][j] < lowcost[j])                  {  // 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值                    lowcost[j] = Edges[k][j]; // 用较小者替换                      adjvex[j] = k;  // 将下标为k的顶点存入adjvex                }              }          }        delete []adjvex;        delete []lowcost;        adjvex = NULL;        lowcost = NULL;    }};template
         
          istream & operator>>(istream &in, Graph
          
            &g){    g >> in;    return in;}template
           
            ostream & operator<<(ostream &out, const Graph
            
              &g){    g << out;    return out;}void main(){    Graph
             
               myg;    cin >> myg;    cout << "打印所有输入信息：" << endl;    cout << myg << endl;    cout << "最小生成树边信息如下：" << endl;    myg.MiniSpanTree();    cout << endl;}

代码中所引用是头文件SeqList.h

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define     UM_QUIT     0#define  UM_INPUTR   1#define  UM_PRINT    2#define  UM_INPUTH   3#define  FINDVALUE   4#define  UM_INSERT   5#define  UM_REMOVE   6#define  UM_SORT     7#define  UM_REMOVEALL  8#define  UM_REVERSE    9#define  UM_ERASE      10#define  UM_PVPOS      11#define  MAXSIZE      10#define  INCSIZE      5template 
         
          class SeqList{private:    Type* m_pData;        //数据区域    size_t m_nMaxSize;    //最大容量    size_t m_nLen;        //元素个数public:    SeqList(size_t size = MAXSIZE);    SeqList(const SeqList
          
           & sqList);    SeqList
           
            & operator=(const SeqList
            
             & sqList);    ~SeqList();public:    size_t GetMaxSize() const;    void SetMaxSize(size_t nMaxSize) const;    size_t GetLength() const;    void SetLength(size_t nLen) const;public:    bool IsFull() const;    bool IsEmpty() const;    bool IsElement(const Type& Value);    void Push_Back(const Type& Value);    void Push_Front(const Type& Value);    void At(const size_t pos);    size_t FindPos(const Type& Value);    void Insert(const size_t pos, const Type& Value);    void Remove(const Type& Value);    void Erase(const size_t pos);    void RemoveAll(const Type& Value);    void Sort();    void Reverse();    void Print() const;private:    bool IncSize();    void Swap(const size_t leftpos, const size_t rightpos);};//基本属性函数template 
             
              size_t SeqList
              
               ::GetMaxSize() const{    return m_nMaxSize;}template 
               
                void SeqList
                
                 ::SetMaxSize(size_t nMaxSize) const{    m_nMaxSize = nMaxSize;}template 
                 
                  size_t SeqList
                  
                   ::GetLength() const{    return m_nLen;}template 
                   
                    void SeqList
                    
                     ::SetLength(size_t nLen) const{    m_nLen = nLen;}// 作用：扩充顺序表容量// 当数据数量大于最大容量时，为顺序表增加容量// 增加度量为INCSIZEtemplate 
                     
                      bool SeqList
                      
                       ::IncSize(){    Type* pNewDate = new Type[m_nMaxSize + INCSIZE + 1];    if (NULL == pNewDate)        return false;    memcpy(pNewDate, m_pData, sizeof(Type) * (m_nLen + 1));    m_pData = pNewDate;    m_nMaxSize += INCSIZE;    return true;}//交换数据template 
                       
                        void SeqList
                        
                         ::Swap(const size_t leftpos, const size_t rightpos){    Type temp = m_pData[leftpos];    m_pData[leftpos] = m_pData[rightpos];    m_pData[rightpos] = temp;}//默认复合构造函数template 
                         
                          SeqList
                          
                           ::SeqList(size_t size = MAXSIZE){    m_nMaxSize = size > MAXSIZE ? size : MAXSIZE;    m_pData = new Type[m_nMaxSize + 1];    assert(m_pData != NULL);    m_nLen = 0;}//拷贝构造函数template 
                           
                            SeqList
                            
                             ::SeqList(const SeqList
                             
                              & sqList){    if (this != &sqList)    {        m_pData = new Type[sqList.m_nMaxSize + 1];        if (m_pData != NULL)        {            memcpy(m_pData, sqList.m_pData, sizeof(Type) * (sqList.m_nLen + 1));        }        m_nMaxSize = sqList.m_nMaxSize;        m_nLen = sqList.m_nLen;    }}//赋值函数(思考什么时候调用赋值函数)template 
                              
                               SeqList
                               
                                & SeqList
                                
                                 ::operator=(const SeqList
                                 
                                  & sqList){    m_nLen = sqList.m_nLen;    m_nMaxSize = sqList.m_nMaxSize;    memcpy(m_pData, sqList.m_pData, sizeof(Type) * (sqList.m_nLen + 1));    return *this; }//析构函数template 
                                  
                                   SeqList
                                   
                                    ::~SeqList(){    if (m_pData != NULL)    {        delete []m_pData;        m_pData = NULL;    }    m_nMaxSize = 0;    m_nLen = 0;}//判满template 
                                    
                                     bool SeqList
                                     
                                      ::IsFull() const{    return m_nLen == m_nMaxSize;}//判空template 
                                      
                                       bool SeqList
                                       
                                        ::IsEmpty() const{    return 0 == m_nLen;}//是否是顺序表中元素template 
                                        
                                         bool SeqList
                                         
                                          ::IsElement(const Type& Value){    size_t pos = FindPos(Value);    return 0 != pos;}//从顺序表末尾添加元素template 
                                          
                                           void SeqList
                                           
                                            ::Push_Back(const Type& Value){    if (IsFull() && !IncSize())    //注意写法用意        return;    m_pData[++m_nLen] = Value;}//从顺序表首部添加元素template 
                                            
                                             void SeqList
                                             
                                              ::Push_Front(const Type& Value){    if (IsFull() && !IncSize())        return;    for (size_t i = m_nLen; i > 0; --i)    {        m_pData[i + 1] = m_pData[i];    }    ++m_nLen;    m_pData[1] = Value;}//输出对应索引处的数据template 
                                              
                                               void SeqList
                                               
                                                ::At(const size_t pos){    if (pos <= 0 || pos > m_nLen)        cout << "输入下标有误！" << endl;    else        cout << pos << "位置的数据为：" << m_pData[pos] << endl; }//查找某数据的索引template 
                                                
                                                 size_t SeqList
                                                 
                                                  ::FindPos(const Type& Value){    m_pData[0] = Value;    size_t i = m_nLen;    while (m_pData[i] != Value)    {        --i;    }    return i;}//在索引处插入值template 
                                                  
                                                   void SeqList
                                                   
                                                    ::Insert(const size_t pos, const Type& Value){    if (pos <= 0 || pos > m_nLen + 1)        return;    if (IsFull() && !IncSize())        return;    ++m_nLen;    for (size_t i = m_nLen; i > pos; --i)    {        m_pData[i] = m_pData[i-1];    }    m_pData[pos] = Value;}//移除某个值template 
                                                    
                                                     void SeqList
                                                     
                                                      ::Remove(const Type& Value){    if (IsElement(Value))    {        size_t pos  = FindPos(Value);        Erase(pos);    }    else    {        cout << "输入数据不存在！" << endl;    }}//按索引删除数据template 
                                                      
                                                       void SeqList
                                                       
                                                        ::Erase(const size_t pos){    if (pos <= 0 || pos > m_nLen)    {        cout << "输入错误" << endl;    }    else    {        for (size_t i = pos; i < m_nLen; ++i)        {            m_pData[i] = m_pData[i+1];        }        --m_nLen;        cout << "删除成功！删除后结果如下：" << endl;        Print();    }}//删除全部（删除所有出现在顺序表中的某值）template 
                                                        
                                                         void SeqList
                                                         
                                                          ::RemoveAll(const Type& Value){    if (IsElement(Value))    {        for (size_t i = m_nLen; i > 0; --i)        {            if (m_pData[i] == Value)                Remove(Value);        }        cout << "删除全部成功！删除后结果如下：" << endl;        Print();    }    else    {        cout << "输入的数据不存在！" << endl;    }}//顺序表数据排序template 
                                                          
                                                           void SeqList
                                                           
                                                            ::Sort(){    if (m_nLen > 2)    {        size_t i = 0, j = 0;        for (i = 2; i <= m_nLen; ++i)        {            if (m_pData[i] < m_pData[i - 1])            {                m_pData[0] = m_pData[i];                j = i - 1;                do                 {                    m_pData[j + 1] = m_pData[j];                    --j;                } while(m_pData[j] > m_pData[0]);                m_pData[j + 1] = m_pData[0];            }        }    }}//逆置顺序表template 
                                                            
                                                             void SeqList
                                                             
                                                              ::Reverse(){    if (m_nLen > 2)    {        size_t i = 0, j = 0;        for (i = 1, j = m_nLen; i < j; ++i, --j)        {            Swap(i, j);        }        cout << "逆置结果如下：" << endl;        Print();    }}//打印顺序表数据信息template 
                                                              
                                                               void SeqList
                                                               
                                                                ::Print() const{    cout << "容量：" << m_nMaxSize << endl;    cout << "元素的个数：" << m_nLen << endl;    cout << "数据如下：" << endl;    for (size_t i = 1; i <= m_nLen; ++i)    {        cout << m_pData[i] << " ";    }    cout << endl;}