تخفیف نوروزی پی استور
هزینه سفارش:
۹۹,۰۰۰ تومان
الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر میباشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده میشود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree نیز گفته میشود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گرهها یا راسها شامل شود. در ادامه به توضیح کامل الگوریتم کروسکال در Python اشاره خواهد شد.
الگوریتم کروسکال در Python برای حل مسئله درخت پوشای کمینه محصولی است که در این پست به آن پرداخته شده است. الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر میباشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده میشود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree نیز گفته میشود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گرهها یا راسها را شامل شود.
الگوریتم کروسکال برای پیدا کردن درخت پوشا بدین صورت عمل میکند ابتدا گراف G با n رأس را در نظر بگیرید.
۱. تمام یالها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گرههای G بدون یال را ایجاد کنید.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوری که حلقه ایجاد نشود.
گاهی چند یال دارای یک وزن هستند، در این حالت ترتیب یالهایی که انتخاب میشوند مهم نیست. درختهای پوشای حداقل مختلفی ممکن است حاصل شود اما مجموع وزن آنها همیشه یکسان و حداقل میشود. پیچیدگی زمانی الگوریتم (O(mn میشود. که m تعداد یالها و n تعداد رئوس گراف G است. روند کلی الگوریتم برای یک مثال بصورت زیر است.
پیاده سازی الگوریتم 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 در نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم میباشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری میباشد. خرید اثر توسط کلیه کارتهای شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود در اختیار شما قرار خواهد گرفت. کیفیت اثر مذکور توسط کارشناسان پی استور تضمین میشود.
تیم برنامه نویسی پی استور یکی از اولین گروههای تشکیل شده در مجموعه آموزشی پی استور میباشد. این تیم از اساتید مجرب و فارغ التحصیلان رشتههای فنی و مهندسی تشکیل شده که در زمینههای مختلف برنامهنویسی و تهیه سورس کد فعال هستند.
نام اثر: | تعیین درخت پوشای مینیمم با الگوریتم کروسکال در Python |
نوع اثر: | سورس کد |
برنامهنویس: | تیم برنامهنویسی پیاستور |
زبان برنامه نویسی: | Python |
ویژگی: | قابلیت دانلود و ویرایش |
توجه: کیفیت این محصول توسط پی استور تضمین شده و در صورت عدم رضایت از محصول، به انتخاب شما:
هزینه سفارش:
۹۹,۰۰۰ تومان
نظرات
احمد
دمت گرم
احمد حیدری
من این محصول رو خریداری کردم ولی می خوام گراف خودم رو بهش بدم چیکار باید کنم؟
مدیریت و پشتیبانی
سلام
دوست عزیز برای وارد کردن گراف خودتان در سورس کد از ماتریس همسایگی گراف باید استفاده کنید.