Алгоритм Краскала (Реализация на C++)

C++   12 Декабрь 2012  Автор статьи:  

Алгоритм Краскала находит минимальное остовное дерево. На вход алгоритм Краскала принимает неориентированный граф, который задается с помощью структуры edge: x — из какой вершины, y — в какую, w — вес ребра. После того, как считали граф, мы должны отсортировать все ребра по возрастанию. Дальше нужно рассматривать ребра по — порядку, решая брать или не брать ребро. Мы должны взять ребро, если оно соединяет вершины, которые расположены в разных подмножествах, и не брать если в одном, для того, чтобы узнать в каком множестве находится вершина используется функция getLeader. Для того, чтобы ответить на вопрос объединять ли две вершины используется функция unite. Таким образом, пробежавшись по всем ребрам и взяв только те, которые подходят мы построим минимальное остовное дерево. Пример алгоритма Краскала:

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
86
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct edge
{
    int x, y, w;
    edge(){}
    edge(int x, int y, int w): x(x), y(y), w(w) {}
};

bool cmp(const edge& a, const edge& b)
{
    return a.w < b.w;
}

vector <int> leader;

int getLeader(int x)
{
    if (x == leader[x])
        return x;

    return leader[x] = getLeader(leader[x]);   
}

bool unite(int x, int y)
{
    x = getLeader(x);
    y = getLeader(y);

    if (x == y)
        return false;

    if (rand() % 2 == 0)
        swap(x, y);

    leader[x] = y;
    return true;
}

int main()
{
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);

    int n, m;
    scanf("%d%d", &n, &m);

    vector <edge> e(m);

    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);

        e[i].x--;
        e[i].y--;
    }

    sort(e.begin(), e.end(), cmp);

    leader.resize(n);
    for (int i = 0; i < n; i++)
        leader[i] = i;

    vector <edge> ans;

    for (int i = 0; i < m; i++)
    {
        int x = e[i].x, y = e[i].y;

        if (unite(x, y))
            ans.push_back(e[i]);
    }
    int sum = 0;
    for (int i = 0; i < ans.size(); i++)
        sum+=ans[i].w;
    printf("%d\n", sum);
    for (int i = 0; i < ans.size(); i++)
        printf("%d %d\n", ans[i].x + 1, ans[i].y + 1);
   
    return 0;
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++