تعیین درخت پوشای مینیمم با الگوریتم کروسکال در Python

الگوریتم کروسکال در Python برای حل مسئله درخت پوشای کمینه محصولی است که در این پست به آن پرداخته شده است. الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر می‌باشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده می‌شود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree نیز گفته می‌شود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گره‌ها یا راس‌ها را شامل شود.

الگوریتم کروسکال Kruskal’s algorithm

الگوریتم کروسکال برای پیدا کردن درخت پوشا بدین صورت عمل می‌کند ابتدا گراف G با n رأس را در نظر بگیرید.

۱. تمام یال‌ها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گره‌های G بدون یال را ایجاد کنید.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوری که حلقه ایجاد نشود.

گاهی چند یال دارای یک وزن هستند، در این حالت ترتیب یال‌هایی که انتخاب می‌شوند مهم نیست. درخت‌های پوشای حداقل مختلفی ممکن است حاصل شود اما مجموع وزن آنها همیشه یکسان و حداقل می‌شود. پیچیدگی زمانی الگوریتم (O(mn می‌شود. که m تعداد یال‌ها و n تعداد رئوس گراف G است. روند کلی الگوریتم برای یک مثال بصورت زیر است.

الگوریتم کروسکال در Python

پیاده سازی الگوریتم Kruskal’s در پایتون شامل توابعی است که مراحل بالا را انجام می‌دهد قسمتی از سورس کد الگوریتم کروسکال در Python به صورت زیر است.

from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
  
    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = [] # default dictionary  
                                # to store graph 
          
   
    # function to add an edge to graph 
    def addEdge(self,u,v,w): 
        self.graph.append([u,v,w]) 
  
    # A utility function to find set of an element i 
    # (uses path compression technique) 
    def find(self, parent, i): 
        if parent[i] == i: 
            return i 
        return self.find(parent, parent[i]) 
  
    # A function that does union of two sets of x and y 
    # (uses union by rank) 
    def union(self, parent, rank, x, y): 
        xroot = self.find(parent, x) 
        yroot = self.find(parent, y) 
  
        # Attach smaller rank tree under root of  
        # high rank tree (Union by Rank) 
        if rank[xroot] < rank[yroot]: 
            parent[xroot] = yroot 
        elif rank[xroot] > rank[yroot]: 
            parent[yroot] = xroot 
  
        # If ranks are same, then make one as root  
        # and increment its rank by one 
        else : 
            parent[yroot] = xroot 
            rank[xroot] += 1
.
.
.
g = Graph(4) 
g.addEdge(0, 1, 10) 
g.addEdge(0, 2, 6) 
g.addEdge(0, 3, 5) 
g.addEdge(1, 3, 15) 
g.addEdge(2, 3, 4) 
  
g.KruskalMST()

خروجی حاصل از اجرای الگوریتم نیز بصورت زیر خواهد بود.

Following are the edges in the constructed MST
۲ -- ۳ == 4
۰ -- ۳ == 5
۰ -- ۱ == 10

درباره سورس کد الگوریتم کروسکال

این اثر تحت عنوان سورس کد تعیین درخت پوشای مینیمم با الگوریتم کروسکال در Python در نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید اثر توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود در اختیار شما قرار خواهد گرفت. کیفیت اثر مذکور توسط کارشناسان پی استور تضمین می‌شود.