首页 > 图论 > 最小生成树 > 贪心算法(4)-最小生成树Prim算法
2014
05-15

贪心算法(4)-最小生成树Prim算法

一个连通图的生成树是一个极小的连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1条边。所谓的最小成本,就是n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小。综合以上两个概念,我们可以得出:构造连通网的最小代价生成树,即最小生成树(Minimum Cost Spanning Tree)。找连通图的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法,这里介绍普里姆算法。在前面一讲Kruskal最小生成树 中已经介绍了最小生成树的算法。和Kruskal算法类似,Prim算法也是利用贪心算法来解决最小生成树。

最小生成树MST性质:假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值(代价)的边,

其中u∈U,v∈V-U,则必存在一颗包含边(u,v)的最小生成树。

prim算法过程为:

假设N=(V,{E})是连通图,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始,

重复执行下述操作:

在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0 并入U,直至U=V为止。

此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。

具体描述如下:

1) 创建一个集合mstSet记录已经包含在MST中的顶点
2)对图中的所有顶点设置一个key值,代表代价,并初始化无穷大。第一个点设置为0,以便总是能第一个取到第一个点
3) While( mstSet没有包含所有的顶点 )
     a) 从mstSet集合中剩下的顶点中,选取一个最小key的顶点u
     b) 把u加入到mstSet
     c) 更新所有的和u相连的那些顶点的key值。

如果大家熟悉迪杰斯特拉算法,会发现他们是很相似的。

我以图为例,看看算法过程。

初始的mstSet为空,keys(各个点击的代价)为{0, INF, INF, INF, INF, INF, INF, INF}

找到其中最小的,并加入mstSet,mstSet变为: {0}. 然后更新和0相邻的那些顶点的key值。相邻的顶点为1和7. 更新后为 {0, 4, INF, INF, INF, INF, INF, 8}

下图中绿色表示 mstSet.

重复上面的过程

       

……….  最终为  

C++实现如下:

#include <stdio.h>
#include <limits.h>

//图中顶点个数
#define V 5

//未在mstSet中的点的集合中,找出最小key的点
int minKey(int key[], bool mstSet[])
{
   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)
     if (mstSet[v] == false && key[v] < min)
         min = key[v], min_index = v;

   return min_index;
}

// 打印MST
int printMST(int parent[], int n, int graph[V][V])
{
   printf("Edge   Weight\n");
   for (int i = 1; i < V; i++)
      printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}

// Prim算法
void primMST(int graph[V][V])
{
     int parent[V]; // 保持MST信息
     int key[V];   // 所有顶点的代价值
     bool mstSet[V];  //当前包含在MST中点的集合

     // 初始为无穷大
     for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;

     key[0] = 0;     //
     parent[0] = -1; // 第一个作为树的根。

     //  MST 有V的顶点
     for (int count = 0; count < V-1; count++)
     {
        int u = minKey(key, mstSet);
        // 添加u到 MST Set
        mstSet[u] = true;
        //更新和u相连的顶点的代价
        for (int v = 0; v < V; v++)
          if (graph[u][v] && mstSet[v] == false && graph[u][v] <  key[v])
             parent[v]  = u, key[v] = graph[u][v];
     }

     // 打印生成的MST
     printMST(parent, V, graph);
}

int main()
{
   /* 创建以下的图
          2    3
      (0)--(1)--(2)
       |   / \   |
      6| 8/   \5 |7
       | /     \ |
      (3)-------(4)
            9          */
   int graph[V][V] = {{0, 2, 0, 6, 0},
                      {2, 0, 3, 8, 5},
                      {0, 3, 0, 0, 7},
                      {6, 8, 0, 0, 9},
                      {0, 5, 7, 9, 0},
                     };

    // Print the solution
    primMST(graph);

    return 0;
}

输出:

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

时间复杂度:O(V^2).  如果使用 链接表存储的方式并使用堆,复杂度可以为 O(E log V) ,后面会讨论这个算法。

参考:http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

http://www.cnblogs.com/jsgnadsj/p/3421288.html


  1. 特别喜欢季淳卿,他倾国倾城,他武功高强,他冷若冰霜,他风度翩翩…… 但在苏家袄面前,他温柔贤惠,他弱不禁风,他柔情似水,他美丽优雅……他为了小时候的一个婚约,赌上了自己的终身,可谁知他竟爱上了她

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。