Chinaunix首页 | 论坛 | 博客
  • 博客访问: 485988
  • 博文数量: 80
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1916
  • 用 户 组: 普通用户
  • 注册时间: 2013-07-11 22:01
个人简介

从事实时计算多年,熟悉jstorm/spark/flink/kafka/rocketMq, 热衷于开源,希望在这里和前辈们一起学习与分享,得到长足的进步!邮箱:hustfxj@gmail.com 我的githup地址是:https://github.com/hustfxj。欢迎和大家一起交流探讨问题。

文章分类

全部博文(80)

文章存档

2017年(11)

2015年(3)

2014年(33)

2013年(33)

分类: C/C++

2013-11-06 14:21:57

一个无向带权图G=(V,E),其中n个顶点Vertex,以及连接各个顶点之间的边Edge,可能有些顶点之间没有边,每条边上的权值都是非负值。

生成树:

G的一个子图,包含了所有的Vertex,和部分的Edge。

最小生成树:

所有的生成树中,各条Edge上的权值总和最小的一个。

例子:设计通信网络时,各个城市之间铺设线路,最经济的方案。

最小生成树性质:

G=(V,E),

S是V的真子集,

如果u在S中,v在V-S中,且(u,v)是图的一条边,称之为特殊边,且(u,v)是所有特殊边中最短的,

那么,(u,v)这条边一定在最小生成树中。

Prim算法:

任意指定一个顶点作为起始点,放在S中。

每一步将最短的特殊边放入S中,需要n-1步,即可把所有的其他的点放入S中。算法结束。


对于这个图,Prim算法的过程为:

Kruskal算法:

不停地循环,每一次都寻找两个顶点,这两个顶点不在同一个真子集里,且边上的权值最小。

把找到的这两个顶点联合起来。

初始时,每个顶点各自属于自己的子集合,共n个子集合。

每一步操作,都会将两个子集合融合成一个,进而减少一个子集合。

结束时,所有的顶点都在同一个子集合里,这个子集合就是最小生成树。

例子:


算法过程为:

这两种方法的实现代码如下:
最小生成树头文件CMinStree.h

点击(此处)折叠或打开

  1. //最小生成树算法
  2. #include<vector>
  3. #define NN 6
  4. using namespace std;

  5. struct MinStreeEdge
  6. {
  7.     int _pos1; //节点1
  8.     int _pos2; //节点2
  9.     int _value; //两节点间的权重
  10.     bool operator<(const MinStreeEdge& v2)
  11.     {
  12.         return this->_value<v2._value;
  13.     }
  14.     MinStreeEdge& operator=(const MinStreeEdge& v2)
  15.     {
  16.         this->_pos1=v2._pos1;
  17.         this->_pos2=v2._pos2;
  18.         this->_value=v2._value;
  19.         return *this;
  20.     }
  21. };
  22. class CMinStree
  23. {
  24. public:
  25.     CMinStree();
  26.     ~CMinStree();
  27. public:
  28.     void Prim(int map[][NN],int N); //基于prim算法的最小树问题
  29.     void kruskal(int map[][NN]); //基于kruskal算法的最小树问题
  30. private:
  31.     vector<MinStreeEdge> m_treeEdges;
  32. };
最小生成树文件CMinStree.cpp:

点击(此处)折叠或打开

  1. #include"stdaxf.h"
  2. #include"CMinStree.h"
  3. #include"CMinHeap.h"

  4. CMinStree::CMinStree()
  5. {
  6.     //测试数据
  7.         int E[6][6] = { { -1, 6, 1, 5, -1, -1 }, { 6, -1, 5, -1, 3, -1 },
  8.                 { 1, 5, -1, 5, 6, 4 }, { 5, -1, 5, -1, -1, 2 },
  9.                 { -1, 3, 6, -1, -1, 6 }, { -1, -1, 4, 2, 6, -1 } };
  10.     //Prim(E,6);
  11.     //kruskal(E);

  12. }
  13. CMinStree::~CMinStree()
  14. {
  15. }
  16. void CMinStree::kruskal(int map[][NN]) //基于kruskal算法的最小树问题
  17. {
  18.     CMinHeap<MinStreeEdge> MinQueue(NN*(NN-1)/2); //CMinHeap是最小队列
  19.     //初始化最小队列
  20.     for(int i=0;i<NN;i++)
  21.         for(int j=i+1;j<NN;j++)
  22.         {
  23.             if(map[i][j]!=-1) //两节点不可到达,用-1表示
  24.             {
  25.                 //将可到达的边加入到最小队列中
  26.                 MinStreeEdge tempEdge;
  27.                 tempEdge._pos1=i;
  28.                 tempEdge._pos2=j;
  29.                 tempEdge._value=map[i][j];
  30.                 MinQueue.insert(tempEdge);
  31.             }
  32.         }
  33.         int visited[NN]; //初始化子集,用数值带下标识子集
  34.         for(int k=0;k<NN;k++)
  35.             visited[k]=k;
  36.         int count=NN-1; //生成最小树一共多少个边
  37.         while(count--)
  38.         {
  39.             MinStreeEdge vistedEdge=MinQueue.ExtractMin();
  40.             if(visited[vistedEdge._pos1]==visited[vistedEdge._pos2]) continue; //判断是不是在同一子集上
  41.             
  42.             //将上述两个子集融合到一个子集中
  43.             int num=visited[vistedEdge._pos2];
  44.             for(int i=0;i<NN;i++)
  45.             {
  46.                 if(visited[i]==num)
  47.                     visited[i]=visited[vistedEdge._pos1];
  48.             }

  49.             //记录下选择的边
  50.             m_treeEdges.push_back(vistedEdge);
  51.         }


  52. }
  53. void CMinStree::Prim(int map[][NN],int N)
  54. {
  55.     int* dis=(int*)calloc(N,sizeof(int)); //已经形成的最小树到其他各个节点的最短距离
  56.     bool* visited=(bool*)calloc(N,sizeof(bool)); //记录各个节点是否已经被采纳了
  57.     
  58.     int initpos=0; //设定初始节点
  59.     for(int j=0;j<N;j++)
  60.     {
  61.         dis[j]=map[initpos][j];
  62.     }
  63.     visited[initpos]=true;
  64.     
  65.     for(int i=0;i<N-1;i++) //每一次循环找到一条边,一共进行N-1次
  66.     {
  67.         int min_distan=100000; //初始化最小边的权重

  68.         MinStreeEdge tempEdge;
  69.         tempEdge._pos1=initpos;

  70.         //下面for循环,计算出此时最小边和节点
  71.         for(int j=1;j<N;j++)
  72.         {
  73.             if(!visited[j]&&(min_distan>dis[j])&&(dis[j]!=-1))
  74.             {
  75.                 min_distan=dis[j];
  76.                 initpos=j; //更新节点
  77.             }
  78.         }

  79.         //更新相应参数
  80.         tempEdge._pos2=initpos;
  81.         tempEdge._value=min_distan;
  82.         m_treeEdges.push_back(tempEdge); //加载到容器

  83.         visited[initpos]=true;
  84.         for(j=0;j<N;j++)
  85.         {
  86.             if(!visited[j]&&((map[initpos][j]<dis[j])||(dis[j]==-1))&&(map[initpos][j]!=-1))
  87.                 dis[j]=map[initpos][j];
  88.         }
  89.     }
  90.     free(dis);
  91.     free(visited);
  92. }
此实现借助了最小堆,来实现每次选取权值最小的边。

最小堆的代码实现:

点击(此处)折叠或打开

  1. //基于堆的最小队列
  2. //@anthor hustfxj
  3. //data 2013/11/6

  4. #ifndef CLASS_CMINHEAP
  5. #define CLASS_CMINHEAP

  6. //#include"stdaxf.h"
  7. template <class T>
  8. class CMinHeap
  9. {
  10. public:
  11.     explicit CMinHeap(int n);
  12.     ~CMinHeap();
  13.     
  14.     bool insert(const T& Addedata);
  15.     T ExtractMin();
  16. private:
  17.     int parentIndex(int child) const;
  18.     int getlchild(int parent) const;
  19.     int getrchild(int parent) const;
  20.     void swap(int k1,int k2);
  21.     
  22. private:
  23.     T* m_HeapData;
  24.     int memoriedSize;
  25.     int size;
  26. };
  27. #endif


  28. template <class T>
  29. CMinHeap<T>::CMinHeap(int n)
  30. {
  31.     m_HeapData=new T[n];
  32.     memoriedSize=n;
  33.     size=0;
  34. }
  35. template <class T>
  36. CMinHeap<T>::~CMinHeap()
  37. {
  38.     delete [] m_HeapData;
  39. }

  40. template <class T>
  41. bool CMinHeap<T>::insert(const T& Addedata)
  42. {
  43.     if(size>=memoriedSize)
  44.         return false;
  45.     int child=size,p;
  46.     m_HeapData[size]=Addedata;
  47.     size++;

  48.     p=parentIndex(child);
  49.     while(m_HeapData[child]<m_HeapData[p]&&p>=0)
  50.     {
  51.         swap(p,child);
  52.      child=p;
  53.         p=parentIndex(child);
  54.     }    
  55.     return true;
  56. }
  57. template <class T>
  58. T CMinHeap<T>::ExtractMin()
  59. {
  60.     if(size==0)
  61.         exit(1); //队列中以及没有元素了
  62.     T val=m_HeapData[0];
  63.     m_HeapData[0]=m_HeapData[size-1];
  64.     size--;
  65.     int begin=0;

  66.     while(begin<size)
  67.     {
  68.         int lchild=getlchild(begin);
  69.         int rchild=getrchild(begin);
  70.         int pos=begin;
  71.         if(lchild<size&&m_HeapData[lchild]<m_HeapData[pos])
  72.             pos=lchild;
  73.         if(rchild<size&&m_HeapData[rchild]<m_HeapData[pos])
  74.             pos=rchild;
  75.         if(pos==begin)
  76.             break;
  77.         swap(pos,begin);
  78.         begin=pos;
  79.     }
  80.     return val;
  81. }
  82. template <class T>
  83. void CMinHeap<T>::swap(int k1,int k2)
  84. {
  85.     if(k1==k2)
  86.         return;
  87.     T temp=m_HeapData[k1];
  88.     m_HeapData[k1]=m_HeapData[k2];
  89.     m_HeapData[k2]=temp;
  90. }
  91. template <class T>
  92. int CMinHeap<T>::parentIndex(int child) const
  93. {
  94.     return child%2==0?child/2-1:child/2;
  95. }
  96. template <class T>
  97. int CMinHeap<T>::getlchild(int parent) const
  98. {
  99.     return (parent+1)*2-1;
  100. }
  101. template <class T>
  102. int CMinHeap<T>::getrchild(int parent) const
  103. {
  104.    return (parent+1)*2;
  105. }




阅读(1714) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~