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

در این مطلب، برنامه بررسی وجود دور در گراف بدون جهت در زبان‌های برنامه‌نویسی «سی‌پلاس‌پلاس» (++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 است.

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

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^