TechCodeview

W tym artykule omówimy algorytm prim. Wraz z algorytmem zobaczymy także złożoność, działanie, przykład i implementację algorytmu prima.

Przed rozpoczęciem głównego tematu powinniśmy omówić podstawowe i ważne pojęcia, takie jak drzewo opinające i minimalne drzewo opinające.

Drzewo rozpinające - Drzewo rozpinające jest podgrafem nieskierowanego, spójnego grafu.

Minimalne drzewo rozpinające - Minimalne drzewo rozpinające można zdefiniować jako drzewo rozpinające, w którym suma wag krawędzi jest minimalna. Ciężar drzewa rozpinającego jest sumą ciężarów nadanych krawędziom drzewa rozpinającego.

A teraz zacznijmy główny temat.

Algorytm Prima to zachłanny algorytm używany do znalezienia minimalnego drzewa rozpinającego z wykresu. Algorytm Prima znajduje podzbiór krawędzi obejmujący każdy wierzchołek grafu w taki sposób, że suma wag krawędzi może zostać zminimalizowana.

Algorytm Prima zaczyna się od pojedynczego węzła i na każdym kroku bada wszystkie sąsiednie węzły ze wszystkimi łączącymi się krawędziami. Wybrano krawędzie o minimalnych wagach powodujących brak cykli w grafie.

Jak działa algorytm Prima?

Algorytm Prima jest algorytmem zachłannym, który zaczyna od jednego wierzchołka i kontynuuje dodawanie krawędzi o najmniejszej wadze, aż do osiągnięcia celu. Kroki implementacji algorytmu prim są następujące:

• Najpierw musimy zainicjować MST losowo wybranym wierzchołkiem.
• Teraz musimy znaleźć wszystkie krawędzie łączące drzewo z powyższego kroku z nowymi wierzchołkami. Spośród znalezionych krawędzi wybierz minimalną krawędź i dodaj ją do drzewa.
• Powtarzaj krok 2, aż utworzy się minimalne drzewo rozpinające.

Zastosowania algorytmu Prima to -

• Algorytm Prima można zastosować w projektowaniu sieci.
• Można go wykorzystać do tworzenia cykli sieciowych.
• Można go również wykorzystać do układania przewodów elektrycznych.

Przykład algorytmu Prima

Przyjrzyjmy się teraz działaniu algorytmu prima na przykładzie. Łatwiej będzie zrozumieć algorytm prima na przykładzie.

Załóżmy, że wykres ważony to -

Krok 1 - Najpierw musimy wybrać wierzchołek z powyższego grafu. Wybierzmy B.

kody kolorów Java

Krok 2 - Teraz musimy wybrać i dodać najkrótszą krawędź z wierzchołka B. Istnieją dwie krawędzie z wierzchołka B, które są B do C o wadze 10 i krawędź B do D o wadze 4. Wśród krawędzi krawędź BD ma minimalną wagę . Dodaj go więc do MST.

Krok 3 - Teraz ponownie wybierz krawędź o minimalnej wadze spośród wszystkich pozostałych krawędzi. W tym przypadku takimi krawędziami są krawędzie DE i CD. Dodaj je do MST i zbadaj sąsiedztwo C, tj. E i A. Zatem wybierz krawędź DE i dodaj ją do MST.

Krok 4 - Teraz wybierz krawędź CD i dodaj ją do MST.

Krok 5 - Teraz wybierz brzegowy CA. Tutaj nie możemy wybrać krawędzi CE, ponieważ utworzyłoby to cykl na grafie. Wybierz więc brzegowy CA i dodaj go do MST.

Zatem wykres utworzony w kroku 5 jest minimalnym drzewem rozpinającym danego wykresu. Koszt MST podano poniżej:

Koszt MST = 4 + 2 + 1 + 3 = 10 jednostek.

Algorytm

 Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT 

Złożoność algorytmu Prima

Przyjrzyjmy się teraz złożoności czasowej algorytmu Prima. Czas działania algorytmu prim zależy od użycia struktury danych dla wykresu i kolejności krawędzi. Poniższa tabela przedstawia niektóre opcje -

Złożoność czasu

Algorytm Prima można w prosty sposób zaimplementować przy użyciu macierzy sąsiedztwa lub reprezentacji graficznej listy sąsiedztwa, a dodanie krawędzi o minimalnej wadze wymaga liniowego przeszukiwania tablicy wag. Wymaga O(|V|²) czas działania. Można to jeszcze ulepszyć, stosując implementację sterty w celu znalezienia krawędzi o minimalnej wadze w wewnętrznej pętli algorytmu.

Złożoność czasowa algorytmu prim wynosi O(E logV) lub O(V logV), gdzie E jest liczbą nie. krawędzi, a V to nr. wierzchołków.

Implementacja algorytmu Prima

Przyjrzyjmy się teraz implementacji algorytmu prima.

Program: Napisz program implementujący algorytm Prima w języku C.

 #include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
 	 weight
'); printf(' %d 
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>