گراف در پایتون – روش های پیاده سازی و نمایش به زبان ساده

گراف‌ها ساختار داده بسیار مهمی در علوم کامپیوتر هستند. این ساختارهای داده برای نمایش انواع شبکه‌ها - از شبکه‌های اجتماعی گرفته تا نقشه‌ جاده‌ها - مورد استفاده قرار می‌گیرند. در پایتون چندین روش مختلف برای پیاده‌سازی و نمایش گراف وجود دارد. برای مثال می‌توان به «ماتریس‌های مجاورت» (Adjacency Matrices)، «لیست‌های مجاورت» (Adjacency Lists) و روش نمایش شیء گرایانه اشاره کرد. یکی دیگر از رایج‌ترین روش‌های نمایش گراف در پایتون استفاده از دیکشنری‌ها برای نمایش رئوس و یال‌های آن است. استفاده از دیکشنری در پایتون برای رسم گراف‌هایی با اندازه کوچک و متوسط روشی ساده، کارآمد و مناسب است. روش مشهور دیگر، استفاده از کتابخانه قدرتمند NetworkX در پایتون است که برای ساخت، استفاده و تصویرکردن گراف‌ها به کار برده می‌‌شود.

کتابخانه NetworkX، تعداد زیادی تابع و الگوریتم «درونی» (Built-In) برای تحلیل و مصورسازی گراف‌ها فراهم کرده است. با کمک این کتابخانه می‌توان گراف‌های بزرگ و پیچیده را به شکل موثری مدیریت کرد. روی‌هم‌رفته، استفاده از گراف در پایتون روشی بسیار کارآمد و انعطاف‌پذیر را برای نمایش و تحلیل هر نوع شبکه‌ای فراهم می‌کند. به همین دلیل در این مطلب از مجله فرادرس چند روش متفاوت پیاده‌سازی و نمایش گراف را به زبان ساده بیان کرده‌ایم. این روش‌ها شامل «ماتریس‌های مجاورت»، «لیست‌های مجاورت»، روش نمایش «شیءگرایانه» و غیره می‌شوند.

گراف در پایتون چیست؟

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

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

آموزش های حرفه ای پایتون در فرادرس

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

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

• فیلم آموزش پردازش موازی در پایتون همراه با کار با کتابخانه Thread و Async IO با فرادرس
• فیلم آموزش پایچارم PyCharm برای برنامه‌ نویسی پایتون همراه با نصب و انجام پروژه کامل در فرادرس
• فیلم آموزش برنامه نویسی پایتون پیشرفته، ترفندهای Python در فرادرس
• فیلم آموزش کتابخانه های NumPy و Matplotlib در پایتون با فرادرس
• فیلم آموزش کاربرد ChatGPT در برنامه نویسی پایتون از فرادرس

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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]
]

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

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

نمایش شی گرایانه

نمایش شیء‌گرایانه گراف‌ها به پیاده‌سازی گراف بر اساس کلاس‌ در پایتون گفته می‌‌شود. این روش پیاده‌سازی، نمایش انتزاعی‌تری با قابلیت استفاده دوباره از گراف‌ها را فراهم می‌کند. در این روش، هر گراف به عنوان مجموعه‌ای از رئوس و یال‌ها نمایش داده می‌شود. در این نمایش هر رأس برای خود شیئی با صفات اختصاصی خود است. به عنوان مثال می‌توان به صفاتی مانند شماره‌شناسایی «ID» و همسایه‌های آن رأس اشاره کرد.

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

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

یکی دیگر از روش‌های نمایش گراف استفاده از دیکشنری‌ها در پایتون است. برای نمایش این رویکرد از دو دیکشنری مختلف استفاده خواهیم کرد. یکی از این دیکشنری‌ها را به نام رأس‌ها یا vertices نام‌گذاری می‌کنیم و دیکشنری دیگر را به نام edges. در دیکشنری رأس، کلید برای نمایش رأس‌ها و مقادیر مربوط به آن‌ها همان یال‌ها هستند. در دیکشنری یال‌، کلید‌های نشان دهنده یال و مقدار مربوط به هر کلید هم نشان‌دهنده رأس‌هایی است که هر یال به یکدیگر متصل می‌کند.

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

      0
      / \
     1---2
      \ /
       3

اکنون گراف بالا را با استفاده از هر دو دیکشنری «یال‌ها» (Edges) و «رأس‌ها» (Vertices) نمایش می‌دهیم.

در کدهای بالا، کلید‌های دیکشنری رأس‌ها vertices نشان‌دهنده تمام رأس‌های گراف و مقدار مربوط به هر کلید هم رأس‌های مجاور آن را نشان می‌دهند. کلید‌های موجود در دیکشنری یال‌ها edges نشان‌دهنده یال‌های گراف و مقدار‌های مربوط به هر کلید هم نشان‌دهنده رأس‌هایی است که آن یال بهم متصل کرده است. به یاد داشته باشید که از SET در پایتون برای نمایش یال‌ها استفاده کنید. این کار باعث می‌شود که هیچ یالی به صورت اشباهی، تکرار نشود.

برای اضافه کردن رأس جدید به گراف، به سادگی می‌توانیم جفت کلید-مقداری را به دیکشنری رأس‌ها اضافه کنیم.

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

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

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

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

مثال اول: گراف بدون جهت

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

      0
      / \
     1---2
      \ /
       3

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

مثال دوم: گراف جهت دار

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

 0 --> 1 --> 2 --> 3
   |           |     |
   v           v     v
   4           5 --> 6

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

با کمک دیکشنری‌های پیاده‌سازی شده در پایین، گراف بالا را نمایش داده‌ایم.

مثال سوم: گراف وزن دار

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

      0
      / \
     1---2
      \ /
       3

در این مسئله، وزن همه یال‌ها از قرار زیر تایین شده‌اند.

• وزن یال بین رئوس ۰ و ۱ برابر با ۴ است.
• وزن یال بین رئوس ۰ و ۲ برابر با ۵ است.
• وزن یال بین رئوس ۱ و ۲ برابر با ۳ است.
• وزن یال بین رئوس ۱ و ۳ برابر با ۲ است.
• وزن یال بین رئوس ۲ و ۳ برابر با ۶ است.

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

در کدهای بالا، مقادیر مربوط به کلید‌ها در دیکشنری vertices  به شکل تاپل در پایتون هستند. در هر دو دیکشنری، کلید‌ها تمام رأس‌های گراف را نشان می‌دهند. در این تاپل‌ها عنصر اول، رأس مجاور را نشان می‌دهد و عنصر دوم، وزن یال متصل کننده آن‌ها را. مقادیر مربوط به هر کلید در دیکشنری edges هم به شکل تاپل نمایش داده می‌‌شوند. در این تاپل‌ها هم عنصر اول رأس مجاور را نشان می‌دهد و عنصر دوم، وزن‌ یال متصل کننده این رأس‌ها به هم است.

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

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

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

• کتابخانه NetworkX یکی از کتابخانه‌های اوپن سورس در زبان برنامه‌نویسی پایتون است که برای تحلیل و مدل‌سازی گراف‌ها به کار می‌رود. برای آشنایی بیشتر با این کتابخانه پیشنهاد می‌کنیم که فیلم آموزش گراف کاوی و تحلیل شبکه ها در پایتون با NetworkX را از فرادرس مشاهده کنید. در پایین نیز لینک مربوط به این فیلم را قرار داده‌ایم.

• گراف کامل به گرافی می‌گویند که دارای «n» رأس بوده و درجه هر رأس - تعداد یال‌های متصل به آن - برابر با «n-1» است. به عبارت دیگر، در گراف کامل هر رأس به تمام رأس‌های دیگر متصل شده است.

برای مثال، شکل نمایش داده شده در پایین از نوع گراف کامل با ۶ رأس است.

گراف کامل چیست؟

«گراف کامل» (Complete Graph) به گرافی می‌گویند که تمام رأس‌های آن به دیگر رأس‌های گراف متصل باشد. تمام مشخصات مربوط به گراف کامل را در فهرست پایین ارائه کرده‌ایم.

• در گراف کامل درجه هر رأس برابر با «n-1» است.
• تعداد کل رأس‌ها برابر با «n(n-1)/2» است.
• همه یال‌های ممکن در «گراف ساده» (Simple Graph)، در گراف کامل وجود دارند.
• این گراف از نوع «گراف‌های دوری» (Cyclic Graph) یا چرخشی است.
• در این گراف بیشترین فاصله بین هر جفت از گره‌ها برابر با «۱» است.
• از آنجا که در این گراف هر گره‌ای به بقیه گره‌ها متصل شده، «عدد فامی» (Chromatic Number) برابر با n است.
• مکمل این گراف، گراف خالی است.

در این بخش از مطلب، برای ایجاد گراف کامل از ماژول NetworkX در پایتون استفاده می‌کنیم. به همین منظور باید از تابع درونی networkx.complete_graph()  برای ایجاد و تابع درونی networkx.draw()  برای رسم گراف استفاده کنیم. این کتابخانه در پایتون به طور خاص برای به تصویر کشیدن و تحلیل انواع مختلفی از گراف به کار برده می‌شود.

سینتکس رسم گراف در پایتون

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

networkx.complete_graph(n)

در سینتکس بالا تنها پارامتر مورد استفاده «n» است. پارامتر n تعداد گره‌های گراف را تعیین می‌کند. این گراف در خروجی شیء گراف کاملی با n گره را برمی‌گرداند. تمام گره‌های گراف از شماره «۰» تا «n-1» شماره‌گذاری شده‌اند.

اما برای رسم گراف به منظور مشاهده توسط کاربر، شیء ایجاد شده را باید به تابع networkx.draw()  ارسال کرد. سینتکس خام این تابع را در کادر زیر نمایش داده‌ایم.

networkx.draw(G, node_size, node_color)

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

• G: این پارامتر به «شیء گراف کامل» ایجاد شده اشاره می‌کند.
• node_size: این پارامتر، اندازه گره‌ها را نشان می‌دهد.
• node_color: این پارامتر هم رنگی را نشان می‌دهد که گره‌ها باید با آن رسم شوند.

مثال های پیاده سازی گراف

فرایند ساخت گراف با کمک کتابخانه NetworkX بسیار ساده‌ است. اما لازم است که مراحل زیر را یک به یک و به صورت منظم طی کنیم.

1. در ابتدا باید ماژول networkx  را به محیط کدنویسی وارد کنیم.
2. سپس با استفاده از متد networkx.complete_graph(n)  شیء گراف با تعداد رأس مورد نظر خود را ایجاد می‌کنیم. در این متد n برابر با تعداد گره‌ها یا رأس‌های گراف است.
3. برای تصویر کردن گراف از متد networkx.draw(G, node_color = ’green’, node_size=1500) استفاده می‌کنیم. در این متد node_color  رنگ و node_size  اندازه گره‌های گراف را تعیین می‌کنند.

• توجه: مقادیر node_size=1500  و node_color = ’green’  اختیاری هستند و هر مقدار مجاز دیگری را می‌توان به این پارامتر‌ها اختصاص داد.

مثال اول پیاده سازی گراف

در مثال زیر گرافی را با تعداد ۶ رأس ساخته و با مشخصات node_size=1500  و node_color = ’green’  رسم کرده‌ایم.

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

تصویر بالا، مربوط به گرافی با ۶ رأس است. زیرا در تابع سازنده گراف complete_graph() عدد ۶ را به عنوان پارامتر ارسال کرده‌ بودیم.

مثال دوم پیاده سازی گراف

در مثال زیر گرافی را با تعداد ۱۰ رأس ساخته و با مشخصات node_size=1500  و node_color = 'pink'  رسم کرده‌ایم.

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

گراف بالا هنوز گراف کامل است و فقط رنگ و تعداد یال‌های آن تغییر کرده‌اند.

انواع آموزش های مربوط به رسم نمودار

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

• فیلم آموزش اف ایکس گراف، رسم نمودارهای ریاضی با FX Graph با فرادرس
• فیلم آموزش نرم افزار هوش تجاری Tableau برای رسم انواع نمودار با فرادرس
• فیلم آموزش ویزیو درباره طراحی انواع نمودار و دیاگرام با Microsoft Visio 2019 دوره مقدماتی در فرادرس
• فیلم آموزش نرم افزار Generic Mapping Tools درباره رسم نقشه های زمین شناسی و نمودارهای آماری با GMT در فرادرس
• فیلم آموزش رسم نمودارهای پیشرفته در اکسل با فرادرس

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

روش‌ های جست و جو گراف در پایتون

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

• «جست وجوی اول سطح» (Breadth-First Search | BFS)
• «جست‌وجوی اول عمق» (Depth-First Search | DFS)

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

جست و جوی اول سطح

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

روش کار الگورتیم BFS را در فهرست پایین به شکل مرتب و منظم بیان کرده‌ایم.

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

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

جست و جوی اول عمق

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

روش کار الگورتیم DFS را در فهرست پایین به شکل مرتب و منظم بیان کرده‌ایم.

1. در ابتدای کار، الگوریتم، پشته‌ای را ایجاد کرده و اولین گره را به آن وارد می‌کند.
2. سپس گره وارد شده را با عنوان گره ملاقات شده، علامت‌گذاری می‌کند.
3. بعد از آن گره‌ای را از پشته واکشی کرده و چاپ می‌کند.
4. سپس تمام گره‌های همسایگی آن را که ملاقات نشده‌اند، به صورت عمقی به پشته وارد می‌کند.
5. تمام گره‌هایی که اخیرا مشاهده شده‌اند را با عنوان گره بررسی شده علامت‌گذاری می‌کند.
6. تا زمانی که پشته خالی نشده، مراحل ۳ تا ۵ را تکرار می‌کند.

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

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

کاربردهای پیاده سازی گراف در پایتون در دنیای واقعی

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

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

• بیوانفورماتیک: زیست انفورماتیک یا «بیو انفورماتیک» (Bioinformatics) حوزه میان‌رشته‌ای است که از تکنیک‌های محاسباتی برای تحلیل داده‌‌های بیولوژیکی توسط کامپیوترها استفاده می‌‌کند. برای نمایش ساختار‌های بیولوژیکی پیچیده‌ای مانند «برهمکنش‌های پروتئینی» (Protein Interactions)، «شبکه‌های بیان ژن» (Gene Expression Networks) و «مسیر‌های متابولیک» (Metabolic Pathways) به صورت متداولی از گراف‌ها استفاده می‌شود. در این حوزه می‌توان از الگورتیم‌های گراف برای پیدا کردن الگو‌ها در داده‌های بیولوژیک، پیش‌بینی اهداف دارویی و توسعه درمان‌های جدید برای بیماری‌ها استفاده کرد.
• سیستم‌های توصیه‌گر: «سیستم‌های توصیه گر» (Recommendation Systems) در سازمان‌هایی مانند نتفلیکس، آمازون و یوتیوب برای پیشنهاد دادن محصولات، فیلم‌ها و ویدئو‌های مورد علاقه کاربران خود از پیاده‌سازی گراف‌ها استفاده می‌کنند. در سیستم‌های توصیه‌گر هر عنصر یا کالایی به عنوان گره و رابطه بین این عناصر مانند یال در نظر گرفته می‌شود. در چنین سیستم‌هایی می‌توان از الگوریتم‌های گراف برای شناسایی عناصر مشابه و پیشنهاد دادن‌ آن‌ها به کاربران استفاده کرد. این پیشنهادات معمولا بر اساس انتخاب‌های قبلی هر کاربر گزینش می‌شوند.
• موتورهای جست‌وجو: موتورهای جست‌وجویی مانند گوگل از پیاده‌سازی گراف‌ها برای نشان‌ دادن صفحات وب در اینترنت استفاده می‌کنند. هر صفحه وب در این ساختار به عنوان گره و لینک‌های بین آن صفحات مختلف به عنوان یال در نظر گرفته می‌شود. در این موارد، الگوریتم‌های گراف برای شناسایی مربوط‌ترین صفحات وب به کوئری جست‌وجوی داده شده و رده‌بندی آن‌ها بر اساس میزان ارتباط - وزن یال‌‌ها - به کار برده می‌‌شوند.

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

جمع‌بندی

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

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