Алгоритм Фарбала

Дерево, Алгоритм, Tree

Алгоритм Краскала - це алгоритм мінімального кістякового дерева, що приймає граф як вхідні дані і знаходить підмножину ребер цього графа, який формує дерево, що включає кожну вершину, а також має мінімальну суму ваг серед усіх дерев, які можуть бути сформовані із графа.

Як працює алгоритм Краскала

Він підпадає під клас алгоритмів, які називаються «жадібними» алгоритмами, які знаходять локальний оптимум, сподіваючись знайти глобальний оптимум.

Ми починаємо з ребер з найменшою вагою і продовжуємо додавати ребра, доки не досягнемо нашої мети.

Кроки для реалізації алгоритму Фарба наступні:

1. Сортувати усі ребра від малої ваги до високої.
2. Візьміть ребро з найменшою вагою і додайте його до кістяного дерева. Якщо додавання ребра створило цикл, відхиліть це ребро.
3. Продовжуйте додавати ребра, доки не досягнете всіх вершин.

Приклад алгоритму Фарбала

Алгоритм Фарбала. Псевдокод.

Будь-який мінімальний алгоритм остовного дерева обертається навколо перевірки, чи створює ребро цикл чи ні.

Найпоширеніший спосіб з'ясувати це - алгоритм Union FInd. Алгоритм Union-Find розділяє вершини на кластери і дозволяє нам перевірити, чи належать дві вершини одному кластеру чи ні, і, отже, вирішити, чи створює додавання ребра цикл.

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
    MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
    if FIND-SET(u) ≠ FIND-SET(v):       
    A = A ∪ {(u, v)}
    UNION(u, v)
return A

Реалізація алгоритму Фарба в C ++

Нижче наведено код для реалізації C++. Ми використовуємо стандартні бібліотеки шаблонів, щоб зробити нашу роботу простіше та чистіше.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define edge pair<int,int>

class Graph {
private:
    vector<pair<int, edge>> G; // graph
    vector<pair<int, edge>> T; // mst
    int *parent;
    int V; // number of vertices/nodes in graph
public:
    Graph(int V);
    void AddWeightedEdge(int u, int v, int w);
    int find_set(int i);
    void union_set(int u, int v);
    void kruskal();
    void print();
};
Graph::Graph(int V) {
    parent = new int[V];

    //i 0 1 2 3 4 5
    //parent[i] 0 1 2 3 4 5
    for (int i = 0; i < V; i++)
        parent[i] = i;

    G.clear();
    T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
    G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
    // If i is the parent of itself
    if (i == parent[i])
        return i;
    else
        // Else if i is not the parent of itself
        // Then i is not the representative of his set,
        // so we recursively call Find on its parent
        return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
    parent[u] = parent[v];
}
void Graph::kruskal() {
    int i, uRep, vRep;
    sort(G.begin(), G.end()); // increasing weight
    for (i = 0; i < G.size(); i++) {
        uRep = find_set(G[i].second.first);
        vRep = find_set(G[i].second.second);
        if (uRep != vRep) {
            T.push_back(G[i]); // add to tree
            union_set(uRep, vRep);
        }
    }
}
void Graph::print() {
    cout << "Edge :" << " Weight" << endl;
    for (int i = 0; i < T.size(); i++) {
        cout << T[i].second.first << " - " << T[i].second.second << " : "
                << T[i].first;
        cout << endl;
    }
}
int main() {
    Graph g(6);
    g.AddWeightedEdge(0, 1, 4);
    g.AddWeightedEdge(0, 2, 4);
    g.AddWeightedEdge(1, 2, 2);
    g.AddWeightedEdge(1, 0, 4);
    g.AddWeightedEdge(2, 0, 4);
    g.AddWeightedEdge(2, 1, 2);
    g.AddWeightedEdge(2, 3, 3);
    g.AddWeightedEdge(2, 5, 2);
    g.AddWeightedEdge(2, 4, 4);
    g.AddWeightedEdge(3, 2, 3);
    g.AddWeightedEdge(3, 4, 3);
    g.AddWeightedEdge(4, 2, 4);
    g.AddWeightedEdge(4, 3, 3);
    g.AddWeightedEdge(5, 2, 2);
    g.AddWeightedEdge(5, 4, 3);
    g.kruskal();
    g.print();
    return 0;
}

Коли ми запускаємо програму, ми отримуємо висновок як:

Edge : Weight
1 - 2 : 2
2 - 5 : 2
2 - 3 : 3
3 - 4 : 3
0 - 1 : 4

Алгоритм Фарбала vs Пріма

Алгоритм Пріма є ще одним популярним алгоритмом мінімального кістякового дерева, який використовує іншу логіку для знаходження MST графа. Замість того, щоб починати з ребра, алгоритм Прима починається з вершини і продовжує додавати ребра з найменшою вагою, яких немає в дереві, доки всі вершини не будуть покриті.