پیاده سازی گراف در پایتون

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

1. «ماتریس‌های مجاورت» (Adjacency Matrices)
2. «لیست‌های مجاورت» (Adjacency Lists)
3. روش «نمایش‌ها شیءگرایانه» (Object-Oriented Representations)
4. استفاده از دیکشنری برای نمایش رأس و یال گراف

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

ماتریس های مجاورت

ماتریس مجاورت، نوعی از ماتریس مربعی است که برای نمایش گراف به‌ کار برده می‌شود. در این ماتریس، سطر‌ها و ستون‌ها برای نمایش روئوس گراف و عناصر ماتریس برای نمایش یال‌ها استفاده می‌‌شوند. اگر بین دو رأس مختلف، یالی وجود داشته باشد، عنصر مربوط به این دو رأس در ماتریس با عدد ۱ مقداردهی می‌شود. اما اگر هیچ یالی بین دو رأس وجود نداشت، عنصر قرار گرفته در محل تقاطع این دو رأس با عدد ۰ مقداردهی می‌شود.

در کادر زیر، کد مربوط به ایجاد ماتریس مجاورت را نمایش داده‌ایم. البته عناصر درون این ماتریس به صورت فرضی مقداردهی شده‌اند.

1# Create a graph with 4 vertices and 5 edges
2graph = [[0, 1, 1, 0],
3         [1, 0, 1, 1],
4         [1, 1, 0, 1],
5         [0, 1, 1, 0]]
6
7
8# Print the graph
9for row in graph:
10    print(row)

بعد از اجرای کد بالا، ماتریس دو بعدی زیر در خروجی به کاربر نمایش داده می‌‌شود.

[0, 1, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]

اکنون مثالی را درباره گراف ساده و بدون جهتی در نظر بگیرید که شامل چهار رأس و چهار یال می‌شود.

      0
      / 
     1---2
       /
       3

برای گراف ساده بالا، ماتریس مجاورت، شبیه به ماتریس رسم شده در کادر زیر است.

   0  1  2  3
0  0  1  1  0
1  1  0  1  1
2  1  1  0  1
3  0  1  1  0

همین‌طور که می‌دانیم برای نمایش ماتریس بالا در پایتون می‌توان به شکل زیر از لیست دوبعدی استفاده کرد.

1adjacency_matrix = [
2    [0, 1, 1, 0],
3    [1, 0, 1, 1],
4    [1, 1, 0, 1],
5    [0, 1, 1, 0]
6]

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

لیست های مجاورت

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

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

1# Create a graph with 4 vertices and 5 edges
2graph = {0: [1, 2],
3         1: [0, 2, 3],
4         2: [0, 1, 3],
5         3: [1, 2]}
6
7
8# Print the graph
9for vertex in graph:
10    print(vertex, ":", graph[vertex])

بعد از اجرای کد بالا، خروجی زیر در کنسول پایتون به کاربر نمایش داده می‌‌شود.

0 : [1, 2]
1 : [0, 2, 3]
2 : [0, 1, 3]
3 : [1, 2]

اکنون مانند بخش قبلی، مثالی درباره گراف ساده‌ و بدون جهتی را در نظر بگیرید که چهار رأس و چهار یال دارد.

      0
      / 
     1---2
       /
       3

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

adjacency_list = [
    [1, 2],
    [0, 2, 3],
    [0, 1, 3],
    [1, 2]
]

در پایتون می‌توانیم لیست بالا را با کمک لیستی شامل لیست‌های دیگر – دقیقا شبیه به کادر بالا – نمایش دهیم.