图的最小生成树(Kruskal算法&Prim算法)

最小生成树

在生活中，我们可能会遇到如下的情景。在某个地方分布着N个村庄，现在需要在N个村庄之间修路，每个村庄之间的距离不同，问怎么修最短的路，将各个村庄连接起来。这个问题可以归纳为最小生成树问题，用正则表达式的表述方式描述为：给定一个无向的带权图G=(V,E)，最小生成树的集合为T，T是最小代价连接V中所有顶点所用变E的最小集合，集合T中的边能够形成一棵树，这是因为每个结点（除根节点外）都能向上找到它的一个父节点。

最小生成树的性质

连通图中的每一棵生成树，都是原图的一个极大无环子图。即：从中删去任何一条边，生成树都不再连通，反之，在其中加入任何一条边，都会形成一条回路。

若连通图由n个顶点组成，则其生成树必含n个顶点和n-1条边。因此，构造最小生成树的准则有以下三条：
1. 只能使用图中的边来构造最下生成树
2. 只能使用恰好n-1条边来连接图中的n个顶点。
3. 选用的n-1条边不能构成回路

构造最小生成树的算法包括：Kruskal算法和Prim算法。这两个算法均采用了逐步求解的贪心策略。

贪心策略指的是在解决某一个问题时，总是做出当前看起来最好的选择，不是整体最优的，只是局部最优。贪心算法不是对所有的问题都能得到整体最优解。

Kruskal算法

首先，将每个顶点放入其自身的数据集合中。然后，按照权值的升序来选择边。当选择每条边时，判断定义边的顶点是否在不同的数据集中。如果是，将此边插入最小生成树的集合中，同时，将集合中包含每个顶点的联合体取出，如果不是，就移动到下一条边。重复这个过程直到所有的边都探查过。

typedef Graph<V, W, IsDirect> Self;
     // 最小生成树---克鲁斯卡尔算法；了解普里姆算法
     Self Kruskal()
     {
          Self g;//创建一个图，保存当前图
          g._v = _v;
          g._linkEdges.resize(_v.size());
          vector<PNode> edges;//用来保存边,滤过重复边
          for (size_t i = 0; i < _v.size(); ++i)
          {
              PNode pCur = _linkEdges[i];
              while (pCur)//遍历
              {
                   if (IsDirect || !IsDirect && (pCur->_src < pCur->_dst))
                        edges.push_back(pCur);
                   pCur = pCur->_pNext;
              }
          }
          //比较权值的仿函数，重载括号
          class Compare
          {
          public:
              bool operator()(const PNode left, const PNode right)
              {
                   return left->_weight < right->_weight;
              }
          };
          sort(edges.begin(), edges.end(), Compare());//按照权值排序

          size_t count = _v.size() - 1;//n个顶点，n-1条边
          UnionFindSet u(_v.size());//创建一个并查集
          for (size_t i = 0; i < edges.size(); ++i)
          {
              PNode pCur = edges[i];
              size_t srcRoot = u.FindRoot(pCur->_src);//找到组长元素
              size_t dstRoot = u.FindRoot(pCur->_dst);
              if (srcRoot != dstRoot)//不在一个组，即没有形成回路，加边
              {
                   g.AddEdge(_v[pCur->_src], _v[pCur->_dst], pCur->_weight);
                   if (!IsDirect)//无向图
                        g.AddEdge(_v[pCur->_dst], _v[pCur->_src], pCur->_weight);
                   u.Union(pCur->_src,pCur->_dst);//合并两个集合
                   count--;
                   if (count == 0)
                        break;
              }
          }
          if (count > 0)
              cout << "最小生成树非法" << endl;
          return g;
     }

Prim算法

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。

Prim算法指的是从任意一个顶点开始，每次选择一个与当前顶点集最近的一个顶点，并将两顶点之间的边加入到树中。Prim算法在找当前最近顶点时使用到了贪婪算法。