از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
نمودارها در پایتون – تئوری و پیاده سازی
سرفصلهای مطلب
نمودارها در پایتون را می توان به روش های مختلف نشان داد. قابل توجه ترین آنها هستند ماتریس مجاورت، لیست مجاورت، و لیست یال ها. در این راهنما، همه آنها را پوشش خواهیم داد. هنگام اجرای نمودارها، می توانید در اوقات فراغت خود بین این نوع نمایش ها جابجا شوید.
اول از همه، به سرعت تئوری گراف را خلاصه میکنیم، سپس ساختارهای دادهای را که میتوانید برای نمایش یک نمودار استفاده کنید، توضیح میدهیم، و در نهایت، یک پیادهسازی عملی برای هر نمایش به شما ارائه میکنیم.
نمودار چیست – به طور خلاصه
بیایید یک بار دیگر به سرعت تعاریف اولیه در مورد نمودارها را مرور کنیم. گراف یک ساختار داده ای است که می توانید از آن برای مدل سازی سلسله مراتب و روابط بین اشیا استفاده کنید. متشکل از مجموعه ای از گره ها و مجموعه ای از لبه ها. گره ها اشیاء مجزا را نشان می دهند، در حالی که لبه ها روابط بین آن اشیاء را نشان می دهند.
توجه داشته باشید: دوباره، اصطلاحات “node’ و ‘راس’ (‘nodes’ و ‘vertices’) اغلب به جای هم استفاده می شوند. در این دوره، ما ترجیح دادیم از این اصطلاح استفاده کنیم node، اما همان معنای اصطلاح را دارد راس.
اگر هر یال در نمودار یک ارتباط دو طرفه را نشان دهد، آن را نمودار می نامیم بدون جهت. از سوی دیگر، اگر بتوانید هر یال را فقط در یک جهت طی کنید، نمودار این است جهت دار.
لازم نیست همه گرههای یک گراف با دیگران مرتبط باشند. اگر می توانید به هر کدام دسترسی داشته باشید node از هر دیگری node در یک نمودار – ما آن گراف را می نامیم متصل. اما گاهی اوقات گره هایی وجود دارند که از هیچ گره دیگری نمی توانید به آنها دسترسی داشته باشید node در یک نمودار – همین است قطع شده نمودارها همه چیز در مورد. تصور غلط رایج این است که هر نموداری باید به هم متصل شود، اما واقعیت این است که اینطور نیست – در واقع، یک گراف نمیتواند حاوی هیچ لبهای باشد، فقط گرهها را شامل شود:
از نقطه نظر پیاده سازی، آخرین چیزی که باید پوشش دهیم این است وزن یک لبه. این یک مقدار عددی است که به لبه اختصاص داده می شود و میزان آن را توضیح می دهد هزینه ها برای عبور از آن لبه هرچه وزن یک لبه کوچکتر باشد، عبور از آن ارزانتر است. مستقر روی که، نمودارهایی با وزن های اختصاص داده شده به لبه های آنها نامیده می شوند نمودارهای وزنی:
مسلح به دانش اساسی، شما می توانید عمیق تر به راه های پیاده سازی یک نمودار شیرجه بزنید!
سه روش رایج برای نمایش نمودار
در این بخش، رایجترین روشهایی را که میتوانید یک نمودار را نشان دهید، مرور میکنیم. ما شهود پشت هر یک از آنها را توضیح می دهیم و چند مثال گویا را برای شما بیان می کنیم. پس از آن، می توانید از این دانش برای پیاده سازی یک نمودار در پایتون استفاده کنید.
به طور کلی، گرههای هر گراف معینی برای اجرای سادهتر با اعداد (از صفر شروع میشوند) برچسبگذاری میشوند. به همین دلیل است که در مثالها و پیادهسازیهای زیر از آن نشانهگذاری استفاده خواهیم کرد.
ما از موارد زیر استفاده خواهیم کرد نمودار جهت دار وزنی به عنوان مثال در بخش های زیر:
توجه داشته باشید: ما یک نمودار جهت دار وزنی را به عنوان مثال انتخاب کرده ایم زیرا بیشتر تفاوت های ظریف اجرا را نشان می دهد. به طور کلی، جابجایی بین نمودارهای وزنی و بدون وزن بسیار ساده است. جابهجایی بین نمودارهای جهتدار و غیر جهتدار نیز کار بسیار آسانی است. در صورت نیاز به هر یک از آن موضوعات در بخش های بعدی خواهیم پرداخت.
لیست لبه ها
فهرست یال ها احتمالاً ساده ترین راه برای نشان دادن a است نمودار، اما از آنجایی که فاقد ساختار مناسب است، اغلب فقط برای اهداف تصویری استفاده می شود. ما از آن برای توضیح برخی از الگوریتمهای نمودار استفاده میکنیم، زیرا هزینههای سربار کمی ارائه میکند و به ما امکان تمرکز میدهد. روی اجرای الگوریتم، به جای اجرای خود نمودار.
همانطور که می دانید، هر لبه دو گره را به هم متصل می کند و ممکن است وزنی به آن اختصاص داده شود. بنابراین، هر یال با یک لیست به شکل زیر نمایش داده می شود: (node1, node2, weight)
، جایی که weight
یک ویژگی اختیاری است (اگر نمودار وزنی ندارید، لازم نیست). همانطور که از نام آن پیداست، لیست یال ها یک نمودار را به عنوان لیستی از یال ها ذخیره می کند که به روش توصیف شده نشان داده شده اند.
بیایید نگاهی به یک نمودار وزن دار جهت دار و لیست لبه های آن بیندازیم:
همانطور که می بینید، لیست لبه ها در واقع یک جدول است. هر ردیف از آن جدول نشان دهنده یک یال – دو تا از گره های آن و وزن آن لبه است. از آنجایی که این یک نمودار وزنی است، ترتیب گره ها در نمایش یال، جهت یال را نشان می دهد. فقط می توانید از لبه عبور کنید node1
به node2
.
از سوی دیگر، شما دو رویکرد برای مقابله دارید نمودارهای بدون جهت. این رویکرد اول اضافه کردن دو ردیف برای هر کدام است node – یکی برای هر جهت لبه. این رویکرد از نظر فضا ناکارآمد است، اما اگر از نمودارهای جهت دار و غیر جهت دار به جای یکدیگر استفاده می کنید، باید از آن استفاده کنید. این رویکرد دوم فقط در صورتی می توان از آن استفاده کرد که مطمئن باشید فقط با نمودارهای غیر جهت دار سر و کار دارید. در آن صورت، می توانید هر یال را بدون جهت در نظر بگیرید و نمایش را یکسان نگه دارید – یک ردیف برای هر یال.
طرفداران:
- ساده و آسان برای درک
- برای اهداف گویا عالی است
- یک نمودار را در هر تعریف نشان می دهد (مجموعه ای از گره ها و مجموعه ای از لبه ها)
معایب:
- به هیچ شکل و فرمی ساختار ندارد
- برای هیچ برنامه دنیای واقعی واجد شرایط نیست
- کارآمد نیست
- به اندازه کافی همه کاره نیست تا نمودارهای جهت دار و بدون جهت را به جای یکدیگر نشان دهد
ماتریس مجاورت
ماتریس مجاورت یکی از محبوبترین راهها برای نمایش نمودار است، زیرا سادهترین راه برای درک و پیادهسازی است و برای بسیاری از برنامهها به خوبی کار میکند. از یک استفاده می کند nxn
ماتریس برای نشان دادن یک نمودار (n
تعداد گره های یک گراف است). به عبارت دیگر، تعداد سطرها و ستون ها برابر با تعداد گره های یک نمودار است.
در ابتدا، هر فیلد ماتریس با مقدار خاصی که انتخاب میکنید تنظیم میشود. inf
، 0
، -1
، False
و غیره، نشان می دهد که هیچ گره ای در نمودار وجود ندارد. پس از مرحله اولیه، می توانید هر لبه نمودار را با پر کردن فیلد مربوطه اضافه کنید 1
(برای نمودارهای بدون وزن) یا وزن لبه (برای نمودارهای وزنی).
ماتریس ذکر شده اساساً یک جدول است که هر سطر و ستون آن یکی را نشان می دهد node از نمودار مثلا ردیف 3
اشاره دارد به node 3
– به همین دلیل است که می توانید از یک ماتریس مجاورت برای نمایش تنها نمودارهایی با گره های دارای برچسب عددی استفاده کنید.
توجه داشته باشید: در واقع، میتوانید پیادهسازی یک ماتریس مجاورت را تغییر دهید تا بتواند گرههایی با نامهای متفاوت را مدیریت کند، اما کار اضافی مورد نیاز معمولاً دستاوردهای بالقوه را از بین میبرد. به همین دلیل است که ما استفاده از آن را انتخاب کرده ایم ساده تر پیاده سازی – فقط گره های دارای برچسب شماره.
فیلدی که محل تقاطع ردیف است i
و ستون j
به وجود یا وزن لبه بین گره ها اشاره دارد i
و j
. به عنوان مثال، اگر فیلدی را که محل تلاقی ردیف است پر کنید 1
و ستون 4
، نشان می دهد که گره های اتصال لبه وجود دارد 1
و 4
(به ترتیب خاص). اگر یک نمودار وزن دارد، آن فیلد را با علامت پر می کنید وزن لبه یا 1
در مورد یک نمودار بدون وزن.
در شرایطی که نمودارهای بدون جهت، باید دو ورودی برای هر لبه اضافه کنید – یکی برای هر جهت.
اگر توضیح قبلی به اندازه کافی واضح نبود، بیایید سعی کنیم آن را با نشان دادن روش ایجاد یک ماتریس مجاورت ساده کنیم. روی مثال نمودار زیر:
وجود دارد n
گره ها در این نمودار بنابراین، ما یک جدول با n
سطرها و ستون ها و تمام سلول ها با 0
– مقدار ویژه ای که نشان می دهد هیچ لبه ای بین هر دو گره وجود ندارد. از آنجایی که نمودار مثال وزن و جهت دار است، باید:
- هر لبه را در یک نمودار اسکن کنید
- شروع و پایان را تعیین کنید node از آن لبه
- وزن آن لبه را تعیین کنید
- فیلد مناسب ماتریس را با مقدار وزن پر کنید
بیایید از لبه استفاده کنیم 4-3
به عنوان مثال. آغاز node است 4
و در پایان node است 3
، بنابراین می دانید که باید فیلدی را که محل تقاطع ردیف است پر کنید 4
و ستون 3
. از تصویر می توان فهمید که وزن لبه است 11
، بنابراین شما فیلد مناسب را با آن پر می کنید 11
. اکنون حضور لبه را مشخص کرده اید 4-3
. که process تا زمانی که تمام لبه ها را در نمودار علامت گذاری کنید تکرار می شود.
طرفداران:
- زمان کم جستجو – می توانید تعیین کنید که آیا لبه در زمان وجود دارد یا خیر
O(1)
- افزودن/حذف لبه ها طول می کشد
O(1)
زمان - آسان برای پیاده سازی و درک
معایب:
- فضای بیشتری را اشغال می کند
O(num_of_nodes²)
- اضافه کردن node طول می کشد
O(num_of_nodes²)
زمان - یافتن گره های مجاور انتخاب شده پرهزینه است node –
O(num_of_nodes)
- پیمودن یک نمودار پرهزینه است –
O(num_of_nodes²)
- برچسب زدن/شمارش لبه ها پرهزینه است –
O(num_of_nodes²)
لیست مجاورت
لیست مجاورت کارآمدترین راه برای ذخیره یک نمودار است. این به شما امکان میدهد فقط یالهایی را که در یک نمودار وجود دارند، ذخیره کنید، که برعکس یک ماتریس مجاورت است، که به صراحت تمام یالهای ممکن را – هم موجود و هم غیر موجود – ذخیره میکند. یک ماتریس مجاورت در ابتدا برای نشان دادن نمودارهای بدون وزن، اما به مؤثرترین روش ممکن – فقط با استفاده از یک آرایه توسعه داده می شود.
همانطور که در تصویر زیر می بینید، ما می توانیم نمودار مثال خود را تنها با استفاده از یک آرایه از 12 مقدار صحیح نمایش دهیم. آن را با ماتریس مجاورت مقایسه کنید – از آن تشکیل شده است n²
عناصر (n
تعداد گره ها در یک گراف است)، که در آن لیست مجاورت فقط در نظر گرفته می شود n+e
عناصر (e
تعداد لبه ها است). اگر یک نمودار متراکم نباشد (تعداد لبه های کمی داشته باشد) فضای بسیار کارآمدتر است.
مشکل این است که درک لیست مجاورت در مقایسه با ماتریس مجاورت سخت تر است، بنابراین اگر قبلاً آنها را تفسیر نکرده اید، با دقت دنبال کنید:
اولین چیزی که برای ایجاد یک لیست مجاورت باید بدانید تعداد گره ها در یک نمودار است. در نمودار مثال ما، 5 گره وجود دارد، بنابراین 5 مکان اول در لیست، آن گره ها را نشان می دهد – به عنوان مثال عنصر با شاخص 1
نشان دهنده a node 1
. پس از رزرو 5 مکان اول یک لیست، می توانید شروع به پر کردن لیست کنید. ارزش روی شاخص i
به نمایه ای در لیست اشاره می کند که در آن می توانید شاخص های گره های مجاور را پیدا کنید node i
.
به عنوان مثال، ارزش روی شاخص 0
است 5
، به این معنی که باید به شاخص نگاه کنید 5
در لیست مجاورت برای پیدا کردن گره هایی که به آن متصل هستند node 0
– این گره ها هستند 0
، 1
، و 2
. اما چگونه متوجه شدیم که چه زمانی جستجوی گره های مجاور را متوقف کنیم؟ خیلی ساده است! به ارزش نگاه کنید روی شاخص در کنار 0
در لیست شاخص بعدی است 1
، نشان دهنده آن است node 1
، و ارزش آن است 8
، به این معنی که می توانید گره های مجاور را پیدا کنید node 1
با شروع از شاخص 8
در لیست مجاورت بنابراین، می توانید گره های مجاور را پیدا کنید node 0
به عنوان مقادیر لیست بین شاخص ها 5
و 8
.
برای درک آسانتر این ساختار، میتوانید عناصر فهرست مجاورت را به روشی ساختاریافتهتر دوباره ترتیب دهید. اگر این کار را انجام دهید، می بینید که ساختار به دست آمده بسیار شبیه یک لیست پیوندی است:
علاوه بر این، ساختار لیست پیوندی بسیار شبیه است روی لغت نامه ها (یا نقشه ها). دارای مجموعه ای از کلیدها – گره ها، و مجموعه ای از ارزش های برای هر کلید – مجموعه ای از گره ها در مجاورت کلید node. اگر می خواهید نمودار وزنی را نشان دهید، باید راهی برای ذخیره وزن علاوه بر نمودار مجاور پیدا کنید node (همانطور که در تصویر زیر می بینید). اما جزئیات پیاده سازی را در بخش های بعدی پوشش خواهیم داد.
تصویر زیر لیست مجاورت نمودار مثال را به شما نشان می دهد – هم با وزن و هم بدون وزن:
وقتی به لیست وزنی مجاور نگاه می کنید، می توانید به راحتی مجموعه ای از یال های نمودار مثال را بسازید. گره 0
دارای سه گره مجاور – 0
، 1
، 2
، به این معنی که نمودار دارای لبه است 0-0
، 0-1
، و 0-2
. وزن آن لبه ها را نیز می توان از لیست مجاورت خواند. وزن لبه 0-0
است 25
، وزن لبه 0-1
است 5
، و غیره روی، برای هر یال در نمودار.
طرفداران:
- ارزان برای یافتن گره های مجاور انتخاب شده node –
O(1)
- کارآمد برای نمودارهای کم تراکم (تعداد لبه ها در مقایسه با تعداد گره ها)
- می توانید از آن برای هر دو گره با حروف و عدد استفاده کنید
- هزینه پایین عبور از یک نمودار –
O(length_of_list)
- هزینه پایین برچسب زدن/شمارش لبه ها –
O(length_of_list)
معایب:
- زمان مراجعه بالا –
O(length_of_list)
- هزینه بالای برداشتن لبه –
O(length_of_list)
(توسعه منطقی زمان مراجعه بالا)
توجه داشته باشید: این length_of_list
برابر است با مجموع از تعداد گره ها و تعداد لبه ها در یک نمودار
روش پیاده سازی گراف در پایتون
اکنون می دانید که چگونه یک نمودار را با رایج ترین ساختارهای داده نمایش دهید! کار بعدی پیاده سازی این ساختارهای داده در پایتون است. هدف این راهنما این است که تا جایی که ممکن است یک نمودار جهانی را به شما ارائه دهد، اما همچنان آن را سبک کند. این چیزی است که به شما امکان می دهد تمرکز کنید روی پیاده سازی الگوریتم های گراف به جای گراف به عنوان ساختار داده. در حالت ایده آل، شما یک کلاس لفاف نشان دهنده یک ساختار داده گراف است که می توانید از آن برای بسته بندی هر روش الگوریتم نموداری که می خواهید بعداً پیاده سازی کنید استفاده کنید.
توجه داشته باشید: پیادهسازیهای سادهای که در این راهنما ایجاد میکنیم باید شما را در تمام موارد استفاده غیرخاصی پوشش دهد. به عنوان مثال، فرض می کنیم که تمام گره ها با اعدادی که از صفر شروع می شوند برچسب گذاری می شوند. اما اگر نیاز دارید پیاده سازی های جامع تر، ما شما را تحت پوشش قرار دادیم! شما می توانید پیاده سازی های کامل را در مخزن GitHub زیر.
این Graph
class نمایش گراف و همچنین سایر روشهایی را که ممکن است برای دستکاری یک نمودار به آن نیاز داشته باشید، ذخیره میکند. بیایید نگاهی به ساختار کلی آن بیندازیم و پس از آن به اجرای آن بپردازیم:
class Graph:
همانطور که می بینید، مثلاً چندین “بخش” وجود دارد که باید در a پیاده سازی کنید Graph
کلاس مهمترین بخش و بخش مورد نظر ما روی در این بخش است بخش سازنده. اینجاست که باید اجرای نمودار خود را (نمایش ساختار داده) قرار دهید. پس از آن ، می توانید هر الگوریتم مربوط به گراف را به عنوان روشی در این کلاس پیاده سازی کنید. از طرف دیگر ، شما می توانید هر الگوریتم گرافیک/جستجوی نمودار را به عنوان یک روش مستقل پیاده سازی کنید و در خود نمودار عبور کنید. تفاوت این است که کاملاً به معنای واقعی کلمه ، فقط در مورد ارجاع الگوریتم self
(گراف والد) یا پاس شده در graph
.
بیایید نگاهی به روش پیاده سازی هر یک از نمودارهای ذکر شده در آن بیاندازیم Graph
کلاس در این بخش ، ما از نمودار نمونه قبلی برای آزمایش هر اجرای استفاده خواهیم کرد:
روش پیاده سازی لیست لبه ها در پایتون
همانطور که قبلاً بیان کردیم ، لیستی از لبه ها برنامه های زیادی در دنیای واقعی ندارند ، اما اغلب برای اهداف مصور استفاده می شود. شما می توانید در صورت نیاز به اجرای ساده نمودار که به طور غیر ضروری اجرای الگوریتم را پیچیده نمی کند ، از آن استفاده کنید.
بیایید نگاهی به اجرای Graph
کلاس که از لیستی از لبه ها برای نشان دادن نمودار استفاده می کند:
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_directed = directed
self.m_list_of_edges = ()
def add_edge(self, node1, node2, weight=1):
self.m_list_of_edges.append((node1, node2, weight))
if not self.m_directed:
self.m_list_of_edges.append((node1, node2, weight))
def print_edge_list(self):
num_of_edges = len(self.m_list_of_edges)
for i in range(num_of_edges):
print("edge ", i+1, ": ", self.m_list_of_edges(i))
همانطور که مشاهده می کنید ، این اجرای بسیار ساده است. نمودار به عنوان لیستی از لبه ها نشان داده شده است ، جایی که هر لبه توسط یک لیست به روش زیر نشان داده می شود: (node1, node2, weight)
. بنابراین، یک نمودار در واقع یک ماتریس است که در آن هر سطر نشان دهنده یک یال است.
بیایید نمودار مثال خود را ایجاد کنیم و ببینیم لیست لبه ها چگونه آن را ذخیره می کند.
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
اول از همه ، نمودار مثال دارای 5 گره است ، بنابراین شما یک نمودار با 5 گره با استفاده از سازنده ایجاد می کنید. سپس تمام لبه ها را به نمودار ایجاد شده اضافه می کنید و print نمودار که خروجی زیر را خواهد داشت:
edge 1 : (0, 0, 25)
edge 2 : (0, 1, 5)
edge 3 : (0, 2, 3)
edge 4 : (1, 3, 1)
edge 5 : (1, 4, 15)
edge 6 : (4, 2, 7)
edge 7 : (4, 3, 11)
همانطور که می بینید، این خروجی مطابق با لیست مثالی از لبه ها است که در بخش های قبلی نشان داده ایم:
توجه داشته باشید: اگر میخواهید این نمودار را بدون جهت بسازید، باید سازنده را به روش زیر انجام دهید: graph = Graph(5, directed=False)
.
روش پیاده سازی ماتریس مجاورت در پایتون
یک ماتریس مجاورت اساساً ساده است nxn
ماتریس، جایی که n
تعداد گره های یک گراف است. بنابراین، ما آن را به عنوان ماتریس با پیاده سازی می کنیم num_of_nodes
ردیف ها و ستون ها ما از a استفاده خواهیم کرد درک لیست برای ساخت آن و مقداردهی اولیه تمام فیلدها به 0
.
در این مورد، 0
یک مقدار ویژه است که به این واقعیت اشاره دارد که در ابتدا هیچ یال در نمودار وجود ندارد. افزودن لبه ها بسیار ساده است، فقط باید فیلد مناسب ماتریس را با آن علامت گذاری کنیم 1
یا weight
بسته به روی آیا یک نمودار وزن دارد یا نه:
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_directed = directed
self.m_adj_matrix = ((0 for column in range(num_of_nodes))
for row in range(num_of_nodes))
def add_edge(self, node1, node2, weight=1):
self.m_adj_matrix(node1)(node2) = weight
if not self.m_directed:
self.m_adj_matrix(node2)(node1) = weight
def print_adj_matrix(self):
print(self.m_adj_matrix)
حالا بیایید این پیاده سازی را به روشی که قبلا توضیح داده شد آزمایش کنیم:
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
با اجرای کد بالا خروجی زیر به دست می آید:
(25, 5, 3, 0, 0)
(0, 0, 0, 1, 15)
(0, 0, 0, 0, 0)
(0, 0, 0, 0, 0)
(0, 0, 7, 11, 0)
همانطور که انتظار می رود، خروجی همان ماتریسی است که در بخش های قبلی نشان داده ایم:
توجه داشته باشید: اگر میخواهید این نمودار را بدون جهت بسازید، باید سازنده را به شکل زیر انجام دهید: graph = Graph(5, directed=False)
. در آن صورت، ماتریس مجاورت متقارن خواهد بود.
روش پیاده سازی لیست مجاورت در پایتون
همانطور که در بخش های قبلی توضیح دادیم، بهترین راه برای نمایش لیست مجاورت در پایتون استفاده از یک فرهنگ لغت – مجموعه ای از کلیدها و مربوطه ارزش های.
برای هر کدام یک کلید ایجاد می کنیم nodeو مجموعه ای از گره های مجاور برای هر کلید. به این ترتیب، ما به طور موثر برای هر یک مجموعه ای از گره های مجاور ایجاد خواهیم کرد node در یک نمودار در اصل ، مجاور node لبه بین کلید را نشان می دهد node و مجاور nodeبنابراین باید به هر یال وزنی اختصاص دهیم. به همین دلیل است که ما هر مجاور را نشان خواهیم داد node به عنوان یک چندتایی – یک جفت از نام مجاور node و وزن آن لبه:
class Graph:
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
self.m_directed = directed
self.m_adj_list = {node: set() for node in self.m_nodes}
def add_edge(self, node1, node2, weight=1):
self.m_adj_list(node1).add((node2, weight))
if not self.m_directed:
self.m_adj_list(node2).add((node1, weight))
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list(key))
دوباره، بیایید پیادهسازی را به روشی که قبلا توضیح داده شد آزمایش کنیم:
graph = Graph(5)
graph.add_edge(0, 0, 25)
graph.add_edge(0, 1, 5)
graph.add_edge(0, 2, 3)
graph.add_edge(1, 3, 1)
graph.add_edge(1, 4, 15)
graph.add_edge(4, 2, 7)
graph.add_edge(4, 3, 11)
graph.print_edge_list()
خروجی مشابه لیست پیوندی است که در بخش های قبلی توضیح داده شد:
node 0 : {(2, 3), (0, 25), (1, 5)}
node 1 : {(3, 1), (4, 15)}
node 2 : set()
node 3 : set()
node 4 : {(2, 7), (3, 11)}
توجه داشته باشید: اگر میخواهید این نمودار را بدون جهت بسازید، باید سازنده را به شکل زیر انجام دهید: graph = Graph(5, directed=False)
.
نتیجه
پس از خواندن این درس، ممکن است از خود بپرسید – در نهایت از چه نمایش نموداری باید استفاده کنم؟ اما پاسخ، طبق معمول، ساده نیست – بستگی دارد
هر نمایش گراف مزایا و معایب خود را دارد – در یک مورد استفاده میدرخشد، اما در موارد دیگر عملکرد پایینی دارد. به همین دلیل است که ما یک نمای کلی از نمایش گراف ها به شما ارائه کرده ایم. پس از خواندن این راهنما، باید درک شهودی از نمایش گراف ها داشته باشید، بدانید که چگونه هر یک از آنها را پیاده سازی کنید و چه زمانی از هر یک از آنها استفاده کنید. روی یک لیست مفید از مزایا و معایب بنابراین، اگر میخواهید در پیادهسازی الگوریتمهای مرتبط با گراف عمیقتر شوید، این راهنما باید نقطه شروع خوبی باشد.
منتشر شده در 1403-01-06 18:36:03