الگوریتم گابو
الگوریتم چریَن- ملورن/ گابو در نظریه گراف، یک روش با پیچیدگی زمانی خطی برای یافتن مولفههای همبندی قوی در یک گراف جهتدار است [۱] . این الگوریتم در سال ۱۹۹۶ توسط جوزف چِریَن و
کورت ملورن[۲] ارائه شد و در سال 1999 توسط هارولد گابو[۳] بهبود یافت.
الگوریتم گابو همانند الگوریتم مولفههای همبند قوی تارجان، تنها یک جستجوی عمق اول در گراف داده شده انجام میدهد، و از یک پشته برای نگهداری گرههایی که
به مولفهای اختصاص داده نشدهاند استفاده میکند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گرهها را به یک مولفهی جدید منتقل میکند.
الگوریتم تارجان از یک آرایه با اندیس گرهها شامل اعداد پیشترتیب استفاده میکند، که به ترتیب دیده شدن در جستجوی عمق اول مقداردهی شدهاند.
از آرایهی پیشترتیبی برای دانستن اینکه چه زمانی مولفهی همبندی جدید ایجا شود استفاده میگردد. الگوریتم گابو به جای استفاده از آرایه، از پشتهی دیگری به این منظور استفاده میکند.
الگوریتم گابو [ویرایش]
الگوریتم گابو با پشتیبانی دو پشتهی S و P یک جستجوی عمق اول بر روی گراف داده شدهی G انجام میدهد. پشتهی S تمامی گرههایی را تاکنون به یک مولفهی همبندی قوی
اختصاص داده نشدهاند، شامل میشود. گرهها در این پشته به ترتیبی که جستجوی عمق اول به آن میرسد قرار دارند. پشتهی P شامل گرههایی است که هنوز اختصاص آنها به مولفههای همبندی
قوی متفاوت از هم، تعیین نشده است. همچنین در الگوریتم از یک شمارندهی C که تعداد گرههای مشاهده شده تاکنون است، برای محاسبهی اعداد پیشترتیب گرهها استفاده میشود.
هنگامی که جستجوی عمق اول به یک گره v میرسد، الگوریتم مراحل زیر را به ترتیب انجام میدهد:
- عدد پیشترتیب v را برابر C قرار میدهد، و مقدار C را یکی افزایش میدهد.
- گره v را در پشتهی S و همینطور P قرار میدهد.
- برای هر یال از گره v به گره مجاور w :
- اگر عدد پیشترتیب w هنوز مقداردهی نشده، به طور بازگشتی جستجو را روی w انجام میدهد؛
- در غیر اینصورت، اگر w هنوز به یک مولفهی همبندی قوی اختصاص داده نشده:
- تا زمانی که عدد پیشترتیب عنصر بالای پشته P، بزرگتر اکید عدد پیشترتیب w است، عنصر بالای P را خارج میکند.
- اگر v عنصر بالای P بود:
- عناصر بالای S را تا زمانی که v خارج شود، خارج کرده و این عناصر را به یک مولفهی همبندی اختصاص میدهد.
- گره v را از P خارج میکند.
الگوریتم کلی شامل یک حلقه روی گرههای گراف G است، که این جستجوی بازگشتی را برای گرههایی که هنوز عدد پیشترتیب آنها مقدار دهی نشده است، صدا میزند.
منابع [ویرایش]
- ↑ Sedgewick, R., "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms year = 2004 (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216
- ↑ Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica 15: 521–549, DOI:10.1007/BF01940880
- ↑ Gabow, H.N. (2003), "Searching (Ch 10.1)", in Gross, J. L.; Yellen, J., Discrete Math. and its Applications: Handbook of Graph Theory, 25, CRC Press, pp. 953–984
- ↑ Sedgewick, R., "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms year = 2004 (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216
- ↑ Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica 15: 521–549, DOI:10.1007/BF01940880
- ↑ Gabow, H.N. (2003), "Searching (Ch 10.1)", in Gross, J. L.; Yellen, J., Discrete Math. and its Applications: Handbook of Graph Theory, 25, CRC Press, pp. 953–984
