الگوریتم پریم — به زبان ساده

۳۴۶۳ بازدید
آخرین به‌روزرسانی: ۱۸ اردیبهشت ۱۴۰۲
زمان مطالعه: ۱۳ دقیقه
الگوریتم پریم — به زبان ساده

«الگوریتم پریم» (Prim’s Algorithm)، یک الگوریتم «حریصانه» (Greedy) است. این الگوریتم، با یک درخت پوشای کمینه (Minimum Spanning Tree | MST) خالی آغاز به کار می‌کند. هدف آن است که دو مجموعه از راس‌ها ساخته شوند. اولین مجموعه، شامل راس‌هایی است که در حال حاضر در درخت پوشای کمینه قرار دارند. مجموعه دیگر، شامل راس‌هایی است که هنوز در درخت قرار ندارند. در هر گام، الگوریتم همه یال‌هایی که دو مجموعه را به یکدیگر متصل می‌کنند در نظر می‌گیرد و یال دارای حداقل وزن را از میان این یال‌ها برمی‌گزیند. پس از انتخاب یال، دیگر نقطه نهایی یال را به پوشه حاوی راس‌های MST انتقال می‌دهد.

در «نظریه گراف» (Graph Theory)، به گروهی از یال‌ها که دو مجموعه از راس‌ها را در گراف به یکدیگر متصل می‌کنند «برش» (Cut) گفته می‌شود. بنابراین، در هر گام از الگوریتم پریم، می‌توان برشی را پیدا (از دو مجموعه، یکی حاوی یال‌هایی که در حال حاضر در MST قرار دارند و دیگری حاوی سایر راس‌ها است) و یال با کمترین وزن را از برش انتخاب کرد و در مجموعه MST قرار داد (مجموعه حاوی راس‌هایی است که در حال حاضر در درخت پوشای کمینه پریم قرار دارند). در ادامه، روش کار الگوریتم پریم مورد بررسی قرار گرفته و سپس، کد پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C ،C، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) ارائه شده است.

روش کار الگوریتم پریم

ایده نهفته در پس الگوریتم پریم ساده است. درخت پوشا یعنی همه راس‌ها باید به یکدیگر متصل باشند. بنابراین، دو مجموعه مجزا (که در بالا تشریح شدند) باید برای ساخت یک درخت پوشا به یکدیگر متصل شوند. همچنین، باید با یال‌های دارای حداقل وزن به یکدیگر متصل شوند تا درخت پوشای کمینه ساخته شود.

الگوریتم پریم

  1. مجموعه mstSet را بساز که راس‌هایی که در حال حاضر در درخت پوشای کمینه پریم وجود دارند در آن قرار دارد.
  2. یک مقدار کلیدی را به همه راس‌ها در گراف ورودی تخصیص بده. همه مقادیر کلیدی را با INFINITE مقداردهی اولیه کن. مقدار کلیدی صفر (۰) را به اولین راس تخصیص بده، تا این راس در ابتدا انتخاب شود.
  3. تا هنگامی که mstSet حاوی همه راس‌ها نیست:
    • راس u را که در mstSet قرار ندارد و کمترین مقدار کلیدی را دارا است انتخاب کن.
    • u را در mstSet قرار بده.
    • مقادیر کلیدی همه راس‌های مجاوری u را به روز رسانی کن. برای به روز رسانی این مقادیر کلیدی، در همه راس‌های مجاور تکرار را انجام بده. برای هر راس مجاور v، اگر وزن یال u-v کمتر از مقدار کلیدی پیشین v است، مقادیر کلیدی را به عنوان وزن u-v به روز رسانی کن.

هدف از استفاده از مقادیر کلیدی، انتخاب یال دارای کمترین وزن از برش است. مقادیر کلیدی تنها برای راس‌هایی استفاده می‌شوند که در MST قرار ندارند، مقدار کلیدی برای این راس‌ها نشان‌گر حداقل وزنی است که آن‌ها را به مجموعه قرار داده شده در MST متصل می‌کند. برای درک بهتر موضوع، در ادامه مثالی ارائه شده است. گراف زیر با ۸ راس مفروض است.

الگوریتم پریم

مجموعه mstSet به صورت اولیه خالی است و کلیدهای تخصیص پیدا کرده به راس‌ها به صورت $$ \{ 0, INF, INF, INF, INF, INF, INF, INF \} $$ هستند؛ INF در این مجموعه به معنای نامتناهی است. اکنون، راسی با کمترین مقدار کلیدی انتخاب می‌شود. راس ۰ انتخاب می‌شود که در mstSet قرار ندارد. پس از قرار دادن ۰ در مجموعه mstSet، مقادیر کلیدی راس‌های مجاور آن به روز رسانی می‌شوند. راس‌های مجاور ۰، راس‌های ۱ و ۷ هستند. مقادیر کلیدی ۱ و ۷ با ۴ و ۸ به روز رسانی می‌شوند. زیرگراف زیر، نشانگر راس‌ها و مقادیر کلیدی آن‌ها است. در شکل زیر، تنها راس‌هایی با مقادیر کلیدی متناهی نمایش داده شده‌اند. راس‌هایی که در MST قرار دارند، به رنگ سبز نمایش داده شده‌اند.

الگوریتم پریم

راسی با حداقل مقدار کلیدی که در حال حاضر در MST (درخت پوشای کمینه) قرار ندارد (در مجموعه mstSET قرار ندارد) و دارای وزن کمترین است (مقدار کلیدی) انتخاب می‌شود. بنابراین، در این وهله، راس 1 انتخاب و به mstSet اضافه می‌شود. بنابراین، mstSet اکنون به صورت {0, 1} است. مقادیر کلیدی از راس‌های مجاور ۱ به روز رسانی می‌شوند. مقدار کلیدی راس ۲ برابر با ۸ است.

الگوریتم پریم

راسی با حداقل مقدار کلیدی که در حال حاضر در MST قرار ندارد (در mstSET قرار ندارد) انتخاب می‌شود. همچنین، می‌توان راس ۷ یا ۲ را انتخاب کرد. در حال حاضر، راس ۷ انتخاب می‌شود. بنابراین، mstSet اکنون به صورت $${0, 1, 7}$$ خواهد بود. مقادیر کلیدی راس‌های مجاور ۷ به روز رسانی می‌شوند. مقدار کلیدی راس‌های ۶ و ۸ متناهی می‌شوند (به ترتیب ۱ و ۷).

الگوریتم پریم

راس با حداقل مقدار کلیدی که در حال حاضر در MST قرار ندارد (در mstSET قرار ندارد) انتخاب می‌شود. بنابراین، mstSet اکنون به صورت {0, 1, 7, 6} خواهد بود. مقدار کلیدهای راس‌های مجاور به روز رسانی می‌شود. مقدار کلیدی راس ۵ و ۸ به روز رسانی می‌شود.

الگوریتم پریم

گام‌های بالا، تا هنگامی که mstSet شامل همه راس‌های گراف نشده است، ادامه خواهد داشت. در نهایت، گراف زیر حاصل خواهد شد.

الگوریتم پریم

برنامه الگوریتم پریم

از یک آرایه بولی []mstSet برای ارائه مجموعه‌ای از راس‌هایی که در درخت پوشای کمینه قرار دارند استفاده می‌شود. اگر مقدار [mstSet[v درست (True) باشد، راس v در MST قرار دارد، در غیر این صورت، در درخت پوشای کمینه نیست. کلید آرایه []key برای ذخیره‌سازی مقادیر کلیدی همه راس‌ها مورد استفاده قرار می‌گیرد. آرایه دیگر []parent برای ذخیره‌سازی اندیس‌های راس‌های (گره‌های) والد در MST مورد استفاده قرار می‌گیرد. آرایه والد، آرایه خروجی است که برای نمایش درخت پوشای کمینه (MST) ساخته شده مورد استفاده قرار می‌گیرد.

برنامه الگوریتم پریم در ++C

1// A C++ program for Prim's Minimum  
2// Spanning Tree (MST) algorithm. The program is  
3// for adjacency matrix representation of the graph  
4#include <bits/stdc++.h> 
5using namespace std; 
6  
7// Number of vertices in the graph  
8#define V 5  
9  
10// A utility function to find the vertex with  
11// minimum key value, from the set of vertices  
12// not yet included in MST  
13int minKey(int key[], bool mstSet[])  
14{  
15    // Initialize min value  
16    int min = INT_MAX, min_index;  
17  
18    for (int v = 0; v < V; v++)  
19        if (mstSet[v] == false && key[v] < min)  
20            min = key[v], min_index = v;  
21  
22    return min_index;  
23}  
24  
25// A utility function to print the  
26// constructed MST stored in parent[]  
27int printMST(int parent[], int graph[V][V])  
28{  
29    cout<<"Edge \tWeight\n";  
30    for (int i = 1; i < V; i++)  
31        cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n";  
32}  
33  
34// Function to construct and print MST for  
35// a graph represented using adjacency  
36// matrix representation  
37void primMST(int graph[V][V])  
38{  
39    // Array to store constructed MST  
40    int parent[V];  
41      
42    // Key values used to pick minimum weight edge in cut  
43    int key[V];  
44      
45    // To represent set of vertices not yet included in MST  
46    bool mstSet[V];  
47  
48    // Initialize all keys as INFINITE  
49    for (int i = 0; i < V; i++)  
50        key[i] = INT_MAX, mstSet[i] = false;  
51  
52    // Always include first 1st vertex in MST.  
53    // Make key 0 so that this vertex is picked as first vertex.  
54    key[0] = 0;  
55    parent[0] = -1; // First node is always root of MST  
56  
57    // The MST will have V vertices  
58    for (int count = 0; count < V - 1; count++) 
59    {  
60        // Pick the minimum key vertex from the  
61        // set of vertices not yet included in MST  
62        int u = minKey(key, mstSet);  
63  
64        // Add the picked vertex to the MST Set  
65        mstSet[u] = true;  
66  
67        // Update key value and parent index of  
68        // the adjacent vertices of the picked vertex.  
69        // Consider only those vertices which are not  
70        // yet included in MST  
71        for (int v = 0; v < V; v++)  
72  
73            // graph[u][v] is non zero only for adjacent vertices of m  
74            // mstSet[v] is false for vertices not yet included in MST  
75            // Update the key only if graph[u][v] is smaller than key[v]  
76            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])  
77                parent[v] = u, key[v] = graph[u][v];  
78    }  
79  
80    // print the constructed MST  
81    printMST(parent, graph);  
82}  
83  
84// Driver code 
85int main()  
86{  
87    /* Let us create the following graph  
88        2 3  
89    (0)--(1)--(2)  
90    | / \ |  
91    6| 8/ \5 |7  
92    | / \ |  
93    (3)-------(4)  
94            9    */
95    int graph[V][V] = { { 0, 2, 0, 6, 0 },  
96                        { 2, 0, 3, 8, 5 },  
97                        { 0, 3, 0, 0, 7 },  
98                        { 6, 8, 0, 0, 9 },  
99                        { 0, 5, 7, 9, 0 } };  
100  
101    // Print the solution  
102    primMST(graph);  
103  
104    return 0;  
105}  
106  
107// This code is contributed by rathbhupendra

برنامه الگوریتم پریم در C

1// A C program for Prim's Minimum 
2// Spanning Tree (MST) algorithm. The program is 
3// for adjacency matrix representation of the graph 
4#include <limits.h> 
5#include <stdbool.h> 
6#include <stdio.h> 
7// Number of vertices in the graph 
8#define V 5 
9  
10// A utility function to find the vertex with 
11// minimum key value, from the set of vertices 
12// not yet included in MST 
13int minKey(int key[], bool mstSet[]) 
14{ 
15    // Initialize min value 
16    int min = INT_MAX, min_index; 
17  
18    for (int v = 0; v < V; v++) 
19        if (mstSet[v] == false && key[v] < min) 
20            min = key[v], min_index = v; 
21  
22    return min_index; 
23} 
24  
25// A utility function to print the 
26// constructed MST stored in parent[] 
27int printMST(int parent[], int graph[V][V]) 
28{ 
29    printf("Edge \tWeight\n"); 
30    for (int i = 1; i < V; i++) 
31        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]); 
32} 
33  
34// Function to construct and print MST for 
35// a graph represented using adjacency 
36// matrix representation 
37void primMST(int graph[V][V]) 
38{ 
39    // Array to store constructed MST 
40    int parent[V]; 
41    // Key values used to pick minimum weight edge in cut 
42    int key[V]; 
43    // To represent set of vertices not yet included in MST 
44    bool mstSet[V]; 
45  
46    // Initialize all keys as INFINITE 
47    for (int i = 0; i < V; i++) 
48        key[i] = INT_MAX, mstSet[i] = false; 
49  
50    // Always include first 1st vertex in MST. 
51    // Make key 0 so that this vertex is picked as first vertex. 
52    key[0] = 0; 
53    parent[0] = -1; // First node is always root of MST 
54  
55    // The MST will have V vertices 
56    for (int count = 0; count < V - 1; count++) { 
57        // Pick the minimum key vertex from the 
58        // set of vertices not yet included in MST 
59        int u = minKey(key, mstSet); 
60  
61        // Add the picked vertex to the MST Set 
62        mstSet[u] = true; 
63  
64        // Update key value and parent index of 
65        // the adjacent vertices of the picked vertex. 
66        // Consider only those vertices which are not 
67        // yet included in MST 
68        for (int v = 0; v < V; v++) 
69  
70            // graph[u][v] is non zero only for adjacent vertices of m 
71            // mstSet[v] is false for vertices not yet included in MST 
72            // Update the key only if graph[u][v] is smaller than key[v] 
73            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
74                parent[v] = u, key[v] = graph[u][v]; 
75    } 
76  
77    // print the constructed MST 
78    printMST(parent, graph); 
79} 
80  
81// driver program to test above function 
82int main() 
83{ 
84    /* Let us create the following graph 
85        2 3 
86    (0)--(1)--(2) 
87    | / \ | 
88    6| 8/ \5 |7 
89    | /     \ | 
90    (3)-------(4) 
91            9         */
92    int graph[V][V] = { { 0, 2, 0, 6, 0 }, 
93                        { 2, 0, 3, 8, 5 }, 
94                        { 0, 3, 0, 0, 7 }, 
95                        { 6, 8, 0, 0, 9 }, 
96                        { 0, 5, 7, 9, 0 } }; 
97  
98    // Print the solution 
99    primMST(graph); 
100  
101    return 0; 
102}

برنامه الگوریتم پریم در جاوا

1// A Java program for Prim's Minimum Spanning Tree (MST) algorithm. 
2// The program is for adjacency matrix representation of the graph 
3  
4import java.util.*; 
5import java.lang.*; 
6import java.io.*; 
7  
8class MST { 
9    // Number of vertices in the graph 
10    private static final int V = 5; 
11  
12    // A utility function to find the vertex with minimum key 
13    // value, from the set of vertices not yet included in MST 
14    int minKey(int key[], Boolean mstSet[]) 
15    { 
16        // Initialize min value 
17        int min = Integer.MAX_VALUE, min_index = -1; 
18  
19        for (int v = 0; v < V; v++) 
20            if (mstSet[v] == false && key[v] < min) { 
21                min = key[v]; 
22                min_index = v; 
23            } 
24  
25        return min_index; 
26    } 
27  
28    // A utility function to print the constructed MST stored in 
29    // parent[] 
30    void printMST(int parent[], int graph[][]) 
31    { 
32        System.out.println("Edge \tWeight"); 
33        for (int i = 1; i < V; i++) 
34            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]); 
35    } 
36  
37    // Function to construct and print MST for a graph represented 
38    // using adjacency matrix representation 
39    void primMST(int graph[][]) 
40    { 
41        // Array to store constructed MST 
42        int parent[] = new int[V]; 
43  
44        // Key values used to pick minimum weight edge in cut 
45        int key[] = new int[V]; 
46  
47        // To represent set of vertices not yet included in MST 
48        Boolean mstSet[] = new Boolean[V]; 
49  
50        // Initialize all keys as INFINITE 
51        for (int i = 0; i < V; i++) { 
52            key[i] = Integer.MAX_VALUE; 
53            mstSet[i] = false; 
54        } 
55  
56        // Always include first 1st vertex in MST. 
57        key[0] = 0; // Make key 0 so that this vertex is 
58        // picked as first vertex 
59        parent[0] = -1; // First node is always root of MST 
60  
61        // The MST will have V vertices 
62        for (int count = 0; count < V - 1; count++) { 
63            // Pick thd minimum key vertex from the set of vertices 
64            // not yet included in MST 
65            int u = minKey(key, mstSet); 
66  
67            // Add the picked vertex to the MST Set 
68            mstSet[u] = true; 
69  
70            // Update key value and parent index of the adjacent 
71            // vertices of the picked vertex. Consider only those 
72            // vertices which are not yet included in MST 
73            for (int v = 0; v < V; v++) 
74  
75                // graph[u][v] is non zero only for adjacent vertices of m 
76                // mstSet[v] is false for vertices not yet included in MST 
77                // Update the key only if graph[u][v] is smaller than key[v] 
78                if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { 
79                    parent[v] = u; 
80                    key[v] = graph[u][v]; 
81                } 
82        } 
83  
84        // print the constructed MST 
85        printMST(parent, graph); 
86    } 
87  
88    public static void main(String[] args) 
89    { 
90        /* Let us create the following graph 
91        2 3 
92        (0)--(1)--(2) 
93        | / \ | 
94        6| 8/ \5 |7 
95        | /     \ | 
96        (3)-------(4) 
97            9         */
98        MST t = new MST(); 
99        int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, 
100                                      { 2, 0, 3, 8, 5 }, 
101                                      { 0, 3, 0, 0, 7 }, 
102                                      { 6, 8, 0, 0, 9 }, 
103                                      { 0, 5, 7, 9, 0 } }; 
104  
105        // Print the solution 
106        t.primMST(graph); 
107    } 
108} 
109// This code is contributed by Aakash Hasija

برنامه الگوریتم پریم در پایتون

1# A Python program for Prim's Minimum Spanning Tree (MST) algorithm. 
2# The program is for adjacency matrix representation of the graph 
3  
4import sys # Library for INT_MAX 
5  
6class Graph(): 
7  
8    def __init__(self, vertices): 
9        self.V = vertices 
10        self.graph = [[0 for column in range(vertices)]  
11                    for row in range(vertices)] 
12  
13    # A utility function to print the constructed MST stored in parent[] 
14    def printMST(self, parent): 
15        print "Edge \tWeight"
16        for i in range(1, self.V): 
17            print parent[i], "-", i, "\t", self.graph[i][ parent[i] ] 
18  
19    # A utility function to find the vertex with  
20    # minimum distance value, from the set of vertices  
21    # not yet included in shortest path tree 
22    def minKey(self, key, mstSet): 
23  
24        # Initilaize min value 
25        min = sys.maxint 
26  
27        for v in range(self.V): 
28            if key[v] < min and mstSet[v] == False: 
29                min = key[v] 
30                min_index = v 
31  
32        return min_index 
33  
34    # Function to construct and print MST for a graph  
35    # represented using adjacency matrix representation 
36    def primMST(self): 
37  
38        # Key values used to pick minimum weight edge in cut 
39        key = [sys.maxint] * self.V 
40        parent = [None] * self.V # Array to store constructed MST 
41        # Make key 0 so that this vertex is picked as first vertex 
42        key[0] = 0 
43        mstSet = [False] * self.V 
44  
45        parent[0] = -1 # First node is always the root of 
46  
47        for cout in range(self.V): 
48  
49            # Pick the minimum distance vertex from  
50            # the set of vertices not yet processed.  
51            # u is always equal to src in first iteration 
52            u = self.minKey(key, mstSet) 
53  
54            # Put the minimum distance vertex in  
55            # the shortest path tree 
56            mstSet[u] = True
57  
58            # Update dist value of the adjacent vertices  
59            # of the picked vertex only if the current  
60            # distance is greater than new distance and 
61            # the vertex in not in the shotest path tree 
62            for v in range(self.V): 
63                # graph[u][v] is non zero only for adjacent vertices of m 
64                # mstSet[v] is false for vertices not yet included in MST 
65                # Update the key only if graph[u][v] is smaller than key[v] 
66                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]: 
67                        key[v] = self.graph[u][v] 
68                        parent[v] = u 
69  
70        self.printMST(parent) 
71  
72g = Graph(5) 
73g.graph = [ [0, 2, 0, 6, 0], 
74            [2, 0, 3, 8, 5], 
75            [0, 3, 0, 0, 7], 
76            [6, 8, 0, 0, 9], 
77            [0, 5, 7, 9, 0]] 
78  
79g.primMST(); 
80  
81# Contributed by Divyanshu Mehta

برنامه الگوریتم پریم در #C

1// A C# program for Prim's Minimum 
2// Spanning Tree (MST) algorithm. 
3// The program is for adjacency 
4// matrix representation of the graph 
5using System; 
6class MST { 
7  
8    // Number of vertices in the graph 
9    static int V = 5; 
10  
11    // A utility function to find 
12    // the vertex with minimum key 
13    // value, from the set of vertices 
14    // not yet included in MST 
15    static int minKey(int[] key, bool[] mstSet) 
16    { 
17  
18        // Initialize min value 
19        int min = int.MaxValue, min_index = -1; 
20  
21        for (int v = 0; v < V; v++) 
22            if (mstSet[v] == false && key[v] < min) { 
23                min = key[v]; 
24                min_index = v; 
25            } 
26  
27        return min_index; 
28    } 
29  
30    // A utility function to print 
31    // the constructed MST stored in 
32    // parent[] 
33    static void printMST(int[] parent, int[, ] graph) 
34    { 
35        Console.WriteLine("Edge \tWeight"); 
36        for (int i = 1; i < V; i++) 
37            Console.WriteLine(parent[i] + " - " + i + "\t" + graph[i, parent[i]]); 
38    } 
39  
40    // Function to construct and 
41    // print MST for a graph represented 
42    // using adjacency matrix representation 
43    static void primMST(int[, ] graph) 
44    { 
45  
46        // Array to store constructed MST 
47        int[] parent = new int[V]; 
48  
49        // Key values used to pick 
50        // minimum weight edge in cut 
51        int[] key = new int[V]; 
52  
53        // To represent set of vertices 
54        // not yet included in MST 
55        bool[] mstSet = new bool[V]; 
56  
57        // Initialize all keys 
58        // as INFINITE 
59        for (int i = 0; i < V; i++) { 
60            key[i] = int.MaxValue; 
61            mstSet[i] = false; 
62        } 
63  
64        // Always include first 1st vertex in MST. 
65        // Make key 0 so that this vertex is 
66        // picked as first vertex 
67        // First node is always root of MST 
68        key[0] = 0; 
69        parent[0] = -1; 
70  
71        // The MST will have V vertices 
72        for (int count = 0; count < V - 1; count++) { 
73  
74            // Pick thd minimum key vertex 
75            // from the set of vertices 
76            // not yet included in MST 
77            int u = minKey(key, mstSet); 
78  
79            // Add the picked vertex 
80            // to the MST Set 
81            mstSet[u] = true; 
82  
83            // Update key value and parent 
84            // index of the adjacent vertices 
85            // of the picked vertex. Consider 
86            // only those vertices which are 
87            // not yet included in MST 
88            for (int v = 0; v < V; v++) 
89  
90                // graph[u][v] is non zero only 
91                // for adjacent vertices of m 
92                // mstSet[v] is false for vertices 
93                // not yet included in MST Update 
94                // the key only if graph[u][v] is 
95                // smaller than key[v] 
96                if (graph[u, v] != 0 && mstSet[v] == false
97                    && graph[u, v] < key[v]) { 
98                    parent[v] = u; 
99                    key[v] = graph[u, v]; 
100                } 
101        } 
102  
103        // print the constructed MST 
104        printMST(parent, graph); 
105    } 
106  
107    // Driver Code 
108    public static void Main() 
109    { 
110  
111        /* Let us create the following graph 
112        2 3 
113        (0)--(1)--(2) 
114        | / \ | 
115        6| 8/ \5 |7 
116        | / \ | 
117        (3)-------(4) 
118            9 */
119  
120        int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, 
121                                      { 2, 0, 3, 8, 5 }, 
122                                      { 0, 3, 0, 0, 7 }, 
123                                      { 6, 8, 0, 0, 9 }, 
124                                      { 0, 5, 7, 9, 0 } }; 
125  
126        // Print the solution 
127        primMST(graph); 
128    } 
129} 
130  
131// This code is contributed by anuj_67. 

پیچیدگی زمانی روش مورد استفاده در کدهای بالا، از درجه (O(V2 است. اگر گراف ورودی با استفاده از لیست مجاورت نمایش داده شود، پیچیدگی زمانی الگوریتم پریم را می‌توان به کمک «هرم دودویی» (Binary Heap) به درجه (O(E log V کاهش داد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۸ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
۲ دیدگاه برای «الگوریتم پریم — به زبان ساده»

ترجمه قوی دارید
متشکر

سلام من در زمینه ی برش گراف کار میکنم و در این زمینه نیاز به مقداری آموزش دارم امکانش هست پل ارتباطی باشید

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *