در مسئله Eulerian باید هر یال دقیقاً یک بار پیمایش شود. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Eulerian Path & Circuit زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
تمرکز این مسئله روی Edgeهاست. با شرایط درجه و الگوریتم Hierholzer مسیر یا دور اویلری ساخته میشود.
مراحل اجرا
- اتصال و درجه رأسها را بررسی میکنیم.
- از رأس مناسب شروع میکنیم.
- یالهای استفادهنشده را یکییکی مصرف میکنیم.
- چرخهها را با Hierholzer در مسیر اصلی ادغام میکنیم.
نمونه کد JavaScript
function eulerTrail(graph, start) {
const g = Object.fromEntries(Object.entries(graph).map(([k,v])=>[k,[...v]]));
const stack=[start], path=[];
while(stack.length){
const u=stack[stack.length-1];
if((g[u]??[]).length) stack.push(g[u].pop());
else path.push(stack.pop());
}
return path.reverse();
}مثالهای واقعی و دنیای کار
- پوشش خیابانها
- بازرسی لینکهای شبکه
- مسئله پلهای Königsberg
- Route Inspection
پیچیدگی زمانی و فضایی
O(E) با Hierholzer
چه زمانی استفاده کنیم؟
وقتی هر یال باید دقیقاً یک بار استفاده شود
چه زمانی مناسب نیست؟
اگر هر رأس یک بار باشد، مسئله Hamiltonian است.
جمعبندی
Eulerian Path & Circuit را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.