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

الگوریتم بورووکا یک الگوریتم حریصانه است که توسط Otakar Borůvka، ریاضیدان چک منتشر شده است که بیشتر به دلیل کارش در نظریه گراف شناخته شده است. معروف ترین برنامه آن به ما کمک می کند تا آن را پیدا کنیم حداقل درخت پوشا در یک نمودار

نکته قابل توجه در مورد این الگوریتم این است که قدیمی ترین الگوریتم درخت پوشا حداقل است. روی رکورد. Borůvka آن را در سال 1926، قبل از اینکه کامپیوترهایی که امروزه می شناسیم وجود داشته باشند، به وجود آورد. به عنوان روشی برای ساختن منتشر شد شبکه برق کارآمد.

در این درس، تجدید نظر می کنیم روی نمودارها و چه چیزهایی حداقل درختان پوشا هستند، و سپس وارد الگوریتم Borůvka شده و آن را در پایتون پیاده سازی کنید.

نمودارها و حداقل درختان پوشا

گراف یک ساختار انتزاعی است که نشان دهنده گروهی از اشیاء خاص است که نامیده می شوند گره ها (همچنین به عنوان شناخته شده است رگه ها) که در آن جفت خاصی از آن گره ها به هم متصل یا مرتبط هستند. هر یک از این اتصالات an نامیده می شود حاشیه، غیرمتمرکز.

درخت نمونه ای از نمودار است:

در تصویر بالا نمودار اول دارای 4 است گره ها و 4 لبه ها، در حالی که نمودار دوم (الف درخت دوتایی) دارای 7 است گره ها و 6 لبه ها.

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

از آنجایی که این در واقع فقط یک نمودار از مردم (گره ها) و آنها روابط (لبه ها) – نمودارها روشی عالی برای تجسم این موضوع هستند:

انواع نمودارها

بسته به روی انواع یال هایی که یک گراف دارد، دو دسته مجزا از نمودارها داریم:

• نمودارهای بدون جهت
• نمودارهای جهت دار

یک بدون جهت graph گرافی است که در آن یال ها جهت گیری ندارند. بنابراین، تمام یال های یک گراف بدون جهت، دو طرفه در نظر گرفته می شوند.

به طور رسمی، می توانیم یک گراف بدون جهت را به صورت تعریف کنیم G = (V, E) جایی که V مجموعه ای از تمام گره های گراف است و E مجموعه ای است که شامل بدون سفارش جفت عناصر از E، که نشان دهنده لبه ها هستند.

جفت‌های نامرتب در اینجا به این معنی است که رابطه بین دو گره همیشه دو طرفه است، بنابراین اگر بدانیم لبه‌ای وجود دارد که از A به B، ما مطمئناً می دانیم که یک لبه وجود دارد که از آن خارج می شود B به A.

آ جهت دار graph گرافی است که در آن یال ها جهت گیری دارند.

به طور رسمی، ما می توانیم یک گراف جهت دار را به عنوان تعریف کنیم G = (V, E) جایی که V s مجموعه ای از تمام گره های نمودار، و E مجموعه ای است که شامل سفارش داده شده جفت عناصر از E.

جفت های مرتب شده نشان می دهد که رابطه بین دو گره می تواند یک یا دو طرفه باشد. به این معنی که اگر لبه ای وجود داشته باشد که از آن می رود A به B، ما نمی توانیم بدانیم که آیا لبه ای وجود دارد که از آن خارج شود B به A.

جهت یک یال با یک فلش نشان داده می شود. به خاطر داشته باشید که روابط دو طرفه را می توان با کشیدن دو فلش مجزا نشان داد یا فقط با کشیدن دو نقطه پیکان روی هر طرف همان لبه:

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

آ وزن دار graph نموداری است که در آن به هر یال یک عدد اختصاص داده می شود – وزن آن. این وزن‌ها می‌توانند فاصله بین گره‌ها، ظرفیت، قیمت و غیره را نشان دهند روی مشکلی که داریم حل می کنیم

نمودارهای وزنی اغلب استفاده می شوند، به عنوان مثال در مسائلی که باید کوتاه ترین را پیدا کنیم یا همانطور که به زودی خواهیم دید، در مسائلی که در آنها باید حداقل درخت پوشا را پیدا کنیم.

یک بدون وزن نمودار وزن ندارد روی لبه های آن

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

درختان و درختان حداقل پوشا

در مورد درخت‌ها، زیرگراف‌ها و درخت‌های پوشا چیز زیادی می‌توان گفت، اگرچه در اینجا یک تفکیک واقعاً سریع و مختصر وجود دارد:

• آ درخت یک گراف بدون جهت است که هر دو گره دارای آن هستند دقیقا یک مسیر که آنها را به هم متصل می کند، نه بیشتر، نه کمتر.

• آ زیرگراف از یک نمودار A گرافی است که از زیرمجموعه ای از گراف به خطر افتاده است Aگره ها و لبه ها

• درخت پوشا از نمودار A زیرگرافی از نمودار است A که درختی است که مجموعه گره های آن همان گراف است A‘s

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

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

اکنون که از نظر تئوری گراف تحت پوشش قرار گرفته‌ایم، می‌توانیم با خود الگوریتم مقابله کنیم.

الگوریتم بورووکا

ایده پشت این الگوریتم بسیار ساده و شهودی است. قبلا ذکر کردیم که این یک بود حریص الگوریتم

هنگامی که یک الگوریتم است حریص، یک راه حل جهانی “بهینه” با استفاده از راه حل های کوچکتر و محلی بهینه برای مسائل فرعی کوچکتر می سازد. معمولاً با a همگرا می شود به اندازه کافی خوب راه حل، زیرا پیروی از بهینه های محلی، راه حل بهینه جهانی را تضمین نمی کند.

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

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

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

1. ما تمام گره ها را به عنوان اجزای جداگانه مقداردهی اولیه می کنیم.
2. ما حداقل درخت پوشا را مقداردهی اولیه می کنیم S به عنوان یک مجموعه خالی که حاوی محلول است.
3. اگر بیش از یک جزء وجود دارد:
   • لبه حداقل وزنی را که این جزء را به هر جزء دیگر متصل می کند، پیدا کنید.
   • اگر این لبه در حداقل درخت پوشا نباشد S، آن را اضافه می کنیم.
4. اگر فقط یک جزء باقی بماند به انتهای درخت رسیده ایم.

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

بیایید به نمودار زیر نگاهی بیندازیم و حداقل درخت پوشا آن را با استفاده از الگوریتم Borůvka پیدا کنیم:

در ابتدا، هر یک نشان دهنده یک جزء جداگانه است. یعنی ما 9 مولفه خواهیم داشت. بیایید ببینیم کوچکترین لبه های وزنی که این اجزا را به هر جزء دیگر متصل می کند چه خواهد بود:

جزء	کوچکترین لبه وزنی که آن را به اجزای دیگر متصل می کند	وزن لبه
{0}	0 – 1	4
{1}	0 – 1	4
{2}	2 – 4	2
{3}	3 – 5	5
{4}	4 – 7	1
{5}	3 – 5	10
{6}	6 – 7	1
{7}	4 – 7	1
{8}	7 – 8	3

حال، نمودار ما در این حالت خواهد بود:

لبه های سبز رنگ در این نمودار نشان دهنده یال هایی هستند که نزدیک ترین اجزای آن را به هم متصل می کنند. همانطور که می بینیم، اکنون سه جزء داریم: {0, 1}، {2, 4, 6, 7, 8} و {3, 5}. الگوریتم را تکرار می‌کنیم و سعی می‌کنیم لبه‌هایی با حداقل وزن را پیدا کنیم که می‌توانند این اجزا را به هم متصل کنند:

جزء	کوچکترین لبه وزنی که آن را به اجزای دیگر متصل می کند	وزن لبه
{0 ، 1}	0 – 6	7
{2 ، 4 ، 6 ، 7 ، 8}	2 – 3	6
{3 ، 5}	2 – 3	6

حال، نمودار ما در این حالت خواهد بود:

همانطور که می بینیم، تنها یک جزء در این نمودار باقی می ماند که نشان دهنده حداقل درخت پوشا ما است! وزن این درخت 29 است که پس از جمع کردن تمام یال ها به آن رسیدیم:

اکنون تنها کاری که باید انجام دهید پیاده سازی این الگوریتم در پایتون است.

پیاده سازی

ما قصد داریم الف را اجرا کنیم Graph کلاس، که ساختار اصلی داده ای خواهد بود که ما با آن کار خواهیم کرد. بیایید با سازنده شروع کنیم:

class Graph:
    def __init__(self, num_of_nodes):
        self.m_v = num_of_nodes
        self.m_edges = ()
        self.m_component = {}

در این سازنده، تعداد گره های گراف را به عنوان آرگومان ارائه کردیم و سه فیلد را مقداردهی اولیه کردیم:

• m_v – تعداد گره ها در نمودار.
• m_edges – لیست لبه ها.
• m_component – فرهنگ لغت که فهرست مؤلفه ای را ذخیره می کند که a node متعلق به.

حالا بیایید یک تابع کمکی بسازیم که می توانیم از آن برای اضافه کردن یک یال به گره های گراف استفاده کنیم:

    def add_edge(self, u, v, weight):
        self.m_edges.append((u, v, weight))

این تابع یک لبه به فرمت اضافه می کند (first, second, edge weight) به نمودار ما

از آنجایی که می‌خواهیم در نهایت متدی بسازیم که دو مؤلفه را متحد کند، ابتدا به روشی نیاز داریم که یک مؤلفه جدید را در یک مؤلفه مشخص منتشر کند. و در مرحله دوم، ما به روشی نیاز خواهیم داشت که شاخص مؤلفه یک داده را پیدا کند node:

    def find_component(self, u):
        if self.m_component(u) == u:
            return u
        return self.find_component(self.m_component(u))

    def set_component(self, u):
        if self.m_component(u) == u:
            return
        else:
            for k in self.m_component.keys():
                self.m_component(k) = self.find_component(k)

در این روش به صورت مصنوعی با دیکشنری مانند درخت برخورد می کنیم. می پرسیم که آیا آن را پیدا کرده ایم یا نه root جزء ما (زیرا فقط root مؤلفه ها همیشه به خودشان اشاره می کنند m_component فرهنگ لغت). اگر ما پیدا نکردیم root node، ما به صورت بازگشتی جریان را جستجو می کنیم nodeوالدین

توجه داشته باشید: دلیلی که ما آن را فرض نمی کنیم m_components به مؤلفه صحیح اشاره می کند زیرا وقتی شروع به یکسان سازی مؤلفه ها می کنیم، تنها چیزی که مطمئناً می دانیم شاخص مؤلفه آن را تغییر نمی دهد این است که root اجزاء.

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

فهرست مطالب	ارزش
0	0
1	1
2	2
3	3
4	4
5	5
6	6
7	7
8	8

ما داریم 9 اجزاء، و هر عضو به خودی خود جزء است. در تکرار دوم، به صورت زیر خواهد بود:

فهرست مطالب	ارزش
0	0
1	0
2	2
3	3
4	2
5	3
6	7
7	4
8	7

اکنون، با ردیابی به ریشه ها، خواهیم دید که اجزای جدید ما به شرح زیر خواهند بود: {0, 1}، {2, 4, 7, 6, 8} و {3, 5}.

آخرین روشی که قبل از پیاده‌سازی خود الگوریتم به آن نیاز داریم، روشی است که دو جزء را با توجه به دو گره که به مؤلفه‌های مربوطه تعلق دارند، در یک جزء متحد می‌کند:

    def union(self, component_size, u, v):
        if component_size(u) <= component_size(v):
            self.m_component(u) = v
            component_size(v) += component_size(u)
            self.set_component(u)

        elif component_size(u) >= component_size(v):
            self.m_component(v) = self.find_component(u)
            component_size(u) += component_size(v)
            self.set_component(v)

        print(self.m_component)

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

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

اکنون که همه روش‌های کاربردی مورد نیاز خود را پیاده‌سازی کرده‌ایم، در نهایت می‌توانیم به الگوریتم Borůvka شیرجه بزنیم:

    def boruvka(self):
        component_size = ()
        mst_weight = 0

        minimum_weight_edge = (-1) * self.m_v

        for node in range(self.m_v):
            self.m_component.update({node: node})
            component_size.append(1)

        num_of_components = self.m_v

        print("---------Forming MST------------")
        while num_of_components > 1:
            for i in range(len(self.m_edges)):

                u = self.m_edges(i)(0)
                v = self.m_edges(i)(1)
                w = self.m_edges(i)(2)

                u_component = self.m_component(u)
                v_component = self.m_component(v)

                if u_component != v_component:
                    if minimum_weight_edge(u_component) == -1 or \
                            minimum_weight_edge(u_component)(2) > w:
                        minimum_weight_edge(u_component) = (u, v, w)
                    if minimum_weight_edge(v_component) == -1 or \
                            minimum_weight_edge(v_component)(2) > w:
                        minimum_weight_edge(v_component) = (u, v, w)

            for node in range(self.m_v):
                if minimum_weight_edge(node) != -1:
                    u = minimum_weight_edge(node)(0)
                    v = minimum_weight_edge(node)(1)
                    w = minimum_weight_edge(node)(2)

                    u_component = self.m_component(u)
                    v_component = self.m_component(v)

                    if u_component != v_component:
                        mst_weight += w
                        self.union(component_size, u_component, v_component)
                        print("Added edge (" + str(u) + " - "
                              + str(v) + ")\n"
                              + "Added weight: " + str(w) + "\n")
                        num_of_components -= 1

            minimum_weight_edge = (-1) * self.m_v
        print("----------------------------------")
        print("The total weight of the minimal spanning tree is: " + str(mst_weight))

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

• لیستی از مؤلفه ها (برای همه گره ها راه اندازی شده است).
• فهرستی که اندازه آنها را حفظ می کند (ابتدایی به 1، و همچنین لیستی از لبه های حداقل وزن (-1 در ابتدا، زیرا ما هنوز نمی دانیم که حداقل وزن لبه ها چقدر است).

سپس، تمام یال های نمودار را مرور می کنیم و آن را پیدا می کنیم root از اجزای روی دو طرف آن لبه ها

پس از آن، ما به دنبال حداقل وزنی هستیم که این دو جزء را با استفاده از یک جفت وصل می کند if بندها:

• اگر حداقل وزن فعلی لبه جزء تو وجود ندارد (است -1)، یا اگر بزرگتر از لبه ای است که در حال حاضر مشاهده می کنیم، مقدار یالی را که مشاهده می کنیم به آن اختصاص می دهیم.
• اگر حداقل وزن فعلی لبه جزء v وجود ندارد (است -1)، یا اگر بزرگتر از لبه ای است که در حال حاضر مشاهده می کنیم، مقدار یالی را که مشاهده می کنیم به آن اختصاص می دهیم.

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

در نهایت، لیست لبه‌های حداقل وزن را به حالت اولیه باز می‌گردانیم -1، تا بتوانیم همه این کارها را دوباره انجام دهیم. تا زمانی که بیش از یک جزء در لیست اجزا وجود داشته باشد، به تکرار ادامه می دهیم.

بیایید نموداری را که در مثال بالا استفاده کردیم به عنوان ورودی الگوریتم پیاده سازی شده خود قرار دهیم:

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

چک کردن آن در اجرای الگوریتم منجر به موارد زیر می شود:

---------Forming MST------------
{0: 1, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge (0 - 1)
Added weight: 4

{0: 1, 1: 1, 2: 4, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge (2 - 4)
Added weight: 2

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8}
Added edge (3 - 5)
Added weight: 5

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 6, 7: 4, 8: 8}
Added edge (4 - 7)
Added weight: 1

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 8}
Added edge (6 - 7)
Added weight: 1

{0: 1, 1: 1, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge (7 - 8)
Added weight: 3

{0: 4, 1: 4, 2: 4, 3: 5, 4: 4, 5: 5, 6: 4, 7: 4, 8: 4}
Added edge (0 - 6)
Added weight: 7

{0: 4, 1: 4, 2: 4, 3: 4, 4: 4, 5: 4, 6: 4, 7: 4, 8: 4}
Added edge (2 - 3)
Added weight: 6

----------------------------------
The total weight of the minimal spanning tree is: 29

پیچیدگی زمانی از این الگوریتم است O(ElogV)، جایی که E تعداد لبه ها را نشان می دهد، در حالی که V تعداد گره ها را نشان می دهد.

پیچیدگی فضا از این الگوریتم است O(V + E)، از آنجایی که ما باید چند لیست را که اندازه آنها برابر با تعداد گره ها است و همچنین تمام لبه های یک نمودار را در داخل خود ساختار داده نگه داریم.

نتیجه

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

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