فرادرسالگوریتم کروسکال چیست؟ – توضیح کراسکال به زبان ساده با مثال و کد
الگوریتم کروسکال یکی از الگوریتم های حریصانه در نظریه گراف‌ها و ریاضیات گسسته است که برای پیدا کردن مقدار کمینه درخت پوشا از گراف داده شده همبند، وزن‌دار و بدون جهت استفاده می‌شود. درخت پوشا زیرگرافی از گراف G(V,E) است. درخت پوشا تمام رئوس گراف داده شده را پوشش می‌دهد با این شرط که مجموع وزن یال‌های درخت در کمترین حالت ممکن باشد. در موردی که گراف داده شده همبند نباشد با به‌کار بردن الگوریتم کروسکال می‌توان MST هر جزء همبند را پیدا کرد. میزان پیچیدگی زمانی الگوریتم کروسکال برابر با O(E∗log(E)) و پیچیدگی فضایی این الگوریتم O(E) است.
در این مطلب از مجله فرادرس درباره الگوریتم کروسکال بحث کرده‌ایم. اینکه این الگوریتم چیست، چطور کار می‌کند و چگونه می‌توان این الگوریتم را پیاده‌سازی کرد. برای هر کدام مثال‌های تصویری یا کدنویسی شده آورده‌ایم و در نهایت بعضی از مهم‌ترین کاربردهای الگوریتم کروسکال را به صورت مختصر و شفاف توضیح داده‌ایم.
الگوریتم کروسکال چیست؟
فرض کنید در منطقه شهرستانی چند روستا وجود دارند. به عنوان شهردار کل منطقه، تصمیم به بازدید از تمام روستاها گرفته‌ایم. اما برای این کار زمان خیلی کمی در اختیار داریم. بنابراین می‌خواهیم همه روستاها را طوری بازدید کنیم که مسیر طی شده کمترین زمان ممکن شود.
در صورت تلاش برای فرمول‌نویسی مسئله مطرح شده بالا در مبحث نظریه گراف‌ها فرمول مورد نظر را باید با توجه به موارد زیر پیاده‌سازی کنیم.
- در نظر گرفتن روستاها به عنوان رئوس گراف
- جاده‌های بین روستاها به عنوان یال‌های گراف
- و مسافت هر جاده به عنوان وزن یال مربوطه
در چنین مواردی الگوریتم کروسکال به کمک حل مسئله می‌آید. به‌طور کل الگوریتم کروسکال برای پیدا کردن « مقدار کمینه درخت پوشا» (Minimum Spanning Tree | MST) در گراف‌های همبند وزن‌دار غیر جهت‌دار به‌کار می‌رود. قبل از بحث درباره جزئیات بیشتر الگوریتم کروسکال باید اول معنی مقدار کمینه درخت پوشا را در گراف درک کنیم.
برای مثال تصویر داده شده در پایین، گراف G را با شش راس و نُه یال نشان می‌دهد.
این گراف می‌تواند چندین درخت پوشا داشته باشد. بعضی از این درخت‌ها در تصاویر زیر همراه با هزینه مربوط به هر کدام نمایش داده شده‌اند.
اما از آنجا که حداقل یک درخت پوشا با اندازه مجموع وزن‌های کمتر وجود دارد، هیچ کدام از این درخت‌های پوشا درخت پوشای کمینه نیستند. درخت پوشای کمینه یا MST گراف بالا در تصویر زیر نمایش داده شده است.
وزن MST گراف داده شده برابر با ۱۷ است. به این معنا که نمی‌توانیم هیچ درخت پوشایی بر روی گراف G با وزن کمتر از ۱۷ پیدا کنیم.
روش های تسلط بر طراحی الگوریتم با فرادرس
الگوریتم کروسکال یکی از الگوریتم‌هایی است که برای حل مسائل مربوط به گراف‌ها طراحی شده است. دنیای کامپیوتر پر است از این الگوریتم‌ها و می‌توان گفت حرفه‌ای‌ترین برنامه‌نویسان کسانی هستند که توانایی طراحی الگوریتم‌ها را دارند. طراحی الگوریتم یکی از رشته‌های تخصصی علوم کامپیوتر است. روش‌های مختلفی برای آموزش طراحی الگوریتم وجود دارد، یکی از روش‌های خوب استفاده از کلاس‌ها و دوره‌های آموزشی است. باید توجه کنیم که فیلم‌های آموزشی نسبت به کلاس‌ها از مزیت‌های بیشتری برخوردار هستند. فرادرس نیز به عنوان یکی از بزرگترین تولید کنندگان محتوا آموزشی فارسی، فیلم‌های بسیار خوبی در زمینه طراحی الگوریتم ارائه داده است.
در ادامه، چند مورد از مزیت‌های فیلم‌های آموزشی را نسبت به کلاس‌های حضوری فهرست کرده‌ایم.
- مشکل اول این است که موسسات خیلی کمی برای آموزش طراحی الگوریتم وجود دارند.
- در صورت پیدا کردن چنین موسسه‌ای هزینه مالی زیادتری نسبت به فیلم‌های آموزشی باید متقبل شد.
- چنین کلاس‌هایی دارای زمان‌بندی مشخصی هستند که معمولا دانشجو مجبور به تنظیم زمان خود با موسسه است زیرا زمان کلاس با دانشجو تنظیم نمی‌شود.
- کیفیت آموزشی این کلاس‌ها را به‌جز از طریق کسب تجربه نمی‌توان سنجید.
به این منظور و برای راهنمایی شما همراهان عزیز، فرادرس فیلم‌های آموزشی زیادی را به‌صورت اختصاصی در این باره تولید و منتشر کرده است که در ادامه چند مورد از آن‌ها را معرفی کرده‌ایم.
- فیلم آموزش طراحی الگوریتم فرادرس
- فیلم آموزش طراحی الگوریتم همراه با حل مثال های عملی فرادرس
- فیلم آموزش حل روابط بازگشتی در سایت فرادرس
- فیلم آموزش مروری بر پیچیدگی محاسبات در وب سایت فرادرس
پیاده سازی الگوریتم کروسکال
ایده اصلی الگوریتم کروسکال برای پیداکردن درخت پوشای کمینه یا MST گراف G با V راس و E یال در دو نکته کلی خلاصه شده که در ادامه فهرست کرده‌ایم.
- باید همه یال‌ها را به ترتیب صعودی مطابق بر وزنشان منظم بچینیم.
- سپس اولین دسته یال‌ها به اندازه V−1 را انتخاب می‌کنیم، با این شرط که حلقه‌ای توسط یال‌های انتخاب شده تشکیل نشود.
برای یادگیری روش تقسیم و حل در طراحی الگوریتم می‌توانید از فیلم آموزش روش تقسیم و حل همراه با مرور و تست کنکور کارشناسی ارشد در فرادرس که در ادامه به صورت لینک آمده استفاده کنید.
باید به این نکته توجه کرد که برای هر گراف با V راس، برای تشکیل MST فقط به V-1 یال نیاز داریم. زیرا برای اتصال همه راس‌ها به هم V-1 یال کافی است.
در بخش‌های بعد با مطالعه بیشتر الگوریتم و دیدن مثال‌ها روش کار دقیق الگوریتم کروسکال را درک خواهیم کرد.
مراحل فرایند اجرای الگوریتم
برای هر گراف G=(V,E) پیدا کردن MST با استفاده از الگوریتم کروسکال شامل مراحل زیر می‌شود.
- همه یال‌های گراف را بر اساس وزنشان به صورت صعودی مرتب می‌کنیم.
- یال با کمترین وزن را پیدا می‌کنیم. اگر اضافه کردن این یال به درخت پوشای جواب باعث ایجاد حلقه شود، این یال را از داخل جواب‌ها حذف می‌کنیم. در غیر این صورت، یال پیدا شده را به جواب اضافه می‌کنیم.
- قدم بالایی را تا زمان رسیدن به تعداد V−1 یال ادامه می‌دهیم.
مثالی از الگوریتم کروسکال
در این سوال فرضی می‌خواهیم MST گراف را پیدا کنیم. شکل نمایش داده شده در تصویر زیر مر بوط به گراف پایه، همبند، وزن‌دار و غیرجهت‌داری است که از ۶ راس و ۹ یال تشکیل شده.
اکنون مطابق الگوریتم توصیف شده در بالا، برای پیدا کردن درخت پوشای کمینه این گراف باید مراحل زیر را طی کنیم.
- همه یال‌ها را بر طبق وزن‌های مربوط به هر کدام با نظم صعودی در جدولی به صورت مرتب قرار می‌دهیم.
- سپس اولین یال از دسته یال‌ها به اندازه V−1=5 را انتخاب می‌کنیم. دسته‌های انتخاب شده نباید شامل شکل حلقه شوند.
- مرحله اول: مرتب کردن یال‌ها با نظم صعودی. در جدول زیر می‌توانیم فهرست یال‌ها را بعد از مرتب کردن مشاهده کنیم.
| وزن | V | U | شماره یال |
| 2 | 5 | 4 | 1 |
| 2 | 6 | 4 | 2 |
| 3 | 4 | 3 | 3 |
| 3 | 3 | 2 | 4 |
| 4 | 5 | 3 | 5 |
| 5 | 6 | 5 | 6 |
| 6 | 5 | 2 | 7 |
| 7 | 2 | 1 | 8 |
| 8 | 3 | 1 | 9 |
- مرحله دوم: ۵ یال را از محل شروع جدول انتخاب می‌کنیم. البته به شرطی که این یال‌ها با هم حلقه تشکیل ندهند.
- یال 4⟺5 را بررسی می‌کنیم. این اولین یال است. از آنجا که یال تنها نمی‌تواند حلقه‌ای تشکیل دهد پس این یال را به گراف جواب اضافه می‌کنیم.
-
- سپس یال‌های 3
-
- این بار یال 2⟺3 را بررسی می‌کنیم. این بار هم
-
- این بار نوبت به بررسی یال 3
-
- این دفعه یال 5⟺6 را بررسی می‌کنیم. اضافه کردن این یال هم به جواب باعث ایجاد حلقه در گراف جواب می‌شود. بنابراین این یال را نیز به گراف جواب اضافه نمی‌کنیم.
-
- الان نوبت بررسی یال 2⟺5 است. اضافه کردن این یال نیز به گراف جواب باعث تشکیل حلقه 2→3→4→5→2 می‌شود. بنابراین این یال را نیز به گراف جواب اضافه نمی‌کنیم.
-
- در نهایت هم یال 1⟺2 را بررسی می‌کنیم. از آنجا که اضافه کردن این یال به گراف جواب باعث تشکیل حلقه نمی‌شود، بنابراین این یال را هم به جواب اضافه می‌کنیم. با اضافه کردن این یال، در کل ۵ یال را به گراف جواب اضافه کرده‌ایم. در نتیجه الان گراف جواب بدست آمده مطابق با درخت پوشای کمینه این گراف است.
گراف MST بعد از اضافه کردن هر ۵ یال پیدا شده به شکل زیر می‌شود.
در نهایت وزن MST را نیز می‌توان به سادگی با فرمول 7+3+3+2+2=17 بدست آورد.
مثال های کدنویسی شده الگوریتم کروسکال
در این بخش می‌خواهیم الگوریتم کروسال را با کمک کدنویسی پیاده‌سازی کنیم. برای انجام این‌کار بهترین روش در ابتدا پیاده‌سازی «شبه کد» (Pseudocode) این الگوریتم است.
توجه کنید که در زبان های برنامه نویسی مختلف سینتکس‌ها و ابزار متفاوتی برای کدنویسی موجود است، اما شبه‌کد، سینتکس جامع و خوانایی دارد. بنابراین همیشه بهتر است که در ابتدا شبه‌کد را پیاده‌سازی و درک کنیم و سپس از روی آن به پیاده‌سازی الگوریتم‌های خود بپردازیم.
1MST_Kruskal(Edges, V, E):
2 e=0, i=0
3 sum=0
4 Sort(Edges)
5 while(e<V-1):
6 u=Edges[i].u
7 v=Edges[i].v
8 if(Adding edge {u, v} do not form cycle):
9 Print(Adding edge {u, v} to MST)
10 sum+=Edges[i].weight
11 e+=1
12 i+=1کد نمایش داده شده بالا پیاده‌سازی شبه‌کد الگوریتم کروسکال است. از روی شبه‌کد بالا می‌توان این الگوریتم را به زبان‌های مختلف پیاده‌سازی کرد.
مثال های کد نویسی شده با زبان های برنامه نویسی
برای بررسی موثرتر این مطلب که آیا شامل شدن یالی به جواب، باعث تشکیل حلقه می‌شود یا نه، از مفهومی به نام «مجموعه‌های مجزا» (Disjoint-Sets) استفاده خواهیم کرد. برای کدنویسی باید مطابق شبه‌کد و الگوریتم توصیف شده در بالا به پیش برویم. در وهله اول فهرست مرتبی از یال‌ها را به صورت صعودی ایجاد می‌کنیم. سپس V−1 یال را به جواب اضافه می‌کنیم. البته توجه داریم که این یال‌ها نباید در کنار یکدیگر حلقه تشکیل بدهند. قبل از اینکه یالی را به MST اضافه کنیم، از تابع find از DSU را برای بررسی تعلق یا عدم تعلق گره‌های هر دو سر یال به مجموعه یکسان استفاده می‌کنیم.
اگر راس‌های دوسر یال به مجموعه یکسانی تعلق نداشتند، آن وقت آن یال را به MST اضافه می‌کنیم. زیرا اضافه کردن این یال به گراف جواب MST باعث ایجاد حلقه نمی‌شود. اکنون از تابع «اتحاد» (Union) DSU برای ادغام دو مجموعه مجزا استفاده خواهیم کرد. در ادامه قبل از پرداختن به کدنویسی این الگوریتم، طرح اولیه آن را مشاهده می‌کنیم.
متغیرها
- V: متغیری سراسری که تعداد رأس‌های گراف را نمایش می‌دهد.
- E: متغیر سراسری دیگری که تعداد یال‌های درون گراف را محاسبه کرده و نشان می‌دهد.
- یال‌ها: لیستی از یال‌ها که بر اساس وزنشان به صورت صعودی مرتب شده است و در الگوریتم کروسکال استفاده می‌شود.
روش
- MST_Kruskal: تابعی که مسئول پیدا کردن MST در گراف داده شده است. این تابع طبق مطالب مطرح شده درباره الگوریتم در شبه‌کد بالا پیاده‌سازی شده است.
در صورتی که به پیاده‌سازی الگوریتم‌ها به زبان برنامه‌نویسی و مبحث گراف‌ها علاقه‌مند هستید، پیشنهاد می‌کنیم مطلب برنامه تشخیص وجود دور در گراف جهت دار همراه با راهنمای کاربردی را از مجله فرادرس مطالعه کنید. در این برنامه برای تشخیص وجود دور در گراف، الگوریتم طراحی شده‌ای را معرفی کرده‌ایم. سپس این الگوریتم را به سه زبان برنامه نویسی پایتون، جاوا و ++C کدنویسی کردیم.
پیاده سازی الگوریتم کروسکال با زبان های C و ++C
در این بخش، برنامه کدنویسی شده‌ای با زبان‌های C و ++C از روی طرح اولیه و الگوریتم کروسکال توصیف شده در بالا را مشاهده می‌کنید.
1#include<bits/stdc++.h>
2using namespace std;
3// Using DSU to quickly
4// tell whether adding edge
5// will form a cycle.
6class DSU{
7
8 // Declaring two arrays to hold
9 // information about parent and
10 // rank of each node.
11 int *parent;
12 int *rank;
13public:
14 // Constructor
15 DSU(int n){
16
17 // Defining size of the arrays.
18 parent=new int[n];
19 rank=new int[n];
20
21 // Initializing their values
22 // by is and 0s.
23 for(int i=0;i<n;i++)
24 {
25 parent[i]=i;
26 rank[i]=0;
27 }
28 }
29
30 // Find function
31 int find(int node){
32
33 // If the node is the parent of
34 // itself then it is the leader
35 // of the tree.
36 if(node==parent[node]) return node;
37
38 //Else, finding parent and also
39 // compressing the paths.
40 return parent[node]=find(parent[node]);
41 }
42
43 // Union function
44 void Union(int u,int v){
45
46 // Make u as a leader
47 // of its tree.
48 u=find(u);
49
50 // Make v as a leader
51 // of its tree.
52 v=find(v);
53
54 // If u and v are not equal,
55 // because if they are equal then
56 // it means they are already in
57 // same tree and it does not make
58 // sense to perform union operation.
59 if(u!=v)
60 {
61 // Checking tree with
62 // smaller depth/height.
63 if(rank[u]<rank[v])
64 {
65 int temp=u;
66 u=v;
67 v=temp;
68 }
69 // Attaching lower rank tree
70 // to the higher one.
71 parent[v]=u;
72
73 // If now ranks are equal
74 // increasing rank of u.
75 if(rank[u]==rank[v])
76 rank[u]++;
77 }
78 }
79};
80// Edge class
81class Edge{
82public:
83 // Endpoints and weight of the edge.
84 int u,v,weight;
85 // Constructor
86 Edge(int U,int V,int Weight){
87 u=U;
88 v=V;
89 weight=Weight;
90 }
91};
92class Graph{
93public:
94 // Number of Vertices and Edges
95 int V, E;
96 // List of Edge(s).
97 vector<Edge> edges;
98 // Constructor of Graph class
99 Graph(int v,int e){
100 V=v;
101 E=e;
102 // // Initializing list of edges.
103 // edges=new ArrayList<>();
104 }
105 // comparator to compare two edges
106 // based on their edges.
107 static bool comparator(Edge e1, Edge e2)
108 {
109 return e1.weight < e2.weight;
110 }
111 // Function responsible to print MST.
112 void MST_Kruskal(){
113 // Initializing e, i, and sum with 0.
114 int e=0,i=0,sum=0;
115 // Creating an object of DSU class.
116 DSU dsu(V);
117 // Sorting edges using a custom comparator
118 sort(edges.begin(), edges.end(), comparator);
119
120 // Iterating till we include V-1 edges in MST
121 while(e<V-1)
122 {
123 Edge edge=edges[i++];
124
125 int u=dsu.find(edge.u);
126 int v=dsu.find(edge.v);
127 // Checking if adding edge with endpoints
128 // u and v form a cycle.
129 // If not
130 if(u!=v)
131 {
132 cout<<"Adding edge "<<edge.u<<" <---> "<<edge.v<<" to MST\n";
133 // Adding the weight of current edge to total
134 // weight of the MST.
135 sum+=edge.weight;
136 // Including the edge.
137 dsu.Union(u,v);
138 // Increasing the edge count.
139 e++;
140 }
141 }
142 // Printing the total sum of the MST.
143 cout<<"MST has a weight of "<<sum;
144 }
145 // Function to add edges.
146 void addEdge(int u,int v,int weight){
147 edges.push_back(Edge(u,v,weight));
148 }
149};
150int main(){
151 // Creating an object of Graph type.
152 Graph g(6,9);
153
154 // Adding 9 edges to make the same
155 // graph as given in examples.
156 g.addEdge(0,1,7);
157 g.addEdge(0,2,8);
158 g.addEdge(1,2,3);
159 g.addEdge(1,4,6);
160 g.addEdge(2,3,3);
161 g.addEdge(2,4,4);
162 g.addEdge(3,4,2);
163 g.addEdge(3,5,2);
164 g.addEdge(4,5,2);
165
166 // Calling the MST_Kruskal Function.
167 g.MST_Kruskal();
168 return 0;
169}پیاده سازی الگوریتم کروسکال با زبان Java
در این بخش، برنامه کدنویسی شده‌ای به زبان جاوا، از روی طرح اولیه و الگوریتم کروسکال توصیف شده در مطلب را مشاهده می‌کنید.
1import java.util.*;
2public class Graph{
3 // Using DSU to quickly
4 // tell whether adding edge
5 // will form a cycle.
6 static class DSU{
7
8 // Declaring two arrays to hold
9 // information about the parent and
10 // rank of each node.
11 private int parent[];
12 private int rank[];
13
14 // Constructor
15 DSU(int n){
16
17 // Defining size of the arrays.
18 parent=new int[n];
19 rank=new int[n];
20
21 // Initializing their values
22 // with i's and 0s.
23 for(int i=0;i<n;i++)
24 {
25 parent[i]=i;
26 rank[i]=0;
27 }
28 }
29
30 // Find function
31 public int find(int node){
32
33 // If the node is the parent of
34 // itself then it is the leader
35 // of the tree.
36 if(node==parent[node]) return node;
37
38 //Else, finding parent and also
39 // compressing the paths.
40 return parent[node]=find(parent[node]);
41 }
42
43 // Union function
44 public void union(int u,int v){
45
46 // Make u as a leader
47 // of its tree.
48 u=find(u);
49
50 // Make v as a leader
51 // of its tree.
52 v=find(v);
53
54 // If u and v are not equal,
55 // because if they are equal then
56 // it means they are already in
57 // same tree and it does not make
58 // sense to perform union operation.
59 if(u!=v)
60 {
61 // Checking tree with
62 // smaller depth/height.
63 if(rank[u]<rank[v])
64 {
65 int temp=u;
66 u=v;
67 v=temp;
68 }
69 // Attaching lower rank tree
70 // to the higher one.
71 parent[v]=u;
72
73 // If now ranks are equal
74 // increasing rank of u.
75 if(rank[u]==rank[v])
76 rank[u]++;
77 }
78 }
79 }
80 // Edge class
81 static class Edge{
82 // Endpoints and weight of the edge.
83 int u,v,weight;
84 // Constructor
85 Edge(int u,int v,int weight){
86 this.u=u;
87 this.v=v;
88 this.weight=weight;
89 }
90 }
91 // Number of Vertices and Edges
92 static int V, E;
93 // List of Edge(s).
94 static List<Edge> edges;
95 // Constructor of Graph class
96 Graph(int V,int E){
97 this.V=V;
98 this.E=E;
99 // Initializing list of edges.
100 edges=new ArrayList<>();
101 }
102
103 // Function responsible to print MST.
104 static void MST_Kruskal(){
105 // Initializing e, i and sum with 0.
106 int e=0,i=0,sum=0;
107 // Creating an object of DSU class.
108 DSU dsu=new DSU(V);
109 // Sorting edges using a custom comparator
110 Collections.sort(edges,
111 new Comparator<Edge>(){
112 public int compare(Edge e1,Edge e2){
113 return e1.weight-e2.weight;
114 }
115 }
116 );
117
118 // Iterating till we include V-1 edges in MST
119 while(e<V-1)
120 {
121 Edge edge=edges.get(i++);
122
123 int u=dsu.find(edge.u);
124 int v=dsu.find(edge.v);
125 // Checking if adding edge with endpoints
126 // u and v form a cycle.
127 // If not
128 if(u!=v)
129 {
130 System.out.println("Adding edge "+ edge.u +" <---> "+ edge.v +" to MST");
131 // Adding the weight of current edge to total
132 // weight of the MST.
133 sum+=edge.weight;
134 // Including the edge.
135 dsu.union(u,v);
136 // Increasing the edge count.
137 e++;
138 }
139 }
140 // Printing the total sum of the MST.
141 System.out.println("MST has a weight of "+sum);
142 }
143 // Function to add edges.
144 static void addEdge(int u,int v,int weight){
145 edges.add(new Edge(u,v,weight));
146 }
147 public static void main(String args[]){
148 // Creating an object of Graph type.
149 Graph g=new Graph(6,9);
150
151 // Adding 9 edges to make the same
152 // graph as given in examples.
153 g.addEdge(0,1,7);
154 g.addEdge(0,2,8);
155 g.addEdge(1,2,3);
156 g.addEdge(1,4,6);
157 g.addEdge(2,3,3);
158 g.addEdge(2,4,4);
159 g.addEdge(3,4,2);
160 g.addEdge(3,5,2);
161 g.addEdge(4,5,2);
162
163 // Calling the MST_Kruskal Function.
164 g.MST_Kruskal();
165 }
166}تجزیه و تحلیل پیچیدگی زمانی و فضایی الگوریتم کروسکال
در این قسمت از مطلب، پیچیدگی‌های این الگوریتم را به صورت کلی فرمول نویسی کرده‌ایم. «پیچیدگی زمانی» (Time Complexity) الگوریتم کروسکال را می‌توان با نکات زیر توصیف کرد.
- هزینه زمانی مرتب کردن E عدد یال برابر با O(E∗log(E)) است.
- برای هر یال، از الگوریتم Union-Find استفاده می‌کنیم که هزینه زمانی معادل O(E∗α(V)) بر عهده سیستم گذاشته می‌شود.
- در مقادیر عملی V، مقدار است. از آنجا که O(𝛼(𝑉)) عبارت O(E∗α(V)) را می‌توان به صورت O(E) نیز نوشت.
بنابراین کل پیچیدگی زمانی این الگوریتم برابر با ≃
پیچیدگی فضایی این الگوریتم هم به این صورت است که چون از لیست یا برداری برای ذخیره E تعداد یال گراف داده شده استفاده می‌کنیم. پیچیدگی فضایی برابر با O(E) است.
فیلم های کمک درسی در رابطه با طراحی الگوریتم
طراحی الگوریتم یکی از دروس اصلی رشته‌های مربوط به علوم کامپیوتر در دانشگاه‌ها است. این قسمت از مطلب به‌طور خاص مناسب دانشجویانی ارائه شده که نه تنها می‌خواهند بدانند که طراحی الگوریتم چیست بلکه باید برای آزمون‌های دانشگاهی و کنکور ارشد نیز آماده شوند. وب‌سایت آموزشی فرادرس فیلم‌های بسیار خوبی درباره الگوریتم با استفاده از اساتید حرفه‌ای و تجزیه و تحلیل سوالات کنکور سال‌های متمادی تهیه کرده است.
در این بخش چند مورد از این فیلم‌های آموزشی را معرفی می‌کنیم. این فیلم‌ها هم برای دانشجویان و برنامه‌نویسان و هم برای سایر افرادی که می‌خواهند با مبحث طراحی الگوریتم تا حد بسیار خوبی آشنا شوند مفید است.
- فیلم آموزشی طراحی الگوریتم همراه با مرور و تست کنکور ارشد فرادرس
- فیلم آموزش پیشرفته ساختمان داده به همراه حل سوالات کنکور ارشد و دکتری فرادرس
- فیلم آموزش روش تقسیم و حل در طراحی الگوریتم همراه با مرور و تست کنکور کارشناسی ارشد فرادرس
- فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته به‌همراه مرور و تست کنکور ارشد فرادرس
کاربردهای الگوریتم کروسکال
MST-هایی که توسط الگوریتم کروسکال پیدا می‌شوند کاربردهای فهرست شده در پایین را دارند.
- در طراحی شبکه، پیدا کردن MST حداقل مقدار سیم مورد نیاز را برای اتصال همه گره‌ها یا سرورهای شبکه، مشخص می‌کند.
- با استفاده از MST می توان مسئله فروشنده دوره‌گرد را نیز با تخمین بسیار خوبی حل کرد. این مسئله کارایی و عملکرد بسیار خوب مقدار کمینه درخت پوشا را برای حل چالش‌های بهینه‌سازی پیچیده نشان می‌دهد.
- MST برای پیکربندی پروتکل‌های Ethernet Bridging نیز استفاده می‌شود. استفاده از این درخت‌های پوشا از تشکیل حلقه در شبکه‌ها جلوگیری می‌کند.
- تمام سایر مسائل گراف دیگری که در آن‌ها باید تمام راس‌ها را با حداقل هزینه بازدید کنیم نیز با استفاده از MST قابل حل است.
جمع بندی
در این مطلب از مجله فرادرس معنی عبارت درخت پوشا در گراف‌ها همراه با درخت پوشای کمینه را با کمک مثال‌های مختلف فهمیدیم. متوجه شدیم که الگوریتم کروسکال، از نوع الگوریتم‌های حریصانه برای پیدا کردن درخت کمینه پوشا است. این الگوریتم بر روی هر گراف وزن‌دار و غیرجهت‌دار همبندی کار می‌کند. همچنین آموختیم که چگونه MST گراف را با استفاده از الگوریتم کروسکال پیدا کنیم. در نهایت، پیچیدگی‌های زمانی و فضای این الگوریتم را بررسی کردیم و با چند مورد از کاربردهای مهم این الگوریتم آشنا شدیم.
الگوریتم کروسکال یکی از مفاهیم مهم در نظریه گراف‌ها و ریاضیات گسسته است که همین‌طور که دیدیم، می‌تواند بسیار از مسائل مربوط به شبکه را حل کند. شناخت و پیاده‌سازی و کارکردن با این الگوریتم تاثیر بسیاری در مهارت کدنویسی و حل مسئله برنامه‌نویسان دارد.
