Bridge یالی است که حذف آن تعداد componentهای گراف را افزایش میدهد. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Bridges in Graphs زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
اگر subtree هیچ راه برگشتی به بالاتر از parent نداشته باشد، یال parent-child میتواند Bridge باشد.
مراحل اجرا
- DFS و discovery time ثبت میشود.
- low هر رأس محاسبه میشود.
- low از child به parent برمیگردد.
- اگر low[child] > disc[parent] باشد یال Bridge است.
نمونه کد JavaScript
// Tarjan idea: tree edge (u,v) is a bridge when low[v] > disc[u].
function isBridge(discU, lowV) {
return lowV > discU;
}مثالهای واقعی و دنیای کار
- لینک حیاتی دیتاسنتر
- جاده بحرانی بین مناطق
- لینک یکتای دو Zone
- تحلیل Redundancy
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
پیدا کردن ارتباطات بحرانی
چه زمانی مناسب نیست؟
برای رأس بحرانی Articulation Point مناسب است.
جمعبندی
Bridges in Graphs را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.