تشخیص چرخه مشخص میکند آیا میتوان از یک مسیر دوباره به نقطهای از همان مسیر برگشت. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Cycle Detection زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
در گراف جهتدار معمولاً سه حالت unvisited، visiting و visited نگه میداریم.
مراحل اجرا
- برای هر رأس state نگه میداریم.
- هنگام ورود آن را visiting میکنیم.
- رسیدن به visiting یعنی cycle.
- پس از پایان بررسی، state را visited میکنیم.
نمونه کد JavaScript
function hasCycle(graph) {
const state = new Map();
function dfs(u) {
if (state.get(u) === 1) return true;
if (state.get(u) === 2) return false;
state.set(u, 1);
for (const v of graph[u] ?? []) if (dfs(v)) return true;
state.set(u, 2); return false;
}
return Object.keys(graph).some(dfs);
}مثالهای واقعی و دنیای کار
- Circular Dependency
- Workflow بینهایت
- Dependency بین Packageها
- اعتبارسنجی DAG
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
تشخیص dependency و loop ناسالم
چه زمانی مناسب نیست؟
برای reachability ساده، BFS/DFS معمولی کافی است.
جمعبندی
Cycle Detection را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.