Blog·Tanky WooABOUTRSS

《算法导论》学习总结 — XX.第23章 最小生成树

07 Jan 2012
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言:http://www.wutianqi.com/?p=2298

以前写过一篇最小生成树的文章,见:http://www.wutianqi.com/?p=1284

最小生成树(Minimum Spanning Tree),全称“最小权值生成树”

有两种具体的实现算法

1.Kruskal算法

2.Prim算法

两者都用到了贪心算法。

最小生成树的形成:

23.1节,此节是两种算法的基础,伪代码:

GENERIC_MST(G, w)
    A <- 空集
    while A does not form a spanning tree
        do find an edge(u, v) that is safe for A
            A <- A  {(u, v)}
    return A

重点是每次选择出一条安全边。

要了解的概念:安全边,割,轻边

23.1定理,这里Mark一笔,定理各种纠结,看了半天还是不明白。

Kruskal算法:

思想:该算法每次从所有未使用边中,找出权值最小的边,加入到生成树中,直到加入V-1条边(V是顶点数),构成一颗MST。

看图23-4,Kruskal的构造过程

具体实现(C/C++):

/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Kruskal
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.7
 */

#include 
#include 
using namespace std;

const int maxint = 999999;

typedef struct Road{
    int c1, c2;   // a到b
    int value;  // 权值
}Road;

int no;
int line;
Road road[100];
int node[101];

bool myCmp(const Road &a;, const Road &b;)
{
    if(a.value < b.value)
        return 1;
    return 0;
}

int Find_Set(int n)
{
    if(node[n] == -1)
        return n;
    return node[n] = Find_Set(node[n]);
}

bool Merge(int s1, int s2)
{
    int r1 = Find_Set(s1);
    int r2 = Find_Set(s2);
    if(r1 == r2)
        return 0;
    if(r1 < r2)
        node[r2] = r1;
    else
        node[r1] = r2;
    return 1;
}

int main()
{
    freopen("input.txt", "r", stdin);

    memset(node, -1, sizeof(node));
    cout << "Input the number of the node:";
    cin >> no;
    cout << "Input the number of the line:";
    cin >> line;
    cout << "Input the edge:";
    for(int i=0; i> road[i].c1 >> road[i].c2 >> road[i].value;
    }
    sort(road, road+line, myCmp);
    int sum = 0, count = 0;  // sum是MST的值,count是记录已使用的点数
    for(int i=0; iPrim算法:


思想:可以通过Dijkstra算法来理解,因为两者的思想非常类似,假设顶点集S,其中集合A是已经加入到生成树中的点,集合B是剩余的点,每次从连接A,B的边中找出权值最小的边,作为生成树的边。

(Dijkstra的讲解见:[http://www.wutianqi.com/?p=1890](http://www.wutianqi.com/?p=1890))

看图23-5Prim的构造过程

具体实现(C/C++):


```cpp

/*
 * Introduction to Algorithms
 * Chapter 23 --- MST.Prim
 * Tanky Woo @ www.WuTianQi.com
 * 2012.1.7
 */


#include 
using namespace std;
const int INF=1001;

int no, line;
int arcs[101][101];
int dis[101], vis[101];
int _min;

int main()
{
    freopen("input.txt", "r", stdin);


    cout << "Input the number of the node:";
    cin >> no;
    cout << "Input the number of the line:";
    cin >> line;

    for(int i=0; i> p >> q >> len;
        if(len < arcs[p-1][q-1])       // 有重边
        {
            arcs[p-1][q-1] = len;      // p指向q
            arcs[q-1][p-1] = len;      // q指向p,这样表示无向图
        }
    }

    memset(vis, 0, sizeof(vis));
    for(int i=1; i小结:


Kruskal算法和Prim算法的最大区别就是在找安全边时,对于安全边的选择不一样,不过同样都是基于贪心算法的。

Kruskal适合一维数组来管理数据,而Prim则适合用一个二维矩阵来管理边之间的关系,具体选择可以看实际数据的量。



DATE: 2012.1.7 @ Home By Tanky Woo