الگوریتم پریم – به زبان ساده
«الگوریتم پریم» (Prim’s Algorithm)، یک الگوریتم «حریصانه» (Greedy) است. این الگوریتم، با یک درخت پوشای کمینه (Minimum Spanning Tree | MST) خالی آغاز به کار میکند. هدف آن است که دو مجموعه از راسها ساخته شوند. اولین مجموعه، شامل راسهایی است که در حال حاضر در درخت پوشای کمینه قرار دارند. مجموعه دیگر، شامل راسهایی است که هنوز در درخت قرار ندارند. در هر گام، الگوریتم همه یالهایی که دو مجموعه را به یکدیگر متصل میکنند در نظر میگیرد و یال دارای حداقل وزن را از میان این یالها برمیگزیند. پس از انتخاب یال، دیگر نقطه نهایی یال را به پوشه حاوی راسهای MST انتقال میدهد.
در «نظریه گراف» (Graph Theory)، به گروهی از یالها که دو مجموعه از راسها را در گراف به یکدیگر متصل میکنند «برش» (Cut) گفته میشود. بنابراین، در هر گام از الگوریتم پریم، میتوان برشی را پیدا (از دو مجموعه، یکی حاوی یالهایی که در حال حاضر در MST قرار دارند و دیگری حاوی سایر راسها است) و یال با کمترین وزن را از برش انتخاب کرد و در مجموعه MST قرار داد (مجموعه حاوی راسهایی است که در حال حاضر در درخت پوشای کمینه پریم قرار دارند). در ادامه، روش کار الگوریتم پریم مورد بررسی قرار گرفته و سپس، کد پیادهسازی آن در زبانهای برنامهنویسی گوناگون شامل ++C ،C، «جاوا» (Java)، «پایتون» (Python) و «سیشارپ» (#C) ارائه شده است.
روش کار الگوریتم پریم
ایده نهفته در پس الگوریتم پریم ساده است. درخت پوشا یعنی همه راسها باید به یکدیگر متصل باشند. بنابراین، دو مجموعه مجزا (که در بالا تشریح شدند) باید برای ساخت یک درخت پوشا به یکدیگر متصل شوند. همچنین، باید با یالهای دارای حداقل وزن به یکدیگر متصل شوند تا درخت پوشای کمینه ساخته شود.
الگوریتم پریم
- مجموعه mstSet را بساز که راسهایی که در حال حاضر در درخت پوشای کمینه پریم وجود دارند در آن قرار دارد.
- یک مقدار کلیدی را به همه راسها در گراف ورودی تخصیص بده. همه مقادیر کلیدی را با INFINITE مقداردهی اولیه کن. مقدار کلیدی صفر (۰) را به اولین راس تخصیص بده، تا این راس در ابتدا انتخاب شود.
- تا هنگامی که mstSet حاوی همه راسها نیست:
- راس u را که در mstSet قرار ندارد و کمترین مقدار کلیدی را دارا است انتخاب کن.
- u را در mstSet قرار بده.
- مقادیر کلیدی همه راسهای مجاوری u را به روز رسانی کن. برای به روز رسانی این مقادیر کلیدی، در همه راسهای مجاور تکرار را انجام بده. برای هر راس مجاور v، اگر وزن یال u-v کمتر از مقدار کلیدی پیشین v است، مقادیر کلیدی را به عنوان وزن u-v به روز رسانی کن.
هدف از استفاده از مقادیر کلیدی، انتخاب یال دارای کمترین وزن از برش است. مقادیر کلیدی تنها برای راسهایی استفاده میشوند که در MST قرار ندارند، مقدار کلیدی برای این راسها نشانگر حداقل وزنی است که آنها را به مجموعه قرار داده شده در MST متصل میکند. برای درک بهتر موضوع، در ادامه مثالی ارائه شده است. گراف زیر با ۸ راس مفروض است.
مجموعه mstSet به صورت اولیه خالی است و کلیدهای تخصیص پیدا کرده به راسها به صورت هستند؛ INF در این مجموعه به معنای نامتناهی است. اکنون، راسی با کمترین مقدار کلیدی انتخاب میشود. راس ۰ انتخاب میشود که در mstSet قرار ندارد. پس از قرار دادن ۰ در مجموعه mstSet، مقادیر کلیدی راسهای مجاور آن به روز رسانی میشوند. راسهای مجاور ۰، راسهای ۱ و ۷ هستند. مقادیر کلیدی ۱ و ۷ با ۴ و ۸ به روز رسانی میشوند. زیرگراف زیر، نشانگر راسها و مقادیر کلیدی آنها است. در شکل زیر، تنها راسهایی با مقادیر کلیدی متناهی نمایش داده شدهاند. راسهایی که در MST قرار دارند، به رنگ سبز نمایش داده شدهاند.
راسی با حداقل مقدار کلیدی که در حال حاضر در MST (درخت پوشای کمینه) قرار ندارد (در مجموعه mstSET قرار ندارد) و دارای وزن کمترین است (مقدار کلیدی) انتخاب میشود. بنابراین، در این وهله، راس 1 انتخاب و به mstSet اضافه میشود. بنابراین، mstSet اکنون به صورت {0, 1} است. مقادیر کلیدی از راسهای مجاور ۱ به روز رسانی میشوند. مقدار کلیدی راس ۲ برابر با ۸ است.
راسی با حداقل مقدار کلیدی که در حال حاضر در MST قرار ندارد (در mstSET قرار ندارد) انتخاب میشود. همچنین، میتوان راس ۷ یا ۲ را انتخاب کرد. در حال حاضر، راس ۷ انتخاب میشود. بنابراین، mstSet اکنون به صورت خواهد بود. مقادیر کلیدی راسهای مجاور ۷ به روز رسانی میشوند. مقدار کلیدی راسهای ۶ و ۸ متناهی میشوند (به ترتیب ۱ و ۷).
راس با حداقل مقدار کلیدی که در حال حاضر در 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 کاهش داد.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- برنامه تشخیص وجود دور در گراف جهتدار — راهنمای کاربردی
- برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
^^
ترجمه قوی دارید
متشکر
سلام من در زمینه ی برش گراف کار میکنم و در این زمینه نیاز به مقداری آموزش دارم امکانش هست پل ارتباطی باشید