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

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

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

یکی از این الگوریتم ها است الگوریتم پریم. در ابتدا توسط Vojtech Jarnik در سال 1930 طراحی شد، پس از آن رابرت سی پریم آن را در سال 1957 دوباره طراحی کرد. این الگوریتم برای یافتن حداقل درخت پوشا در یک وزن دار، بدون جهت نمودار

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

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

یک درخت یک نوع گراف است، اگرچه همه نمودارها درخت نیستند. ویژگی اصلی درخت این است که هر جفت گره فقط توسط یک مسیر به هم متصل می شوندبنابراین بر خلاف انواع دیگر نمودارها، چرخه‌هایی در نمودار وجود ندارند – آنها غیر چرخه‌ای هستند.

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

نمودار سمت چپ یک درخت است و گراف سمت راست به این دلیل نیست که دارای a است چرخه. اگرچه ممکن است این درخت چندان شبیه درختی نباشد که شما به دیدن آن در پارک عادت کرده اید – بسیاری از درختان در واقع شبیه آنها هستند، با داشتن یک سلسله مراتب از root node با شاخه ها و برگ های فراوان اگرچه، انصافاً – بیشتر درختان در علوم رایانه وارونه هستند، با این root در بالا

یافته حداقل درخت پوشا (MST) یک اتفاق رایج در دنیای واقعی است. معمولاً وقتی می خواهید آن را پیدا کنید مفید است “ارزان ترین” پوشش یک منطقه خاص به عنوان مثال، یک رستوران زنجیره ای پیتزا ممکن است بخواهد بداند که رستوران های خود را در کجا باز کند تا بیشترین منطقه تحویل را در مدت زمان تضمین شده خود پوشش دهد. حداقل تعداد رستوران‌های باز – ارائه خدمات به حداکثر تعداد افراد، با حداقل سرمایه‌گذاری و در نتیجه بیشترین بازده. نتیجه یک است حداقل درخت پوشا از رستوران های آنها

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

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

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

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

ماتریس مجاورت چیست؟

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

این ساختار نشان می دهد کدام گره به کدام گره متصل است، به این معنی که آن را نشان می دهد ساختار لبه از یک نمودار ماتریس مجاورت یک ماتریس مربع با ابعاد است nxn، جایی که n تعداد گره ها در نمودار است. هنگامی که ساختار ماتریس تعریف شد، فیلدهای آن مشخص می کند که کدام گره ها دارای مسیرهای متصل به گره های دیگر هستند.

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

ما هر کدام را برچسب گذاری کرده ایم node در درخت با یک نامه همچنین، ما هر سطر و ستون از ماتریس مجاورت مربوطه را با یک برچسب گذاری کرده ایم node. بنابراین، هر فیلد از ماتریس مجاورت مربوط به دو گره است. به عنوان مثال، اگر یک درخت دارای یک لبه بین گره ها باشد A و B، میدان (A)(B) یک ماتریس مجاورت با علامت گذاری شده است 1. از سوی دیگر، اگر هیچ لبه ای بین آن گره ها وجود نداشته باشد، فیلد (A)(B) با مشخص شده است 0.

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

به همین دلیل است که یک ماتریس مجاورت یک درخت است یک متقارن ماتریس می توانید متوجه یک مورب متمایز (که در تصویر بالا مشخص شده است) ماتریس را به دو بخش آینه ای تقسیم می کند – به نام مثلث بالا و پایین.

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

شهود الگوریتم پریم

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

1. تصادفی انتخاب کنید node.
2. مسیر را با حداقل وزن متصل به انتخاب شده است node.
3. مسیر شما را به مسیر جدیدی هدایت می کند node، خود را در آنجا قرار دهید.
4. هنگامی که درخت اولیه را تشکیل دادید/به‌روزرسانی کردید، مسیر را با علامت انتخاب کنید حداقل وزن که به کل درخت متصل است. به خاطر داشته باشید که باید اجتناب از ایجاد چرخه.
5. مراحل 3 و 4 را تا زمانی که تمام رئوس را پوشانده اید تکرار کنید.

بیایید نگاهی به نمودار مثال بیندازیم و درخت پوشای حداقل آن را با استفاده از الگوریتم Prim پیدا کنیم. این نمودار همان نموداری است که در درس های مربوط به دو الگوریتم دیگر برای یافتن MST در یک گراف استفاده می شود – Kruskal’s و Borůvka’s:

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

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

در این مورد، لبه AB هیچ چرخه ای تشکیل نمی دهد، بنابراین می توانید آن را به درخت حاصل اضافه کنید:

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

پس از آن، یک لبه جدید را برای اضافه کردن و غیره انتخاب می کنید روی. بیایید به این وضعیت جالب که پس از چند بار تکرار رخ می دهد نگاهی بیندازیم:

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

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

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

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

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

اولین چیزی که باید برای الگوریتم Prim پیاده سازی کنید یک است Graph کلاس این یک کلاس پایتون است که از آن برای نشان دادن یک گراف و تمام روش‌های مرتبط برای دستکاری نمودارها استفاده خواهید کرد. در این مقاله از پیاده سازی ساده آن استفاده می کنیم و کمی آن را تغییر می دهیم تا با الگوریتم Prim سازگارتر شود:

class Graph:
    def __init__(self, num_of_nodes):
        self.m_num_of_nodes = num_of_nodes
        
        self.m_graph = ((0 for column in range(num_of_nodes)) 
                    for row in range(num_of_nodes))

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

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

این add_edge() روش یک یال به یک ماتریس مجاورت اضافه می کند. از آنجایی که الگوریتم پریم با نمودارهای بدون جهت کار می کند، add_edge() اطمینان حاصل می کند که ماتریس به دست آمده است متقارن.

الگوریتم درخت پوشا حداقل Prim

اکنون می توانید آن را تعریف کنید prims_mst() روش داخل Graph کلاس شما از آن برای تعریف تمام مراحل از الگوریتم Prim استفاده خواهید کرد و بنابراین MST را به عنوان نتیجه به دست خواهید آورد.

از آنجایی که می خواهید وزن ها را مقایسه کنید و برای شروع به دنبال حداقل وزن باشید node، باید عددی را تعریف کنید که قبل از عدد اول به عنوان حداقل موقت کار کند node به MST اختصاص داده شده است. این کمک می کند که این عدد به طور مسخره ای بالا باشد، مانند بی نهایت، تا تضمین شود که اولین node متوجه شدیم که وزن کمتری نسبت به آن دارد و انتخاب خواهد شد. به همین دلیل ما a را تعریف می کنیم positive_inf برای اندازه گیری خوب – هرچند، در مثال ما که اعداد زیر 10 تضمین شده است – مقدار موقت را در 10 از نظر فنی معتبر خواهد بود.

ما باید گره های انتخاب شده را ردیابی کنیم تا تشخیص دهیم کدام یک در MST گنجانده شده اند. هنگامی که همه گره ها بخشی از زیرگراف هستند، می توانید جستجوی MST را متوقف کنید! برای رسیدن به این هدف، می‌خواهیم فهرست درک دیگری با مقادیر بولی ایجاد کنیم – selected_nodes. هر ستون در این لیست درک جدید نشان دهنده یک است node. اگر node به عنوان بخشی از MST فیلد انتخاب شد True، و False در غیر این صورت.

این result حداقل درخت پوششی را که نتیجه الگوریتم Prim است ، ذخیره می کند. همه اینها در کنار هم جمع می شوند بخش اصلی الگوریتم – while(False in selected_nodes) حلقه ، که در آن همه گره هایی را که هنوز انتخاب نشده اند حلقه می کنیم.

MST برای این منظور واقعاً شروع یا پایان ندارد – هرچند ، از نظر الگوریتمی ، به داشتن یک start و end node. این start به سادگی اولین نفری خواهد بود که به طور تصادفی انتخاب می شود node، و end آخرین خواهد بود node ما به MST اضافه می کنیم. این متغیرها به عنوان گره ها به هم وصل می شوند و ما قصد داریم از آنها برای پر کردن ماتریس MST خود استفاده کنیم:

def prims_mst(self):
    
    postitive_inf = float('inf')

    
    
    selected_nodes = (False for node in range(self.m_num_of_nodes))

    
    result = ((0 for column in range(self.m_num_of_nodes)) 
                for row in range(self.m_num_of_nodes))
    
    indx = 0
    for i in range(self.m_num_of_nodes):
        print(self.m_graph(i))
    
    print(selected_nodes)

    
    while(False in selected_nodes):
        
        minimum = postitive_inf

        
        start = 0

        
        end = 0

        for i in range(self.m_num_of_nodes):
            
            if selected_nodes(i):
                for j in range(self.m_num_of_nodes):
                    
                    if (not selected_nodes(j) and self.m_graph(i)(j)>0):  
                        
                        if self.m_graph(i)(j) < minimum:
                            
                            minimum = self.m_graph(i)(j)
                            start, end = i, j
        
        
        selected_nodes(end) = True

        
        result(start)(end) = minimum
        
        if minimum == postitive_inf:
            result(start)(end) = 0

        print("(%d.) %d - %d: %d" % (indx, start, end, result(start)(end)))
        indx += 1
        
        result(end)(start) = result(start)(end)

    
    
    for i in range(len(result)):
        for j in range(0+i, len(result)):
            if result(i)(j) != 0:
                print("%d - %d: %d" % (i, j, result(i)(j)))

در اینجا ، ما با استفاده از دو حلقه از ماتریس مجاور نمودار اولیه حرکت کرده ایم. حلقه اول برای محور x (ردیف) و حلقه دوم برای محور y (ستون ها) است. قبل از ورود به حلقه دوم ، باید اعتبار آن را تأیید کنید node با توجه به حلقه اول انتخاب شده است که بخشی از نمودار MST را تضمین می کند. ما این را با if selected_nodes(i): در کد بالا مسدود کنید.

وقتی شروع به ساختن درخت می کنید ، هیچکدام از گره ها در ابتدا انتخاب نمی شوند ، همه آنها هستند False، بنابراین حلقه اول قبل از اینکه حتی به حلقه دوم وارد شویم پایان می یابد. به این دلیل، start و end در ابتدا روی 0 تنظیم شده اند ، و هنگامی که از حلقه خارج می شویم ، مقدار بولی که به end موقعیت تبدیل خواهد شد True. در نتیجه، یک زمینه از result پر از حداقل موجود ، و از آنجا result متقارن است ما می توانیم از همان ترفند استفاده کنیم روی را self.m_graph برای پر کردن فیلد دیگر

اکنون که یک انتخاب شده داریم node، که است مرحله 1 الگوریتم پریم، در حلقه دوم به مرحله 2 می رسیم! ابتدا از طریق هر ستون حرکت می کنید و روابط بین انتخاب شده ما را بررسی می کنید node و سایر گره ها منتخب ما node با دیگری مقایسه خواهد شد n گره ها با توجه به پارامترهای زیر:

• راس داده شده توسط i باید مسیری داشته باشد که آن را با راس وصل کند j (این به معنای وزن در (i,j) موقعیت ماتریس مجاورت باید بزرگتر از صفر باشد).
• رأس j نباید انتخاب نشود (اگر قبلاً انتخاب شده باشد ، می تواند به یک چرخه منجر شود).

با توجه به این دو شرط، می توانید وزن لبه یک رابطه معین را با حداقل کلی MST مقایسه کنید. اگر وزن کمتر از حداقل باشد، به حداقل جدید و متغیرها تبدیل می شود start و end را دریافت خواهد کرد i و j ارزش های. اگر وزن بیشتر از حداقل باشد، به جستجو در ستون های باقی مانده ادامه می دهید.

این start و end ماتریس MST را پر می کند و درخت مورد نظر ما را ایجاد می کند. پس از آن، شما تکرار شرح داده شده است process تا زمانی که تمام گره ها را از نمودار اولیه انتخاب کنید.

آزمایش الگوریتم پریم بر روی نمودار مثال

برای آزمایش اجرای الگوریتم پریم که قبلا توضیح داده شد، اجازه دهید a ایجاد کنیم Graph به عنوان مثال با 9 گره:

example_graph = Graph(9)

سپس، بیایید نمودار مثالی را که قبلاً در تصاویر و انیمیشن از آن استفاده کرده بودیم، بازسازی کنیم:

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.prims_mst()

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

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

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

به یاد داشته باشید که می توانیم با یک تصادفی شروع کنیم node، لزوماً لازم نیست با اولی شروع کنیم. اگر می‌خواهید خودتان را به چالش بکشید، می‌توانید کد را طوری تغییر دهید که یک عدد تصادفی (البته در محدوده صحیح) به عنوان شروع انتخاب شود. node و الگوریتم را مشاهده کنید که همان درخت را به ترتیب متفاوت پیدا کنید.

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

اگر الگوریتم Prim را فقط با استفاده از یک ماتریس مجاورت پیاده سازی کنید، پیچیدگی زمانی آن است O(N²) – جایی که N تعداد گره های یک گراف است. اجرای ساده پیچیدگی زمانی بالایی در این مورد به همراه دارد.

شما می توانید پیچیدگی زمانی را با انتخاب اجرای پیچیده تر، متشکل از فیبوناچی یا یک هیپ باینری در کنار ماتریس مجاورت در آن صورت، پیچیدگی زمانی می تواند باشد O(E log N)، به این معنی که الگوریتم Prim می تواند به سرعت Kruskal و Borůvka اجرا شود!

نتیجه

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