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

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

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

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

注意：最小是指权值最小

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

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

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

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

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

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

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

【2】普里姆算法

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

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

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

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

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

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

【3】普里姆算法的实现

实现代码如下：

1 #include 
      
         2 #include "SeqList.h"  3 #include 
       
          4 using namespace std;  5   6 #define  INFINITY  65535  7   8 template
        
           9 class Graph 10 { 11 private: 12     SeqList
         
           Vertices; 13     DistType **Edges; 14     int nVer, nEdges; 15  16 public: 17     Graph()  18         : Edges(NULL) 19         , nEdges(0) 20         , nVer(0) 21     {} 22     ~Graph() 23     {} 24  25 public: 26  27     istream & operator>>(istream &in) 28     { 29         int v, u, value; 30         int i, j; 31         NameType item; 32         cout << "请输入顶点的个数: " << endl; 33         in >> nVer; 34         cout << "请输入顶点的数据信息: " << endl; 35         for (i = 0; i < nVer; ++i) 36         { 37             in >> item; 38             Vertices.push_back(item);    // 保存全部顶点 39         } 40         /////二维数组的创建并初始化 41         Edges = new DistType*[nVer]; // DistType *ar[10]; 42         for (i = 0; i < nVer; ++i) 43         { 44             Edges[i] = new DistType[nVer]; 45             for (j = 0; j < nVer; ++j) 46             { 47                 Edges[i][j] = 0; 48             } 49         } 50         cout << "请输入边的个数: " << endl; 51         in >> nEdges; 52         cout << "请输入边的信息：" << endl; 53         for (i = 0; i < nEdges; ++i) 54         { 55             in >> v >> u >> value; 56             Edges[v][u] = value; 57             Edges[u][v] = value; 58         } 59         return in; 60     } 61     ostream & operator<<(ostream &out) const 62     { 63         int i, j; 64         out << "顶点信息 " << endl; 65         for (i = 1; i <= nVer; ++i) 66         { 67             out << Vertices[i] << setw(5); 68         } 69         out << endl; 70         out << "矩阵信息：" << endl; 71         out << setw(10); 72         for (i = 1; i <= nVer; ++i) 73         { 74             out << Vertices[i] << setw(5); 75         } 76         out << endl; 77         for (i = 0; i < nVer; ++i) 78         { 79             out << Vertices[i+1] << setw(5); 80             for (j = 0; j < nVer; ++j) 81             { 82                 if (0 == Edges[i][j] && i != j) 83                     Edges[i][j] = INFINITY; 84                 cout << Edges[i][j] << setw(5); 85             } 86             out << endl; 87         } 88         out << endl; 89  90         return out; 91     } 92     //  图采用邻接矩阵存储  最小生成树 普里姆算法 93     void MiniSpanTree()   94     {   95         int min = 0, i = 0, j = 0, k = 0; 96         int* adjvex = new  int[nVer];    // 保存相关顶点下标   97         int* lowcost = new int[nVer];    // 保存相关顶点间边的权值   98         lowcost[0] = 0;         // 初始化第一个权值为0，即V0已加入生成树 99         //lowcost的值为0，在这里就是此下标的顶点已经加入生成树    100         adjvex[0] = 0;          // 初始化第一个顶点下标为0  101 102         for (i = 1; i < nVer; ++i)  //循环除过下标为0外的全部顶点103         {  104             lowcost[i] = Edges[0][i];  // 将v0顶点与之有边的权值存入数组 105             adjvex[i] = 0;             // 并初始化都为v0的下标106         }  107 108         for (i = 1; i < nVer; ++i) 109         {  110             min = INFINITY;  // 初始化最小权值为常数，通常设置为不可能到达的数值111             k = 0;    // 复位112 113             for (j = 1; j < nVer; ++j)  114             {  115                 // 如果两个顶点之间存在边有权值，不为0并且小于min  116                 if (lowcost[j] != 0 && lowcost[j] < min)  117                 {  118                     min = lowcost[j];  // 缓存最小值119                     k = j;    // 将当前最小值的下标缓存入k120                 }121             }  122             cout << "("<< adjvex[k] << "," << k << ")" << endl;   //打印当前顶点边中权值最小的边  123             lowcost[k] = 0;                     // 将当前顶点的权值设为0，表示此顶点已经完成任务  124 125             for (j = 1; j < nVer; ++j)  // 循环所有节点126             {  127                 if (lowcost[j] != 0 && Edges[k][j] < lowcost[j])  128                 {  // 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值129                     lowcost[j] = Edges[k][j]; // 用较小者替换  130                     adjvex[j] = k;  // 将下标为k的顶点存入adjvex131                 }  132             }  133         }134 135         delete []adjvex;136         delete []lowcost;137         adjvex = NULL;138         lowcost = NULL;139     }140 };141 142 template
          
           143 istream & operator>>(istream &in, Graph
           
             &g)144 {145 g >> in;146 return in;147 }148 149 template
            
             150 ostream & operator<<(ostream &out, const Graph
             
               &g)151 {152 g << out;153 return out;154 }155 156 void main()157 {158 Graph
              
                myg;159 cin >> myg;160 cout << "打印所有输入信息：" << endl;161 cout << myg << endl;162 cout << "最小生成树边信息如下：" << endl;163 myg.MiniSpanTree();164 cout << endl;165 }
              
             
            
           
          
         
        
       
      

代码中所引用是头文件SeqList.h从随笔《》拷贝即可，也可以自己另行处理。

 

Good  Good  Study,  Day  Day  Up.

顺序   选择   循环   总结