一、最小生成树(MST)

　　①、生成树的代价：设G=（V，E）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。 

　　②、最小生成树：在图G所有生成树中，代价最小的生成树称为最小生成树。

　　最小生成树的概念可以应用到许多实际问题中。 例：在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？

　　③、MST性质：假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集。若(u, v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u, v)的最小生成树。

二、Prim算法

　　①基本思想：设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是G的最小生成树， T的初始状态为U={u0}（u0∈V），TE={ }，重复执行下述操作：在所有u∈U，v∈V-U的边中找一条代价最小的边(u, v)并入集合TE，同时v并入U，直至U=V。

　　关键:是如何找到连接U和V-U的最短边，利用MST性质，可以用下述方法构造候选最短边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边。

　　②数据结构设计

　　数组lowcost[n]：用来保存集合V-U中各顶点与集合U中顶点最短边的权值，lowcost[v]=0表示顶点v已加入最小生成树中；

　　数组adjvex[n]：用来保存依附于该边（集合V-U中各顶点与集合U中顶点的最短边）在集合U中的顶点。

　　如何用数组lowcost和adjvex表示候选最短边集？

　　lowcost[i]=w；表示顶点vi和顶点vk之间的权值为w，

　　adjvex[i]=k；其中：vi∈ V-U 且vk ∈U。

　　③Prim算法——伪代码

1. 初始化两个辅助数组lowcost和adjvex；2. 输出顶点u0，将顶点u0加入集合U中；3. 重复执行下列操作n-1次   3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k；   3.2 输出顶点k和对应的权值；   3.3 将顶点k加入集合U中；   3.4 调整数组lowcost和adjvex；

　　④C++实现

1 #include
     
       2 #include
      
        3 using  namespace std; 4  5 #define MAX 100 6 #define MAXCOST 0x7fffffff 7  8 int graph[MAX][MAX]; 9 10 /*方法二*/11 struct Node12 {13     int lowcost;// 权值14     int adjvex;// 候选最短边的邻接点15 };16 Node shortEdge[MAX];// 候选最短边集合17 void prim2(int graph[][MAX], int n)18 {    19      // 初始化辅助数组shortEdge,所有点到点1的权值20     for (int i = 2; i <= n; i++)21     {22         shortEdge[i].lowcost = graph[1][i];23         shortEdge[i].adjvex = 1;24     }25     shortEdge[1].lowcost = 0;// 将顶点1加入集合U26     for (int i = 2; i <= n; i++)27     {28         // 寻找最短边的邻接点k29         int k = 0, min = MAXCOST;30         for (int j = 2; j <= n; j++)31         {32             if (min >shortEdge[j].lowcost&&shortEdge[j].lowcost!=0)33             {34                 min = shortEdge[j].lowcost;35                 k = j;36             }37         }38         cout << "(" << k << shortEdge[k].adjvex << ")" << shortEdge[k].lowcost;39         shortEdge[k].lowcost = 0;// 将顶点k加入结合U中40         for (int j = 2; j <= n; j++)41         {42             if (graph[k][j] < shortEdge[j].lowcost)43             {44                 shortEdge[j].lowcost = graph[k][j];45                 shortEdge[j].adjvex = k;46             }47         }48     }49 }50 51 int main()52 {53     int i, j, k, m, n;54     int x, y, cost;55     ifstream in("input.txt");56     in >> m >> n;//m=顶点的个数，n=边的个数57     //初始化图G58     for (i = 1; i <= m; i++)59     {60         for (j = 1; j <= m; j++)61         {62             graph[i][j] = MAXCOST;63         }64     }65     //构建图G66     for (k = 1; k <= n; k++)67     {68         in >> i >> j >> cost;69         graph[i][j] = cost;70         graph[j][i] = cost;71     }    72     prim2(graph, m);73     system("pause");74     return 0;75 }
      
     

三、Kruskal算法

　　①基本思想：设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。

　　②数据结构设计：因为Kruskal算法是依次对图中的边进行操作，因此考虑用边集数组存储图中的边，为了提高查找最短边的速度，可以先对边集数组按边上的权值排序。

1 struct EdgeType 2 { 3     int from, to;// 边依附的两个顶点 4     int weight;// 边的权值 5 }; 6  7 template
     
       8 struct EdgeGraph 9 {10     T vertex[Maxvertex];// 存放顶点信息    11     vector
      
        edge;// 存放边的数组(用vector便于排序)12     int vertexNum, edgeNum;//顶点数和边数13 };
      
     

　　③Kruskal算法——伪代码

1. 初始化：U=V；  TE={ }； 2. 循环直到T中的连通分量个数为1       2.1 在E中寻找最短边(u，v);     2.2 如果顶点u、v位于T的两个不同连通分量，则           2.2.1 将边(u，v)并入TE；           2.2.2 将这两个连通分量合为一个；     2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取；

　　④C++实现

#include
     
      #include
      
       #include
       
        #include
        
         using  namespace std;const int Maxvertex = 10;// 最多顶点数const int MaxEdge = 100;// 最多边数struct EdgeType{    int from, to;// 边依附的两个顶点    int weight;// 边的权值};template
         
          struct EdgeGraph{    T vertex[Maxvertex];// 存放顶点信息        vector
          
            edge;// 存放边的数组(用vector便于排序) int vertexNum, edgeNum;//顶点数和边数};int FindRoot(int parent[], int v)// 求顶点的双亲结点{ int t = v; while(parent[t]> -1) t = parent[t]; return t;}void Kruskal(EdgeGraph
           
             G){ int parent[Maxvertex]; for (int i = 0; i < G.vertexNum; i++) parent[i] = -1;// 表示顶点i没有双亲结点 for (int num = 0, i = 0; i < G.edgeNum; i++) { int vex1 = FindRoot(parent, G.edge[i].from); int vex2 = FindRoot(parent, G.edge[i].to); if (vex1 != vex2) { cout << "(" << G.edge[i].from << G.edge[i].to << ")" << endl; parent[vex2] = vex1;// 合并生成树 num++; if (num == G.vertexNum - 1) return; } }}bool sort_by_weight(EdgeType&k1, EdgeType&k2){ return k1.weight < k2.weight;}int main(){ EdgeGraph
            
              Edgraph;// 存放图的信息 ifstream in("input.txt"); in >> Edgraph.vertexNum >> Edgraph.edgeNum; //构建图G for (int k = 0; k 
             
              > temp.from >> temp.to >> temp.weight; Edgraph.edge.push_back(temp); } // 将边按照权值排序 sort(Edgraph.edge.begin(), Edgraph.edge.end(), sort_by_weight); Kruskal(Edgraph); system("pause"); return 0;}
             
            
           
          
         
        
       
      
     

 

input.txt6 101 2 61 3 11 4 52 3 52 5 33 4 53 5 63 6 44 6 25 6 6