در این مطلب، برنامه تشخیص درخت بودن یک گراف در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «پایتون» (Python) و «جاوا» (Java) ارائه شده است. در واقع، هدف نوشتن تابعی است که یک گراف بدون جهت را دریافت کرده و بررسی کند که آیا درخت است یا نه. در صورتی که گراف یک درخت بود «مقدار یک» و در غیر این صورت، «مقدار صفر» را بازگرداند. برای مثال، گراف زیر یک درخت است.

برنامه تشخیص درخت بودن یک گراف -- راهنمای کاربردی

اما، گراف زیر یک درخت نیست.

برنامه تشخیص درخت بودن یک گراف -- راهنمای کاربردی

یک گراف بدون جهت، در صورتی درخت است که مشخصات زیر را داشته باشد:

  1. هیچ دوری نداشته باشد.
  2. گراف هم‌بند باشد.

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

روش شناسایی دور در یک گراف بدون جهت

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

روش شناسایی هم‌بندی در یک گراف بدون جهت

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

برنامه تشخیص درخت بودن یک گراف در ++C

برنامه تشخیص درخت بودن یک گراف در جاوا

برنامه تشخیص درخت بودن یک گراف در پایتون

خروجی

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

الهام حصارکی (+)

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

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

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