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

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

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

#include
#include
#include
#include

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 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 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 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++