I denne vejledning lærer du, hvordan Prims algoritme fungerer. Du finder også arbejdseksempler på Prims algoritme i C, C ++, Java og Python.
Prims algoritme er en minimumsomspændende træalgoritme, der tager en graf som input og finder undersættet af kanterne på den graf, som
- danne et træ, der inkluderer hvert toppunkt
- har den mindste sum af vægte blandt alle de træer, der kan dannes ud fra grafen
Sådan fungerer Prims algoritme
Det falder ind under en klasse af algoritmer kaldet grådige algoritmer, der finder det lokale optimale i håb om at finde et globalt optimalt.
Vi starter fra et toppunkt og fortsætter med at tilføje kanter med den laveste vægt, indtil vi når vores mål.
Trinene til implementering af Prims algoritme er som følger:
- Initialiser det mindste spændende træ med et tilfældigt valgt stikpunkt.
- Find alle de kanter, der forbinder træet med nye hjørner, find minimumet og tilføj det til træet
- Fortsæt med at gentage trin 2, indtil vi får et minimum spændende træ
Eksempel på Prims algoritme
Start med en vægtet graf 
Vælg et toppunkt 
Vælg den korteste kant fra dette toppunkt og tilføj det 
Vælg det nærmeste toppunkt, der endnu ikke er i løsningen 
Vælg den nærmeste kant, der endnu ikke er i løsningen, hvis der er flere valg, skal du vælge et tilfældigt 
Gentag indtil du har et spændende træ
Prims algoritme pseudokode
Pseudokoden til prims algoritme viser, hvordan vi opretter to sæt hjørner U og VU. U indeholder listen over hjørner, der er besøgt, og VU listen over hjørner, der ikke har været. En efter en flytter vi hjørner fra sæt VU til sæt U ved at forbinde den mindste vægtkant.
T = ∅; U = ( 1 ); while (U ≠ V) let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V - U; T = T ∪ ((u, v)) U = U ∪ (v)
Python, Java og C / C ++ eksempler
Selvom der anvendes adjacency matrix repræsentation af grafer, kan denne algoritme også implementeres ved hjælp af Adjacency List for at forbedre dens effektivitet.
Python Java C C ++ # Prim's Algorithm in Python INF = 9999999 # number of vertices in graph V = 5 # create a 2d array of size 5x5 # for adjacency matrix to represent graph G = ((0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)) # create a array to track selected vertex # selected will become true otherwise false selected = (0, 0, 0, 0, 0) # set number of edge to 0 no_edge = 0 # the number of egde in minimum spanning tree will be # always less than(V - 1), where V is number of vertices in # graph # choose 0th vertex and make it true selected(0) = True # print for edge and weight print("Edge : Weight") while (no_edge G(i)(j): minimum = G(i)(j) x = i y = j print(str(x) + "-" + str(y) + ":" + str(G(x)(y))) selected(y) = True no_edge += 1
// Prim's Algorithm in Java import java.util.Arrays; class PGraph ( public void Prim(int G()(), int V) ( int INF = 9999999; int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false boolean() selected = new boolean(V); // set selected false initially Arrays.fill(selected, false); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in // graph // choose 0th vertex and make it true selected(0) = true; // print for edge and weight System.out.println("Edge : Weight"); while (no_edge < V - 1) ( // For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise // choose another vertex nearest to selected vertex at step 1. int min = INF; int x = 0; // row number int y = 0; // col number for (int i = 0; i < V; i++) ( if (selected(i) == true) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) System.out.println(x + " - " + y + " : " + G(x)(y)); selected(y) = true; no_edge++; ) ) public static void main(String() args) ( PGraph g = new PGraph(); // number of vertices in grapj int V = 5; // create a 2d array of size 5x5 // for adjacency matrix to represent graph int()() G = ( ( 0, 9, 75, 0, 0 ), ( 9, 0, 95, 19, 42 ), ( 75, 95, 0, 51, 66 ), ( 0, 19, 51, 0, 31 ), ( 0, 42, 66, 31, 0 ) ); g.Prim(G, V); ) )
// Prim's Algorithm in C #include #include #define INF 9999999 // number of vertices in graph #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight printf("Edge : Weight"); while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) printf("%d - %d : %d", x, y, G(x)(y)); selected(y) = true; no_edge++; ) return 0; )
// Prim's Algorithm in C++ #include #include using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G(V)(V) = ( (0, 9, 75, 0, 0), (9, 0, 95, 19, 42), (75, 95, 0, 51, 66), (0, 19, 51, 0, 31), (0, 42, 66, 31, 0)); int main() ( int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected(V); // set selected false initially memset(selected, false, sizeof(selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected(0) = true; int x; // row number int y; // col number // print for edge and weight cout << "Edge" << " : " << "Weight"; cout << endl; while (no_edge < V - 1) ( //For every vertex in the set S, find the all adjacent vertices // , calculate the distance from the vertex selected at step 1. // if the vertex is already in the set S, discard it otherwise //choose another vertex nearest to selected vertex at step 1. int min = INF; x = 0; y = 0; for (int i = 0; i < V; i++) ( if (selected(i)) ( for (int j = 0; j G(i)(j)) ( min = G(i)(j); x = i; y = j; ) ) ) ) ) cout << x << " - " << y << " : " << G(x)(y); cout << endl; selected(y) = true; no_edge++; ) return 0; )
Prim's vs Kruskals algoritme
Kruskals algoritme er en anden populær minimumsomspændende træalgoritme, der bruger en anden logik til at finde MST i en graf. I stedet for at starte fra et toppunkt sorterer Kruskals algoritme alle kanter fra lav vægt til høj og fortsætter med at tilføje de laveste kanter og ignorerer de kanter, der skaber en cyklus.
Prims algoritmekompleksitet
Tids kompleksiteten i Prims algoritme er O(E log V).
Prims algoritme ansøgning
- Lægning af kabler til elektriske ledninger
- I netværksdesignet
- At lave protokoller i netværkscyklusser
