نمودارها در پایتون – تئوری و پیاده سازی – حداقل درختان پوشا

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

الگوریتم کروسکال یک الگوریتم حریصانه است که با یافتن بهینه های کوچک و محلی و ترکیب آنها، راه حل بهینه جهانی را پیدا می کند. علاوه بر این، هنوز هم بسیار مفید و به طور گسترده ای گسترش یافته است.

در این درس، روش عملکرد الگوریتم کروسکال را به تصویر می کشیم و توضیح می دهیم روی یک مثال عملی، و سپس پیاده سازی دقیق آن را در پایتون به شما ارائه می دهد.

ما قبلاً موضوعات زیادی را در مورد نمودارها در پایتون پوشش داده ایم. اگر علاقه مند به کسب اطلاعات بیشتر در مورد موضوعات یا الگوریتم های خاص هستید، حتما باید برخی از آنها را مطالعه کنید:

حداقل درخت پوشا چیست؟

به زبان ساده، حداقل درخت پوشا درختی است که از یک گراف وزن دار و بدون جهت ساخته شده است، بنابراین:

• همه گره ها را به هم متصل می کند (به آن رئوس نیز گفته می شود)
• دارد بدون چرخه
• دارد کوچکترین مجموع وزنهای لبه ممکن است

بیایید این را بررسی کنیم دوستانه و غیر رسمی تعریفی برای روشن کردن تمام تصورات غلط ممکن در مورد شرایط تعریف شده.

اولین واقعیت مهم این است که شما فقط می توانید MST را بسازید روی آ نمودار وزن دار و بدون جهت. این بدان معناست که هر یال نمودار دارای وزن عددی است و شما می توانید هر یال را از هر دو جهت طی کنید (برخلاف نمودارهای جهت دار).

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

MST باید داشته باشد کوچکترین مجموع وزن لبه های ممکن. گاهی اوقات چندین درخت با مجموع وزن لبه های یکسان وجود دارد. اگر این مجموع کوچکترین باشد، هر یک از آنها می تواند MST باشد.

آخرین واقعیت تقریباً خود توضیحی است. همانطور که احتمالا می دانید، درختان نوع خاصی از نمودار هستند. آنها به زبان ساده عبارتند از نمودارهای متصل بدون چرخهو MST نوعی درخت است که به این معنی است نباید هیچ چرخه ای داشته باشد.

توضیح الگوریتم کروسکال

در کنار Prim و Borůvka، الگوریتم کروسکال یکی از معروف‌ترین الگوریتم‌ها برای یافتن حداقل درخت پوشا از نمودارهای وزن‌دار و بدون جهت است. در این درس، از همان نموداری که در درس توضیح داده شده الگوریتم Borůvka استفاده می کنیم:

ایده پشت الگوریتم کروسکال بسیار ساده است، اساساً وجود دارد دو قدم که تا زمانی که MST را بدست آورید تکرار می کنید:

1. تمام لبه ها را بر اساس وزن آنها به ترتیب صعودی مرتب کنید

2. لبه را با کمترین وزن انتخاب کنید و سعی کنید آن را به درخت اضافه کنید

   • اگر یک چرخه تشکیل می دهد، از آن لبه بگذرید

3. این مراحل را تکرار کنید تا زمانی که یک درخت متصل داشته باشید که همه گره ها را پوشش دهد

برای این نمودار خاص، لیست مرتب شده از تمام یال ها به شکل زیر خواهد بود:

حاشیه، غیرمتمرکز	وزن
EF	1
CF	1
DE	2
FH	3
AB	4
EH	5
GI	5
DG	6
AC	7
BD	9
به عنوان مثال	10
قبل از میلاد مسیح	11
سلام	12
EI	15
BF	20

لبه ها EF و CF وزن یکسانی دارند، بنابراین می توانید یکی از آنها را به عنوان لبه شروع انتخاب کنید. ما فرض می کنیم که شما انتخاب کرده اید EF. در این لحظه درختی که برای ساخت MST استفاده می کنید خالی است. حالا سعی کنید اضافه کنید EF به درخت و بررسی کنید که آیا یک چرخه تشکیل می دهد.

همانطور که می بینید، اضافه کردن EF هیچ چرخه ای تشکیل نمی دهد، بنابراین می توانید آن را در درخت نگه دارید. سپس این مراحل را برای هر لبه در لیست مرتب شده تکرار می کنید. البته ابتدا لبه را با حداقل وزن چک می کنید و همینطور روی.

موقعیت جالب زمانی رخ می دهد که می خواهید آن را اضافه کنید EH به درخت:

اضافه کردن EH به درخت یک چرخه ایجاد می کند – EFH. بنابراین، شما باید حذف کنید EH از درخت، و بررسی کنید که آیا می توانید لبه بعدی را با حداقل وزن اضافه کنید – GI. بعد از اینکه اضافه کردید GI به درخت، همه گره ها بازدید می شوند:

اگرچه شما از همه گره ها بازدید کردید، درخت هنوز متصل نشده است. شما می توانید متوجه سه متمایز شوید درختان فرعی – {A, B}، {C, D, E, F, H}، و {G, I}. آن درختان فرعی الف را تشکیل می دهند حداقل جنگل پوشا که تمام گره های گراف اولیه را پوشش می دهد اما MST نیست. MST باید تمام گره های نمودار اولیه را به هم متصل کنید، بنابراین باید به افزودن یال ها ادامه دهید تا جنگل به یک درخت متصل تبدیل شود. الگوریتم Kruskal تضمین می کند که آن لبه های اضافه شده حداقل وزن ممکن را دارند.

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

این process واقعاً می توان از طریق یک انیمیشن قدردانی کرد:

روش پیاده سازی الگوریتم کروسکال در پایتون

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

پیاده سازی الف Graph کلاس

اولین چیزی که باید پیاده سازی کنید یک است Graph کلاس. این یک نمودار را نشان می دهد و تمام روش هایی را که ممکن است در هنگام کار با نمودارها به آن نیاز داشته باشید، تعریف می کند.

class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        self.m_graph = ()

    def add_edge(self, node1, node2, weight):
        self.m_graph.append((node1, node2, weight))

این یک اجرای نسبتاً عمومی از a است Graph کلاس اما چند ترفند برای سازگاری با الگوریتم Kruskal خواهد داشت. ما آن ترفندها را در زیربخش های بعدی معرفی خواهیم کرد.

همانطور که احتمالاً از قبل می دانید ، __init__ به طور موثر سازنده هر کلاس معین در پایتون است. در این حالت ، شما با فراخوانی نمودار می سازید Graph(num_of_nodes). تنها دو مقدار که در a ذخیره می شوند Graph کلاس Nuber گره ها در نمودار است (m_num_of_nodes) و مجموعه ای از لبه ها (m_graph). آن آرایه از یال ها ساختار داده ای است که برای ذخیره نمودار در این مثال استفاده می کنید.

هر یال هر گراف وزنی دقیقاً دو گره را به هم متصل می کند و وزن خاصی به آن اختصاص داده می شود. را add_edge(node1, node2, weight) روش آن خاصیت را نشان می دهد. لبه را به a اضافه می کند Graph شیء به شکل زیر – (node1, node2, weight). این ساده ترین و بسیار موثرترین راه برای نمایش گراف در پایتون است.

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

آرایه های کمکی – parent و subtree_sizes

پیاده سازی الگوریتم کروسکال خود باید کار نسبتاً ساده ای باشد. فقط چند نکته کلیدی وجود دارد که باید در نظر داشته باشید. اول از همه، با فرض اینکه از قبل فهرستی از لبه ها دارید (که به روشی که قبلاً توضیح داده شده است)، باید مرتب سازی از کوچکترین وزن لبه تا بزرگترین.

پس از آن، شما باید دو آرایه کمکی را اولیه و حفظ کنید – parent و subtree_sizes. روش ساخت آنها از اهمیت بالایی برخوردار است، بنابراین با دقت دنبال کنید. هر دوی آنها دارند اندازه ای که با تعداد گره ها در نمودار اولیه مطابقت دارد (یعنی اگر نمودار اولیه داشته باشد n گره ها ، آن دو آرایه n عناصر).

به این ترتیب، هر شاخص از آن آرایه ها به طور مستقیم دقیقاً با یک مورد مطابقت دارد node از نمودار به عنوان مثال، می توانید به تک تک اطلاعاتی که ممکن است در مورد آن نیاز داشته باشید دسترسی داشته باشید node 3 با تماس parents(3) و subtree_sizes(3).

حالا که فهمیدی چگونه برای ساخت این دو آرایه، اجازه دهید توضیح دهیم که چرا اصلاً به آنها نیاز داریم. همانطور که قبلاً بیان کردیم، الگوریتم Kruskal به طور موثر ایجاد می کند مجموعه ای از زیر درختان (یا یک جنگل) و آنها را با لبه های حداقل وزن ممکن متصل می کند. در ابتدا شما هر فردی را در نظر می گیرید node درختی مجزا باشد و شروع به اتصال آنها کند. شما زیردرخت ها را به هم متصل می کنید تا زمانی که یک درخت بدست آورید که تمام گره های گراف اولیه را به هم متصل می کند.

آنجاست که parent آرایه در جای خود قرار می گیرد. همانطور که می دانید، شاخص های آن آرایه نشان دهنده گره ها هستند (مثلاً شاخص 3 اشاره دارد به node 3 از نمودار). در parent آرایه، شما اطلاعات مربوط به آن را نگه می دارید node متعلق به کدام زیردرخت است از آنجایی که شما هر یک را در نظر می گیرید node برای اینکه در ابتدا یک زیردرخت جداگانه باشد parent آرایه به شکل زیر خواهد بود:

همانطور که می بینید، هر کدام node والد برای خودش است و درخت حاصل خالی است. هنگامی که لبه را با حداقل وزن انتخاب کردید و آن را به درخت حاصل اضافه کردید، در واقع شما دو تا از زیردرخت های شروع را به هم وصل کنید.

در نمودار مثال، لبه ای با حداقل وزن لبه ای است که گره ها را به هم متصل می کند 5 و 2، که هر دو زیردرخت گراف اولیه هستند. اتصال آنها یک زیردرخت جدید و بزرگتر را تشکیل می دهد که شامل گره ها است 2 و 5. را parent آرایه آن را با اختصاص دادن منعکس می کند node 2 به عنوان پدر و مادر node از node 5.

این کار تا زمانی ادامه می یابد که به جای چندین درخت فرعی کوچکتر، یک درخت واحد داشته باشید.

برای کمک به حفظ parent و subtree_sizes آرایه ها به روشی توصیف شده، باید روش های زیر را پیاده سازی کنیدn Graph کلاس:

def find_subtree(self, parent, i):
    if parent(i) == i:
        return i
    return self.find_subtree(parent, parent(i))


def connect_subtrees(self, parent, subtree_sizes, x, y):
    xroot = self.find_subtree(parent, x)
    yroot = self.find_subtree(parent, y)
    if subtree_sizes(xroot) < subtree_sizes(yroot):
        parent(xroot) = yroot
    elif subtree_sizes(xroot) > subtree_sizes(yroot):
        parent(yroot) = xroot
    else:
        parent(yroot) = xroot
        subtree_sizes(xroot) += 1

را find_subtree() روش به صورت بازگشتی در را جستجو می کند parentآرایه و زیردرختی را پیدا می کند که حاوی node i.

را connect_subtrees() روش دو زیردرخت را به هم متصل می کند. یک زیردرخت شامل node x و دیگری شامل node y. ابتدا آن دو زیردرخت را پیدا می کند، سپس اندازه آنها را مقایسه می کند و زیردرخت کوچکتر را به درخت بزرگتر متصل می کند.

اکنون که اجرای آن را کدنویسی و توضیح دادیم Graph کلاس در کنار تمام متدهای اضافی، می توانیم نگاهی به آن بیندازیم روش پیاده سازی الگوریتم کروسکال خود

الگوریتم MST کروسکال

با تمام روش های دیگر از a Graph کلاس توضیح داد، پیاده سازی الگوریتم Kruskal باید نسبتاً آسان باشد. ما انتخاب کرده ایم که الگوریتم را به عنوان روش در a پیاده سازی کنیم Graph کلاس:

def kruskals_mst(self):
    
    result = ()
    
    
    i = 0
    
    e = 0

    
    self.m_graph = sorted(self.m_graph, key=lambda item: item(2))
    
    
    parent = ()
    subtree_sizes = ()

    
    for node in range(self.m_num_of_nodes):
        parent.append(node)
        subtree_sizes.append(0)

    
    
    
    while e < (self.m_num_of_nodes - 1):
        
        node1, node2, weight = self.m_graph(i)
        i = i + 1

        x = self.find_subtree(parent, node1)
        y = self.find_subtree(parent, node2)

        if x != y:
            e = e + 1
            result.append((node1, node2, weight))
            self.connect_subtrees(parent, subtree_sizes, x, y)
    
    
    for node1, node2, weight in result:
        print("%d - %d: %d" % (node1, node2, weight))

خود الگوریتم تمام روش های توصیف شده قبلی را ترکیب می کند. اول از همه، لیستی از لبه ها را بر اساس وزن آنها مرتب می کند و مقداردهی اولیه می کند parent و subtree_sizes آرایه ها سپس روی لیست مرتب شده لبه ها تکرار می شود، آنها را یکی یکی انتخاب می کند و در صورت امکان به درخت حاصل اضافه می کند. الگوریتم زمانی متوقف می شود که تعداد لبه های درخت حاصل برابر باشد (num_of_nodes - 1). درخت به دست آمده حداقل درخت پوشا است که ما در تلاش برای ساختن آن بوده ایم.

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

آزمایش الگوریتم کروسکال روی نمودار نمونه

اول از همه، شما باید ایجاد کنید Graph شیئی که نمودار مثال شما را نشان می دهد:

example_graph = Graph(9)

سپس تمام گره ها را از گره مثال به گره اضافه می کنید example_graph استفاده کردن add_edge() روش:

example_graph.add_edge(0, 1, 4)
example_graph.add_edge(0, 2, 7)
example_graph.add_edge(1, 2, 11)
example_graph.add_edge(1, 3, 9)
example_graph.add_edge(1, 5, 20)
example_graph.add_edge(2, 5, 1)
example_graph.add_edge(3, 6, 6)
example_graph.add_edge(3, 4, 2)
example_graph.add_edge(4, 6, 10)
example_graph.add_edge(4, 8, 15)
example_graph.add_edge(4, 7, 5)
example_graph.add_edge(4, 5, 1)
example_graph.add_edge(5, 7, 3)
example_graph.add_edge(6, 8, 5)
example_graph.add_edge(7, 8, 12)

و در نهایت الگوریتم را اجرا کنید:

example_graph.kruskals_mst()

که خروجی زیر را به همراه خواهد داشت:

2 - 5: 1
4 - 5: 1
3 - 4: 2
5 - 7: 3
0 - 1: 4
6 - 8: 5
3 - 6: 6
0 - 2: 7

همانطور که می بینید، این خروجی MST را توصیف می کند که همان چیزی است که در بخش نشان داده شده است. توضیح الگوریتم کروسکال. هر ردیف از خروجی یک یال را به شکل زیر نشان می دهد: node1 - node2: weight. می توانید MST ساخته شده را در تصویر زیر مشاهده کنید.

پیچیدگی الگوریتم کروسکال چیست؟

بیایید فرض کنیم که شما یک نمودار با E لبه ها و N گره ها MST را با استفاده از الگوریتم Kruskal در زمان پیدا خواهید کرد O(E log E)، که معادل است O(E log N).

نتیجه

الگوریتم کروسکال یکی از پرکاربردترین الگوریتم‌ها برای یافتن حداقل درخت پوشا در نمودار در کنار الگوریتم Prim و Borůvka است. هر یک از آنها تقریباً پیچیدگی یکسانی دارند، بنابراین این شما هستید که تصمیم می گیرید از کدام یک استفاده کنید.

در این مقاله ، ما الگوریتم Kruskal را نشان داده ایم روی یک مثال عملی و اجرای واقعی به شما داده است ، بنابراین می توانید از آن در پروژه های خود استفاده کنید و روش عملکرد آن را درک کنید.