Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1059275
  • 博文数量: 77
  • 博客积分: 821
  • 博客等级: 军士长
  • 技术积分: 1905
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-23 16:17
个人简介

学校:上海交通大学软件工程 学历:硕士 行业:从事流媒体移动开发 QQ: 412595942 邮箱:yiikai1987910@gmail.com

文章分类

全部博文(77)

文章存档

2016年(4)

2015年(15)

2014年(16)

2013年(12)

2012年(21)

2011年(9)

分类: C/C++

2015-02-25 16:28:17

    在之前,我曾经写过一边关于最小生出树的算法--prime,今天是另一个算法kruskal,这两个算法的复杂度是一样的。主要和prime在代码实现上的区别在于,kruskal算法是把焦点集中在了边上, 而prime算法是在节点上,一个是对优先队列中的点进行操作,一个是对于优先队列中的边进行操作。详细的算法细节大家可以google。
   在kruskal算法中应用到了一个很重要也很有用的数据结构 --并查集
   并查集对于连通图的连同性的判断很有用,kruskal就是利用它来判断所使用的边是否会使MST产生环
   直接上伪代码:
   initGraph();
   union_find m;  //定义并查集结构
   put edge to priority_queue;
   while(queue is not empty)
          m = queue.pop();
          queue.pop();
          if connected(m.src,m.end)  //如果边的两个node是在一个集合里
              continue;
          else
             //就算是MST里的一条边

   思路还是很清楚的,直接上代码了:
   

点击(此处)折叠或打开

  1. #include <queue>
  2. #include <vector>

  3. #define MAXN 4
  4. int ID[MAXN] = { 0 };
  5. int rank[MAXN];
  6. class union_find
  7. {
  8. public:
  9.     union_find();
  10.     int find_root(int x);
  11.     void connect(int x, int y);
  12.     bool isConnected(int x, int y);
  13. };

  14. bool union_find::isConnected(int x, int y)
  15. {
  16.     int xRoot = find_root(x);
  17.     int yRoot = find_root(y);
  18.     if (xRoot == yRoot)
  19.     {
  20.         printf("Has Connected\n");
  21.         return true;
  22.     }
  23.     else
  24.         return false;
  25. }


  26. union_find::union_find()
  27. {
  28.     for (int i = 0; i < MAXN; i++)
  29.     {
  30.         ID[i] = i;
  31.         rank[i] = 1;
  32.     }
  33. }

  34. int union_find::find_root(int x)
  35. {
  36.     if (ID[x] == x)
  37.         return x;
  38.     return find_root(ID[x]);
  39. }

  40. void union_find::connect(int x, int y)
  41. {
  42.     int xRoot = find_root(x);
  43.     int yRoot = find_root(y);
  44.     if (xRoot == yRoot)
  45.     {
  46.         printf("Has Connected\n");
  47.         return;
  48.     }
  49.     if (rank[xRoot] >= rank[yRoot])
  50.     {
  51.         rank[xRoot] += 1;
  52.         ID[yRoot] = ID[xRoot];
  53.     }
  54.     else
  55.     {
  56.         rank[yRoot] += 1;
  57.         ID[xRoot] = ID[yRoot];
  58.     }
  59. }


  60. #define MAXNODE 4
  61. int edge[4][4];
  62. struct doubleEdge
  63. {
  64.     int src;
  65.     int end;
  66.     int cost;
  67. };

  68. void initGraph()
  69. {
  70.     for (int i = 0; i < MAXNODE; i++)
  71.         for (int j = 0; j < MAXNODE; j++)
  72.             edge[i][j] = -1;
  73.     

  74. }

  75. struct cmp2
  76. {
  77.     bool operator()(doubleEdge x, doubleEdge y)
  78.     {
  79.         return x.cost > y.cost;
  80.     }
  81. };

  82. int _tmain(int argc, _TCHAR* argv[])
  83. {
  84.     initGraph();
  85.     union_find m;
  86.     doubleEdge edge1 = { 0, 3, 1 };
  87.     doubleEdge edge2 = { 0, 2, 7 };
  88.     doubleEdge edge3 = { 0, 1, 3 };
  89.     doubleEdge edge4 = { 2, 3, 2 };
  90.     doubleEdge edge5 = { 2, 1, 4 };
  91.     std::priority_queue<doubleEdge, std::vector<doubleEdge>, cmp2> que;
  92.     que.push(edge1);
  93.     que.push(edge2);
  94.     que.push(edge3);
  95.     que.push(edge4);
  96.     que.push(edge5);

  97.     while (!que.empty())
  98.     {
  99.         doubleEdge tmp = que.top();
  100.         que.pop();
  101.         if (m.isConnected(tmp.src, tmp.end))
  102.         {
  103.             //printf("This edge is in MST");
  104.             continue;
  105.         }
  106.         else
  107.         {
  108.             m.connect(tmp.src, tmp.end);
  109.             printf("%d,%d\n", tmp.src, tmp.end);
  110.         }
  111.     }


  112.     return 0;
  113. }

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