Крускаль алгоритмі

Дерево, Алгоритм, 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++ тілінде енгізуге арналған код берілген. Жұмысымызды жеңілдету және таза ету үшін біз стандартты үлгі кітапханаларын пайдаланамыз.

#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

Крускал алгоритмі Примаға қарсы

Прим алгоритмі - MST графигін табу үшін басқа логиканы пайдаланатын тағы бір танымал минималды аумақтық ағаш алгоритмі. Прим алгоритмі жиектен бастаудың орнына шыңнан басталады және барлық шыңдар жабылмайынша, ағашта жоқ ең аз салмақты жиектерді қосуды жалғастырады.