Kruskal -algoritmen

Minimum spanning tre

En graf som ikke har veibeskrivelse, kalles en rettet graf. Hver graf må ha en sti fra en node til en annen node. Et spanningstre er også en rettet tilkoblet graf der alle nodene på grafen er til stede med minimumskanter. Hvis et spanningstre ikke har alle nodene på grafen, kan vi ikke si at det er et spanningstre. Totalvektene for spanning-tre vil være mindre enn den opprinnelige vekten på grafen når vi koblet den gjennom minimumsvektkantene. Det spanningstreet har heller ikke en syklus. Enhver graf har mer enn ett spanningstre, men bare en av disse vil være unike. Vi kaller det et minimalt spanningstre siden vi prøver å lage en full graf med alle noder mens vi holder vekten lav.

La oss forstå det minimale spanningstreet med et eksempel. Så som vi vet, er det minimale spanningstreet en del av grafen, men med mindre kostnader. Så dette scenariet kan illustreres med et eksempel. La oss anta at vi har en graf som denne.

Grafen ovenfor kan ordnes på forskjellige måter slik at grafsyklusen blir fjernet, ellers vil det ikke være en MST (minimum spanningstre). Så vi vil fjerne syklusen fra grafen og telle den totale kostnaden for grafen. Vi har fire noder, eller hjørner (a, b, c og d).

Sak - 1:

Etter å ha fjernet syklusen fra grafen, er grafskostnadene ovenfor (minimum spanningstre) 56.

Sak -2:

Etter å ha fjernet syklusen fra grafen, er grafkostnaden ovenfor (minimum spanningstre) 53.

Sak - 3:

Etter å ha fjernet syklusen fra grafen, er grafskostnadene ovenfor (minimum spanningstre) 41.

Vi kan se at den siste grafen over case-3s totale kostnad er mye lavere sammenlignet med de to andre grafene. Så denne grafen er vår siste MST (minimum spanningstre) for den originale grafen. Prims eller Kruskals algoritmers motiv er å finne grafkostnaden så lave som mulig. Så det er vårt motiv i denne artikkelen for å forklare denne MST.

Vi kan tegne et spanningstre ved hjelp av følgende to metoder:

1. Kruskals algoritme
2. Prims algoritme

I denne artikkelen skal vi diskutere Kruskals algoritme. Prims algoritme vil bli diskutert i neste artikkel.

Kruskals algoritme

Kruskals algoritme er veldig enkel å implementere sammenlignet med Prims algoritme fordi vi ikke trenger å bry oss om adjacency -hjørnene i denne algoritmen. I denne algoritmen starter Kruskals algoritme fra alle hjørnene på grafen. Vi velger minimum Vektkanthvertus og begynner å lage minimumsspanningstreet. Vi velger en annen kant med minimumsvekten og legger den til minimumsspanningstreet. Denne prosessen fortsetter til vi ikke legger til alle de originale grafnodene. Når alle nodene i grafen er lagt til det minimale spanningstreet, vil algoritmen stoppe. Under å lage et minimumsspannings tre på en graf, må vi også ta vare på den grafen, og ikke lage noen sykluser fordi sykluser ikke skal være i minimumsspanningstreet.

Så hvis noen node oppretter syklusen i minimumsspanningstreet, velger vi den andre noden, selv om denne nodens vekt er større enn den forrige noden som oppretter syklusen.

Kruskals algoritme er forskjellig fra Prims algoritme. Prims algoritme, mens du lager et minimum spanningstre, starter fra hvilken som helst node eller vertice og legger deretter til en annen node eller vertice bare fra adjacency -nodene. Men Kruskals algoritme bryr seg ikke om adjacency -noden og velger alltid den noden som har mindre vekt, men den noden skal ikke skape en syklus i det minste spennende treet.

Kruskals algoritme trinn:

Følgende trinn blir tatt mens du skriver C ++ -koden for Kruskals algoritme.

1. Vi lager en rekke for å lagre grupper av nodene eller hjørnene på grafen.
2. Vi oppretter en annen matrise for å lagre grafkantvekter.
3. For det spanningstreet lager vi en ny matrise.
4. Vi arrangerer kantene matriser i stigende rekkefølge.
5. Vi gjentar trinn 6 til en rekke sorterte kantvekter ikke er tomt.
6. Vi sammenligner de to gruppene side om side. I dette tilfellet, hvis den ene noden til en gruppe ikke samsvarer med den andre noden, legger vi den kanten til det spennende treet og legger den inn i samme gruppe.
7. Itererer gjennom alle spannings -tretre for å bestemme totalvekten.

Nå vil vi implementere algoritmetrinnene ovenfor ved hjelp av et eksempel. Vi har grafen nedenfor, og vi finner ut det minimale spanningstreet for denne grafen.

Så ifølge algoritmen velger vi først den minste vektkanten, som er AB. Så vi valgte den kanten og holdt den i det spanne tre -arrayet. Vekten på abten er 9.

Nå velger vi den neste minste vektkanten, CD, og ​​holder den kanten i minimumsspannings -tre -array. CD -kantvekten er 12.

Den neste minste kanten vi fikk var BC, som vi holdt i matrisen. Den vektede BC -kanten er 17.

Algoritmen vår vil stoppe her fordi vi har alle toppunktene til en graf, og vi har et minimums spanningstre. Den totale vekten av denne MST er 9 + 12 + 17 = 38.

Program: Nedenfor er en C ++ -kode for Kruskals algoritme.

#inkludere
#inkludere
#inkludere
Class EdgeGraph
offentlig:
int nodestart;
int nodeend;
int wght;
EdgeGraph ()
EdgeGraph (int node_1, int node_2, int vekt): nodestart (node_1),
Nodeend (Node_2), WGHT (vekt)
;
bool sammenligne Gevekt (const edgeraph a, const edge graph b)
returner a.wght < b.wght;

klasse G
privat:
int num_of_nodes;
std :: vektor EdgeGraphList;
std :: vektor parentnode;
std :: vektor RankNode;
offentlig:
G ()
G (int num_of_nodes)

dette-> num_of_nodes = num_of_nodes;
Parentnode.Endre størrelse (num_of_nodes);
Ranknode.Endre størrelse (num_of_nodes);

void AddEdgeGraph (EdgeGraph E);
int findParentNode (int node);
void Kruskalmst_algo (std :: vektor&);
void displayEdraphs (std :: vektor&);
;
void g :: addEdgeGraph (EdgeGraph E)
EdgeGraphlist.push_back (e);

int g :: findParentNode (int node)
if (node != parentnode [node])
parentnode [node] = findParentNode (parentnode [node]);
return parentnode [node];

void G :: DisplayEdgeGraphs (STD :: Vector& mst)
int -kostnad = 0;
std :: cout << "EdgeGraphs of MST : ";
for (auto & e: mst)
std :: cout << "[" << e.nodeSTART << "-" << e.nodeEND
<< "](" << e.wght << ") ";
kostnad += e.wght;

std :: cout << "\n Kruskal MST Cost : " << cost << std :: endl;

// dette er hovedkruskals algoritmefunksjon som søk
// det minimale spanningstreet.
void g :: Kruskalmst_algo (std :: vektor& resultat)
for (int i = 0; iparentnode [i] = i;
RankNode [i] = 0;

Sorter (EdgeGraphList.Begynn (), EdgeGraphlist.slutt(),
Sammenligne Gevekt);
for (auto & e: edgegraphlist)
int root_1 = findParentNode (e.nodestart);
int root_2 = findParentNode (e.nodeend);
if (root_1 != root_2)
resultat.push_back (e);
if (ranknode [root_1] < rankNode[root_2])
parentnode [root_1] = root_2;
RankNode [root_2] ++;
annet
parentnode [root_2] = root_1;
RankNode [root_1] ++;




int main ()
int num_of_nodes = 6; // (0, 1, 2, 3, 4, 5)
EdgeGraph E1 (0, 1, 4);
EdgeGraph E2 (0, 2, 1);
EdgeGraph E3 (0, 3, 5);
EdgeGraph E4 (1, 3, 2);
EdgeGraph E5 (1, 4, 3);
EdgeGraph E6 (1, 5, 3);
EdgeGraph E7 (2, 3, 2);
EdgeGraph E8 (2, 4, 8);
EdgeGraph E9 (3, 4, 1);
EdgeGraph E10 (4, 5, 3);
G g1 (num_of_nodes);
G1.AddEdgeGraph (E1);
G1.AddEdgeGraph (E2);
G1.AddEdgeGraph (E3);
G1.AddEdgeGraph (E4);
G1.AddEdgeGraph (E5);
G1.AddEdgeGraph (E6);
G1.AddEdgeGraph (E7);
G1.AddEdgeGraph (E8);
G1.AddEdgeGraph (E9);
G1.AddEdgeGraph (E10);
std :: vektor MST; // dette vil lagre det minste spanningstreet
G1.Kruskalmst_algo (MST);
G1.DisplayEdraphs (MST);
retur 0;

Produksjon:

EdgeGraphs of MST: [0-2] (1) [3-4] (1) [1-3] (2) [2-3] (2) [1-5] (3)
Kruskal MST Kostnad: 9

Konklusjon:

Vi har studert Kruskals minimumsspanningstre, som er den første preferansen for folk flest når de må finne MST -grafen fra en graf. Kruskals algoritme er enkel å forstå og implementere i en virkelig applikasjon. Som Prims algoritme, er Kruskals algoritme også veldig nyttig i virkelige applikasjoner. Så vi må forstå denne algoritmen.