در این مطلب، برنامه بررسی وجود دور در گراف بدون جهت در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++C)، «پایتون» (Python) و «جاوا» (Java) ارائه شده است. در ادامه، مساله تعریف و همراه با مثالی حل می‌شود. یک گراف بدون جهت داده شده است. هدف آن است که بررسی شود آیا دوری در گراف وجود دارد یا نه. برای مثال، گراف زیر دارای دور ۱-۲-۰-۱ است.

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

پیش از این، در مطلبی با عنوان «برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی»، روش پیدا کردن دور در گراف جهت دار مورد بررسی قرار گرفت. پیچیدگی زمانی الگوریتم مجموعه‌های مجزا برابر با (O(ELogV است. می‌توان همچون گراف جهت‌دار، از «جستجوی اول عمق» (Depth First Search | DFS) برای شناسایی دور در گراف‌های بدون جهت در زمان (O(V+E استفاده کرد. پیمایش گراف داده شده با استفاده از DFS انجام می‌شود. برای هر راس بازدید شده V، اگر راس همسایه u وجود دارد که پیش از این بازدید شده باشد و u والد v نباشد، دور در گراف وجود دارد. اگر چنین راس مجاوری برای هیچ راسی یافت نشود، گفته می‌شود که گراف فاقد دور است. فرض این رویکرد آن است که هیچ دو یال موازی بین دو راس وجود نداشته باشد.

برنامه بررسی وجود دور در گراف بدون جهت در ++C

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

برنامه بررسی وجود دور در گراف بدون جهت در پایتون

خروجی

Graph contains cycle
Graph doesn't contain cycle

پیچیدگی زمانی

برنامه، یک پیمایش ساده DFS را در گراف انجام می‌دهد و گراف با استفاده از لیست هم‌جواری نشان داده می‌شود. بنابراین، پیچیدگی زمانی از درجه (O(V+E است.

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

^^

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

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

بر اساس رای 2 نفر

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

نظر شما چیست؟

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