الگوریتم مؤلفه قوی مبتنی بر مسیر: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
قلی زادگان (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
{{بی منبع}}
=='''<big><big>الگوریتم گابو</big></big>'''==
'''الگوریتم چریَن- ملورن/ گابو''' در [[نظریه گراف]]، یک روش با [[پیچیدگی زمانی]] خطی برای یافتن مولفه‌های همبندی قوی در یک [[گراف جهتدار]] است
| last = Sedgewick | first = R.
| contribution = 19.8 Strong Components in Digraphs
| edition = 3rd
| location = Cambridge MA
| pages = 205–216
| publisher = Addison-Wesley
| title = Algorithms in Java, Part 5 – Graph Algorithms
year = 2004}}</ref>
. این الگوریتم در سال 1996 توسط جوزف چِریَن و{{سخ}} کورت ملورن<ref>{{citation
| last1 = Cheriyan | first1 = J.
| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn
| doi = 10.1007/BF01940880
| journal = [[Algorithmica]]
| pages = 521–549
| title = Algorithms for dense graphs and networks on the random access computer
| volume = 15
| year = 1996}}</ref> ارائه شد و در سال 1999 توسط هارولد گابو<ref>{{citation
| last = Gabow | first = H.N.
| contribution = Searching (Ch 10.1)
| editor1-last = Gross | editor1-first = J. L.
| editor2-last = Yellen | editor2-first = J.
| pages = 953–984
| publisher = CRC Press
| title = Discrete Math. and its Applications: Handbook of Graph Theory
| volume = 25
| year = 2003}}</ref> بهبود یافت.{{سخ}}
الگوریتم گابو همانند الگوریتم مولفه‌های همبند قوی تارجان، تنها یک [[جستجوی عمق اول]] در گراف داده شده انجام می‌دهد،
و از یک [[پشته]] برای نگهداری گره‌هایی که{{سخ}} به مولفه‌ای اختصاص داده نشده‌اند استفاده می‌کند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گره‌ها را به یک مولفه‌ی جدید منتقل می‌کند.{{سخ}}الگوریتم تارجان از یک آرایه با اندیس گره‌ها شامل اعداد پیش‌ترتیب استفاده می‌کند، که به ترتیب دیده شدن در جستجوی عمق اول مقدار‌دهی شده‌اند.{{سخ}}از آرایه‌ی پیش‌ترتیبی برای دانستن اینکه چه زمانی مولفه‌ی همبندی جدید ایجا شود استفاده می‌گردد. الگوریتم گابو به جای استفاده از آرایه، از پشته‌ی دیگری به این منظور استفاده می‌کند.
الگوریتم گابو با پشتیبانی دو پشته‌ی S و P یک جستجوی عمق اول بر روی گراف داده شده‌ی G انجام می‌دهد. پشته‌ی S تمامی گره‌هایی را تاکنون به یک مولفه‌ی همبندی قوی {{سخ}}
اختصاص داده نشده‌اند، شامل می‌شود. گره‌ها در این پشته به ترتیبی که جستجوی عمق اول به آن می‌رسد قرار دارند. پشته‌ی P شامل گره‌هایی است که هنوز اختصاص آن‌ها به
سطر ۲۴ ⟵ ۵۰:
الگوریتم کلی شامل یک حلقه روی گره‌های گراف G است، که این جستجوی بازگشتی را برای گره‌هایی که هنوز عدد پیش‌ترتیب آن‌ها مقدار دهی نشده است، صدا می‌زند.
==منابع:==
{{پانویس}}
<references />
| |||