Kruskal

kruskal与prim不同，是基于边去构造最小生成树，所以适用于边比较少的稀疏图。
kruskal需要边的集合，我们称其为边集数组。边集数组按从小到大的顺序排序，方便构造最小生成树。

边集数组

结构体

1
2
3
4
5
struct edge {
    int begin, end, weight;
    bool operator<(edge const& rhs)
    {return this->weight < rhs.weight;}
}edges[maxsize * (maxsize - 1)];

边集数组构造函数
1
2
3
4
5
6
7
8
9
10
11
12
void get_edges_set()
{
    int a = 0;
    for (int i = 0; i < nume; i++)
    {
        cin >> u >> v >> w;
        edges[a].begin = u - 'A';
        edges[a].end = v - 'A';
        edges[a++].weight = w;
    }
    sort(edges, edges + a);
}

构造最小生成树

边集数组构造好，vector中根据权值从小到大排序。我们沿着下标选择begin和end连线来构造最小生成树，但是，在连接过程中可能出现成环的现象，这是由于父节点重复了，孩子想与父节点连在一起或是孩子想连在一起而造成的一种严重错误。
我们可以通过并查集来避开成环情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findset(int x)
{
    return (fa[x] == x) ? x : findset(fa[x]);
}

void Union(int b, int e)
{
    int bb = findset(b);
    int ee = findset(e);
    if (bb != ee)
        fa[bb] = ee;
}

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

Kruskal
1
2
3
4
5
6
7
8
9
10
11
12
13
void kruskal(vector<pair<int, int>>& ET)
{
    for (int i = 0; i < nume; i++)
    {
        int uu = findset(edges[i].begin);
        int vv = findset(edges[i].end);
        if (uu != vv)
        {
            Union(edges[i].begin, edges[i].end);
            ET.push_back(make_pair(edges[i].begin, edges[i].end));
        }
    }
}

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
string const alphabet("ABCDEFGHIJkLMNOPQRSTUVWXYZ");
int const maxsize = 26;
int fa[maxsize];
int nume, w;
char u, v;
struct edge {
    int begin, end, weight;
    bool operator<(edge const& rhs)
    {
        return this->weight < rhs.weight;
    }
}edges[maxsize * (maxsize - 1)];

void get_edges_set()
{
    int a = 0;
    for (int i = 0; i < nume; i++)
    {
        cin >> u >> v >> w;
        edges[a].begin = u - 'A';
        edges[a].end = v - 'A';
        edges[a++].weight = w;
    }
    sort(edges, edges + a);
}

int findset(int x)
{
    return (fa[x] == x) ? x : findset(fa[x]);
}

void Union(int b, int e)
{
    int bb = findset(b);
    int ee = findset(e);
    if (bb != ee)
        fa[bb] = ee;
}

void init()
{
    for(int i = 0; i < maxsize; i++)
        fa[i] = i;
}
void kruskal(vector<pair<int, int>>& ET)
{
    for (int i = 0; i < nume; i++)
    {
        int uu = findset(edges[i].begin);
        int vv = findset(edges[i].end);
        if (uu != vv)
        {
            Union(edges[i].begin, edges[i].end);
            ET.push_back(make_pair(edges[i].begin, edges[i].end));
        }
    }
}

int main()
{
    while (cin >> nume && nume > 0)
    {
        init();
        vector<pair<int, int>> ET;
        get_edges_set();
        kruskal(ET);

        cout << "{";
        for (auto i=ET.begin();i!=ET.end();i++)
        {
            if(i!=prev(ET.end()))
            cout << alphabet[(*i).first] << alphabet[(*i).second] << ",";
            else
            cout << alphabet[(*i).first] << alphabet[(*i).second] ;
        }
        cout << "}";
    }
}

时间复杂度

Tn=O(e)·O(sort)+O(e)·α(v)
α是阿克曼的反函数，近乎常数（不超过5）
因此Tn=O(eloge);