PRIMS -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. Spanning-treet 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.

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

1. Kruskals algoritme
2. Prims algoritme

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

Prims algoritme:

Prims algoritme brukes til å finne det minimale spanningstreet til en graf. Prims algoritme starter fra en hvilken som helst node og legger deretter til enhver tilstøtende node hvis vekt er minimum, og denne prosessen fortsetter til alle nodene i grafene blir besøkt. Når vi oppretter det minste spanningstreet på en graf, må vi heller ikke lage noen sykluser fordi sykluser ikke skal være i det minste spanningstreet.

Prims algoritme trinn:

Prims algoritme bruker den grådige tilnærmingen for det minste spanningstreet. Vi må velge hvilken som helst toppunkt på grafen og deretter velge neste adjacency toppunkt hvis vekt er mindre, og vi fortsetter denne prosessen til vi ikke får hele grafnodene tilkoblet.

Trinn 1: Velg hvilken som helst kildeutvikling i grafen.

Steg 2: Finn den minste vektkanten som ligger ved siden av kilden, og koble den deretter til det spennende treet.

Trinn 3: Gjenta trinn 2 til alle noder ikke er lagt til i minimumsspanningstreet.

Eksempel:

Nedenfor er et eksempel for å søke på et minimum spanningstre ved å bruke Prims algoritme.

1. Vi velger hvilken som helst tilfeldig node fra graf G og legger den til MST (minimum spanningstre). Vi velger her Node 0.

2. Nå velger vi den kanten som ligger i tilknytning.

3. Nå velger vi den kanten som ligger i tilknytning.

4. Nå velger vi den kanten som ligger i tilknytning.

5. Nå velger vi den kanten som ligger i tilknytning.

6. Nå velger vi den kanten som ligger i tilknytning.

7. Nå velger vi den kanten som ligger i tilknytning.

Over er vår siste MST (minimum spanningstre), og den totale kostnaden er 6.

C ++ Prims MST (minimum Spanning Tree) -program:

#inkludere
#inkludere
#inkludere
#inkludere
#inkludere
typedef std :: par Sii;
typedef std :: vektor Ssii;
int primsmst (int sourcenode, std :: vektor & graf)
// denne køen vil lagre detaljer om hver node
// sammen med deres vektverdi.
STD :: Priority_queue, std :: større> k;
k.push (std :: make_pair (0, sourcenode));
bool nodersadded [graf.størrelse()];
memset (nodersadded, falsk, størrelse av (bool)*graf.størrelse());
int mst_tree_cost = 0;
samtidig som (!k.tom ())
// Vi velger her noden som har minimumskostnader
SII itemNode;
itemNode = k.topp();
k.pop ();
int node = itemNode.sekund;
int cost = itemNode.først;
// Her sjekker vi om noen node ikke er lagt til MST,
// deretter legge til den noden.
hvis (!nodesadded [node])
mst_tree_cost += kostnad;
Nodesadded [node] = true;
// itererer over negibour -nodene som nylig ble tatt
// ut av prioriteringskøen.
// og lagt til MST som ennå ikke er lagt til
for (auto & par_node_cost: graf [node])
int adjency_node = par_node_cost.sekund;
if (nodesadded [adjency_node] == falsk)
k.push (par_node_cost);




return mst_tree_cost;

int main ()
// detaljene i grafen med kostnad og adjency node.
Ssii fromnode_0_in_graph_1 = 1,1, 2,2, 1,3,
1,4, 2,5, 1,6;
Ssii fromnode_1_in_graph_1 = 1,0, 2,2, 2,6;
Ssii fromnode_2_in_graph_1 = 2,0, 2,1, 1,3;
Ssii fromnode_3_in_graph_1 = 1,0, 1,2, 2,4;
Ssii fromnode_4_in_graph_1 = 1,0, 2,3, 2,5;
Ssii fromnode_5_in_graph_1 = 2,0, 2,4, 1,6;
Ssii fromnode_6_in_graph_1 = 1,0, 2,2, 1,5;
int num_of_nodes = 7; // Total noder (0 til 6)
std :: vektor PRIMSGRAPH;
PRIMSGRAPH.Endre størrelse (num_of_nodes);
primsgraph [0] = fromnode_0_in_graph_1;
primsgraph [1] = fromnode_1_in_graph_1;
primsgraph [2] = fromnode_2_in_graph_1;
primsgraph [3] = fromnode_3_in_graph_1;
primsgraph [4] = fromnode_4_in_graph_1;
primsgraph [5] = fromnode_5_in_graph_1;
primsgraph [6] = fromnode_6_in_graph_1;
// Som vi allerede vet, må vi velge kildestyret,
// Så vi starter fra toppunktet 0 -noden.
std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
"" << PrimsMST(0, primsgraph) << std :: endl;
retur 0;

Produksjon:

Total kostnad for minimum spanningstre etter Prims algoritme: 6

Tidskompleksitet av Prims MST -algoritme:

1. Den totale tiden som kreves for å behandle og velge den spesifikke prioriteringskønoden som ennå ikke er lagt til MST er LOGV.Men ettersom det fungerer for hvert toppunkt, er Total Time Complexity V (LOGV).

2. Grafen er ikke rettet, og de totale kantene vil være 2e. Siden vi må skyve nodene inn i prioriteringskøen, vil det ta en total tidslogg (V). Men fordi vi har totalt 2e kanter, vil vår totale push -operasjon være 2e (log (V)).

3. Total kompleksitet etter operasjon 1 og 2 er O ((e + v) log (v)).

Konklusjon:

Vi har studert prims minimumsspanningstre, som er den første preferansen for folk flest når de må finne MST -grafen fra en graf. Prims algoritme er enkel å forstå og implementere i en applikasjon i den virkelige verden.Prims algoritme er veldig nyttig i virkelige applikasjoner, for eksempel å koble jernbanespor til hele over byene. Så det er bare et enkelt eksempel, men applikasjonen er enorm, så vi må forstå denne algoritmen.