Примов алгоритам

Преглед садржаја

Како функционише Примов алгоритам
Пример Примовог алгоритма
Псеудокод Прим-овог алгоритма
Примери за Питхон, Јава и Ц / Ц ++
Прим вс вс Крускал'с Алгоритхм
Сложеност Примовог алгоритма
Примов алгоритам примене

У овом упутству ћете научити како функционише Примов алгоритам. Такође, наћи ћете радне примере Прим-овог алгоритма на Ц, Ц ++, Јава и Питхон.

Примов алгоритам је минимални опсежни алгоритам стабла који узима граф као улаз и проналази подскуп ивица тог графа који

чине дрво које укључује сваки врх
има минимални збир тежина међу свим стаблима која се могу формирати из графикона

Како функционише Примов алгоритам

Подпада под класу алгоритама званих похлепни алгоритми који проналазе локални оптимум у нади да ће пронаћи глобални оптимум.

Полазимо од једног темена и настављамо да додајемо ивице са најмањом тежином док не постигнемо циљ.

Кораци за примену Приминог алгоритма су следећи:

Иницијализујте дрво са минималним распоном врховима насумично одабраним.
Пронађите све ивице које дрво повезују са новим теменима, пронађите минимум и додајте га дрвету
Понављајте корак 2 док не добијемо минимално растегнуто стабло

Пример Примовог алгоритма

Почните са пондерираним графом

Изаберите врх

Изаберите најкраћу ивицу из овог темена и додајте га

Изаберите најближи врх који још увек није у решењу

Изаберите најближу ивицу која још увек није у решењу, ако постоји више избора, одаберите један насумично

Понављајте док не имају дрвеће које растеже

Псеудокод Прим-овог алгоритма

Псеудокод за примов алгоритам показује како креирамо два скупа темена У и ВУ. У садржи листу темена која су посећена, а ВУ листу темена који нису. Један по један померамо темена из скупа ВУ у скуп У повезивањем ивице најмање тежине.

 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)

Примери за Питхон, Јава и Ц / Ц ++

Иако се користи матрична репрезентација графика суседства, овај алгоритам се такође може применити помоћу Адјаценци Лист да би се побољшала његова ефикасност.

Питхон Јава Ц Ц ++

 # 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; )

Прим вс вс Крускал'с Алгоритхм

Крускалов алгоритам је још један популаран алгоритам дрвећа са минималним распоном који користи другачију логику за проналажење МСТ-а графа. Уместо да крене од темена, Крускалов алгоритам сортира све ивице од мале тежине до велике и наставља да додаје најниже ивице, игноришући оне ивице које стварају циклус.