test_kruskal.cpp

数据结构与算法-程序、素材Kruskal构造算法

//---------------------------------------------------------------------------
/*
    例10-9 Kruskal构造算法的范例程序
    关键：算法10.10 Kruskal算法构造最小生成树
    首先，建立简易的graph_miniTree类
    然后，编写Kruskal构造算法的范例程序模块
*/
#include <algorithm>
#include "Graph_Trav.h"
using namespace std;

//---------------------------------------------------------------------------
// 重载边结点的<运算符
template <class T,class T1>
bool operator<(const EdgeNode<T,T1> &x, const EdgeNode<T,T1> &y)
{  return x.cost < y.cost;  }    // 由小到大排列, 在类外定义

// 建立简易的graph_miniTree类
template <class T,class T1>
class graph_miniTree: public graph_traver<T>
{
    private:
       // 边结点的向量容器
       vector<EdgeNode<T,T1> > Edges_data; // 存放初始化数据的向量
    public:
       // 构造器：创建基于邻接链表的带权值图的Kruskal算法初始化对象
       graph_miniTree(weightedgraphInfo<T,T1> ginfo)
           : graph_traver<T>(ginfo.graph)
       {
           // 保存Kruskal算法的边结点数据
           Edges_data.resize(GetnumEdges());
           for(int i=0; i<GetnumEdges(); i++) {
              Edges_data[i].v1 = ginfo.graph.edges[i].v1;
              Edges_data[i].v2 = ginfo.graph.edges[i].v2;
              Edges_data[i].cost = ginfo.edgesCost[i];
           }
       }
       vector<EdgeNode<T,T1> > Kruskal();
       void print_tree(vector<EdgeNode<T,T1> > tree)
       {
          T1 total=0;
          cout << "起点\t终点\t长度\n";
          for (size_t j=0; j<tree.size(); j++) {
              cout << " " << tree[j].v1 << "\t " << tree[j].v2 << "\t "
                   << tree[j].cost << endl;
          total += tree[j].cost;
          }
          cout << "  网络最小生成树的权值总和为" << total << endl;
       }
};
//---------------------------------------------------------------------------
// 实现
template <class T, class T1>
vector<EdgeNode<T, T1> > graph_miniTree<T, T1>::Kruskal()
{
   int n = GetnumVertices();
   T u, w;
   EdgeNode<T, T1> e;
   vector<EdgeNode<T, T1> > tree;			// 储存最小生成树的向量
   list<T> L;
   list<T>::const_iterator itr;
   // 构造过程初始化
   for(int i=0;  i<GetnumVertices();  i++)
      AdjLists[i].clear();
   // 向量Edges_data排序
   sort(Edges_data.begin(), Edges_data.end());
   i = 0;
   int k = 0;
   bool b;
   while (k<n-1)
   {
      // tree中含有边数 n-1
      // E中选取最短边e = (u, w)
      e = Edges_data[i]; 
      u = e.v1;  w = e.v2;
      b = false;
      // 深度搜索遍历产生路径
      L = dfs(u);							
      // 检查(u,w)并入tree后是否产生回路：若b=true，则产生回路
      if(L.size()>1)
      {
         // 路径长度至少为2才可能产生回路
         itr=L.begin();  itr++;  itr++;
         // 从第2条边的末端顶点开始依次检测其邻接链表是否含有顶点w
         while(itr!=L.end())
         {
             list<T> adjL = AdjLists[GetVertexPos(*itr)];
             b = findVertex(adjL, w);
             if(b)  break;
             itr++;
         }
      }
      if( !b )
      {
         // b为false表示(u, w)并入tree后未产生回路，因此将(u, w)并入tree中
         tree.push_back(e);
         // 更新不带权邻接链表
         AdjLists[GetVertexPos(u)].push_front(e.v2);
         if(!gType)
             AdjLists[GetVertexPos(w)].push_front(e.v1);
         ++k;
      }
      ++i;
   }
   return tree;
}
//---------------------------------------------------------------------------
   // 测试最小生成树Kruskal算法的输入类常量
   const weightedgraphInfo<int,int> Kruskal_inf =
   {
      // 是否是有向图
      false,
      // 顶点数、边数
      6, 10,
      // 顶点信息
      {1,2,3,4,5,6},
      // 边信息
      { {1,2},{1,3},{1,4},{2,3},{2,5},
        {3,4},{3,5},{3,6},{4,6},{5,6} },
      // 权值
      {  6,    1,    5,    5,    3,
         5,    6,    4,    2,    6    }
   };
void main()
{
   // 创建网络对象并用输入数据初始化
   graph_miniTree<int,int> G(Kruskal_inf);
   // 调用对象的Kruskal方法，返回向量后调用print_tree函数输出
   G.print_tree(G.Kruskal());
}