最小生成树（Kruskal,Prim算法）

2040阅读　0评论2016-05-24　enenshiwo
分类：C/C++

1.Kruskal
  每次找出权值最小的边，用并查集判断构成这两个边的顶点是不是有一个根（即构成回路），若不是则加入这条边，直到加入N-1条。
  1. bool Kruskal(GraphLink& minSpanTree)
  2.     {
  3.         // 1.把顶点、顶点数量放入最小生成树
  4.         minSpanTree._linkTable = new LinkVertex<V, W>[_vertexSize];
  5.         minSpanTree._vertexSize = _vertexSize;
  6.         for (int i = 0; i < _vertexSize; ++i)
  7.         {
  8.             minSpanTree._linkTable[i]._vertex = _linkTable[i]._vertex;
  9.         }
  10.         // 2.将所有的边放到一个最小堆
  11.         Heap<LinkEdge<V,W>*, CompareLinkEdge<V,W>> minHeap;
  12.         for (int i = 0; i < _vertexSize; ++i)
  13.         {
  14.             LinkEdge<V, W>* begin = _linkTable[i]._head;
  15.             while (begin)
  16.             {
  17.                 // 无向图的边需要进行过滤
  18.                 if (begin->_srcIndex < begin->_dstIndex)
  19.                 {
  20.                     minHeap.Push(begin);
  21.                 }

  23.                 begin = begin->_next;
  24.             }
  25.         }
  26.         
  27.         // 3.使用并查集和最小堆构建最小生成树
  28.         UnionFindSet UFSet(_vertexSize);
  29.         int count = _vertexSize;
  30.         while (--count)
  31.         {
  32.             if (minHeap.Empty())
  33.             {
  34.                 return false;
  35.             }

  37.             LinkEdge<V,W>* edge = minHeap.Top();
  38.             minHeap.Pop();
  39.             int src = UFSet.Find(edge->_srcIndex);
  40.             int dst = UFSet.Find(edge->_dstIndex);

  42.             if(src != dst)//若两个不是一个根，即没有构成回路
  43.             {
  44.                 UFSet.Union(src, dst);//合成一个根
  45.                 minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex, edge->_weight);
  46.             }
  47.         }

  49.         return true;
  50.     }
2.Prim

  1. bool Prim(GraphLink& minSpanTree)
  2.     {
  3.         // 1.初始化最小生成树
  4.         minSpanTree._linkTable = new LinkVertex<V, W>[_vertexSize];
  5.         minSpanTree._vertexSize = _vertexSize;
  6.         for (int i = 0; i < _vertexSize; ++i)
  7.         {
  8.             minSpanTree._linkTable[i]._vertex = _linkTable[i]._vertex;
  9.         }

  11.         bool* visitedSet = new bool[_vertexSize];
  12.         memset(visitedSet, false, sizeof(bool)*_vertexSize);

  14.         int src = 0;
  15.         visitedSet[src] = true;
  16.         Heap<LinkEdge<V,W>*, CompareLinkEdge<V,W>> minHeap;

  18.         int count = 1;
  19.         do
  20.         {
  21.             // 2.取出一个顶点所有未访问过的临接边放到一个最小堆里面
  22.             LinkEdge<V, W>* edge = _GetFirstEdge(src);
  23.             while(edge)
  24.             {
  25.                 if (visitedSet[edge->_dstIndex] == false)
  26.                 {
  27.                     minHeap.Push(edge);
  28.                 }

  30.                 edge = _GetNextEdge(src, edge->_dstIndex);
  31.             }

  33.             // 2.选出堆中最小的边加入生成树
  34.             while(!minHeap.Empty() && count < _vertexSize)
  35.             {
  36.                 edge = minHeap.Top();
  37.                 minHeap.Pop();
  38.                 if (visitedSet[edge->_dstIndex] == false)
  39.                 {
  40.                     minSpanTree._AddEdge(edge->_srcIndex, edge->_dstIndex,edge->_weight);
  41.                     visitedSet[edge->_dstIndex] = true;
  42.                     src = edge->_dstIndex;
  43.                     ++count;

  45.                     break;
  46.                 }
  47.             }
  48.         }while (count < _vertexSize);

  50.         return true;
  51.     }

  53.     W _GetWeight(int src, int dst, const W& maxValue)
  54.     {
  55.         if (src == dst)
  56.             return maxValue;

  58.         LinkEdge<V,W>* edge = _linkTable[src]._head;
  59.         while (edge)
  60.         {
  61.             if (edge->_dstIndex == dst)
  62.             {
  63.                 return edge->_weight;
  64.             }

  66.             edge = edge->_next;
  67.         }

  69.         return maxValue;
  70.     }


上一篇：Redis基本指令备忘。
下一篇：图单源最短路径（Dijkstra)