a naive implementation for boruvka algorithm

| 分类 algorithm  | 标签 algorithm 

http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm

wiki上面讲的还是很详细的。

过程就是:

寻找连通分量之间的最短边;
连接;
#include <iostream>
#include <vector>
#include <algorithm>
#include <istream>
#include <cmath>

using namespace std;

#define VERTEX_NUMBER 12

struct edge_t {
    int a, b;
    int weight;

    edge_t() {}
    edge_t(int _a, int _b, int _w):a(_a), b(_b), weight(_w) {}
};

istream& operator>>(istream& in, edge_t& elem)
{
    char ch1, ch2;
    int weight;

    in >> ch1 >> ch2 >> elem.weight;
    elem.a = ch1 - 'a';
    elem.b = ch2 - 'a';

    return in;
}

ostream& operator<<(ostream& out, edge_t& elem)
{
    char ch1 = elem.a + 'a', ch2 = elem.b + 'a';
    out << ch1 << "-->" << ch2 << ' ' << elem.weight << endl;
    return out;
}

int f[VERTEX_NUMBER];

void init()
{
    for (int i = 0; i < VERTEX_NUMBER; ++i)
        f[i] = i;
}

int find(int x)
{
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}

vector<edge_t> boruvka(const vector<edge_t>& GE)
{
    int N, i;
    edge_t closest[VERTEX_NUMBER];
    vector<edge_t> ret;
    vector<edge_t> E(GE);

    const edge_t inf(-1, -1, INFINITY);
    init();

    // find all possible edges
    for (int e = E.size(); e > 0; e = N) {
        for (int j = 0; j < VERTEX_NUMBER; ++j)
            closest[j] = inf;

        // select the active edges between 2 components
        for (i = N = 0; i < e; ++i) {
            int a = find(E[i].a), b = find(E[i].b);

            // if they are in the same forest
            if (a == b)
                continue;

            if (closest[a].weight > E[i].weight)
                closest[a] = E[i];
            if (closest[b].weight > E[i].weight)
                closest[b] = E[i];
            E[N++] = E[i];
        }

        // for every component
        for (int j = 0; j < VERTEX_NUMBER; ++j) {
            if (closest[j].weight == INFINITY || find(closest[j].a) == find(closest[j].b))
                continue;
            int a = find(closest[j].a), b = find(closest[j].b);
            f[a] = b;
            ret.push_back(closest[j]);
        }
    }
    return ret;
}

int main()
{
    edge_t e;
    vector<edge_t> E;
    vector<edge_t> mst;

    while (cin >> e)
        E.push_back(e);

    mst = boruvka(E);
    for (int i = 0; i < mst.size(); ++i)
        cout << mst[i];

    return 0;
}

针对上面的程序,附一测试数据(其实就是wiki上的那幅图):

a b 13

a c 6

b c 7

b d 1

c d 14

c e 8

c h 20

d 3 9

d f 3

e f 2

e j 18

g h 15

g i 5

g j 19

g k 10

h j 17

i k 11

j k 16

j l 4

k l 12


上一篇     下一篇