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

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

داده‌ها را در ساختار گراف می‌توان به صورت یک مجموعه از گره‌ها و یال‌ها تصور کرد. گره‌ها (نیز معروف به راس‌ها) نقاط داده‌ای هستند که با یکدیگر با یال‌ها (نیز معروف به لبه‌ها) متصل می‌شوند. گراف‌ها به صورت غیرجهت دار (undirected) و یا جهت‌دار (directed) می‌توانند باشند. در گراف‌های جهت‌دار، یال‌ها جهت مشخصی دارند و معمولاً به عنوان ترتیب یا جریان در داده‌ها مورد استفاده قرار می‌گیرند.

در یک گراف جهت دار ، یال ها یک طرفه هستند. به عنوان مثال، با جفت (۰،۱)، به این معنی است که یک یال از راس ۰ به سمت راس ۱ وجود دارد و تنها راه عبور از ۰ به ۱ است.

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

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

در این مثال، یک کلاس به نام Graph ایجاد شده است. این کلاس دو آرایه برای نگهداری گره‌ها و یال‌ها دارد. سپس متدهایی برای افزودن گره، افزودن یال و چاپ گراف تعریف شده است. در نهایت، یک نمونه از این کلاس ایجاد می‌شود و گره‌ها و یال‌ها به آن اضافه می‌شوند. سپس با استفاده از متد printGraph()، گراف چاپ می‌شود.

اجرای این کد، خروجی زیر را تولید می‌کند:

A -> B
B -> C
C -> D

این خروجی نشان می‌دهد که گره‌ها به ترتیب A، B، C و D قرار دارند و بین آن‌ها روابط جهت‌دار وجود دارد.

.

در کدی که در آموزش قبلی ارائه شد، کلمه کلیدی this برای ارجاع به متغیرها و روش‌های کلاس Graph استفاده می‌شود. به صورت خلاصه، this به معنای ارجاع به موجودیت فعلی (در این حالت، شیء myGraph) است.

در زیر، توضیحی درباره استفاده از this در کدهای قبلی ارائه شده است:

در این کد، this به myGraph ارجاع می‌دهد. بنابراین، وقتی از روش‌ها و متغیرهای کلاس Graph استفاده می‌شود، this به myGraph اشاره می‌کند. به عنوان مثال، this.nodes.push(node); به معنای اضافه کردن node به آرایه nodes در myGraph است.

برای استفاده صحیح از this، باید کدها را در محدوده مناسبی قرار دهید. در مثال بالا، this درون تعریف کلاس Graph استفاده شده است، بنابراین محدوده صحیح برای استفاده از this نیز درون کلاس قرار دارد.


الگوریتم های پیمایش گراف (نمودار)

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

دو تکنیک اساسی برای پیمایش گراف عبارتند از:

  • جستجوی پهنای اول Breadth-First Search (BFS): الگوریتم BFS به طور گسترده رشد می کند. تمام گره ها در یک سطح مشخص قبل از حرکت به سطح بعدی پیمایش می شوند. این گسترش سطح عاقلانه تضمین می کند که برای هر رأس شروع، شما می توانید به همه سطوح دیگر در یک زمان برسید. استراتژی جستجوی سطح اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی سطح به سطح گراف» است.
  • جستجوی عمق اول Depth-First Search (DFS): این الگوریتم برعکس BFS است. از نظر عمقی رشد می کند. با شروع از هر گره، به یک گره مجاور حرکت می کنیم تا به دورترین سطح برسیم. سپس به نقطه شروع برمی گردیم و گره مجاور دیگری را انتخاب می کنیم. یک بار دیگر به دورترین سطح کاوش می کنیم و به عقب برمی گردیم. این روند تا زمانی که تمام گره ها بازدید شوند ادامه می یابد.  روش جستجوی عمق اول برای پیمایش گراف، همان‌طور که از نامش پیداست «جستجوی رأس‌های عمیق‌تر در گراف تا زمانی که امکان دارد» است.

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

گراف ها برای حل مسائل زندگی واقعی که شامل نمایش فضای مشکل به عنوان یک شبکه است استفاده می شود. هر برنامه مرتبط با شبکه (مسیرها، یافتن روابط، مسیریابی، و غیره) مفهوم گراف را اعمال می کند. بنابراین، ساختار داده گراف نقش اساسی در چندین برنامه ایفا می کند:

  • جی پی اس
  • شبکه های عصبی
  • شبکه های همتا به همتا
  • خزنده های موتورهای جستجو
  • جمع آوری زباله
  • وب سایت های شبکه های اجتماعی
  • و بیشتر

به عنوان مثال، یک کاربر در فیس بوک می تواند به عنوان یک گره (راس) نمایش داده شود، در حالی که ارتباط آنها با دیگران می تواند به عنوان یک لبه بین گره ها نمایش داده شود، و هر گره می تواند ساختاری باشد که حاوی اطلاعاتی مانند شناسه، نام، مکان کاربر است. ، و غیره.

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

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

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *