موضوع مقاله: الگوریتم مؤلفه قوی مبتنی بر مسیر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم مؤلفه قوی مبتنی بر مسیر | مقدمه: الگوریتم مؤلفه قوی مبتنی بر مسیر در نظریه گراف برای پیدا کردن مولفه‌های قویا همبند یک گراف جهت‌دار استفاده می‌شود. | ## بخش 1: الگوریتم مؤلفه قوی مبتنی بر مسیر | قبل از این الگوریتم، الگوریتم کساراجو و الگوریتم تارژان نیز به همین منظور ارائه شده‌است. مفاهیم گراف قویا همبند به گراف جهت‌داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. در این الگوریتم رأس‌های گراف را از ۱ تا n و مؤلفه‌های قویا همبند را با شروع از n+۱ شماره‌گذاری می‌کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می‌باشد در نظر می‌گیریم و در این گراف مسیر P را به صورت زیر می‌سازیم: ابتدا یک رأس دلخواه از گراف را در نظر می‌گیریم و از این رأس در جهت کاملاً دلخواه حرکت می‌کنیم تا یکی از دو حالت زیر رخ دهد: اگر به رأسی رسیدیم که قبلاً در مسیر P وجود داشت، تمام گره‌های بین این رأس که تاکنون پیموده شده‌است را هم در گراف H و هم در مسیر p منقبض می‌کنیم. اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مؤلفه قویا همبند معرفی می‌کنیم. این الگوریتم از الگوریتم جستجوی عمق اول و همچنین دو پشته برای نمایش مسیر P استفاده می‌کند. پشته S که شامل دنباله رأس‌های مسیر P است و پشته B که شامل کران‌های رأس‌های منقبض شده‌است. | ## بخش 2: الگوریتم مؤلفه قوی مبتنی بر مسیر | در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مؤلفه قویا همبند را ذخیره می‌کند. به عبارت دقیق تر این ارائه به صورت زیر تعریف می‌شود: I[v]=۰ هرگاه گره v در مسیر P نباشد. الگوریتم‌های مرتبط برای دیدن الگوریتم‌های مرتبط با این الگوریتم می‌توانید به الگوریتم کساراجو و الگوریتم مؤلفه‌های همبند قوی تارجان مراجعه کنید. الگوریتم گابو الگوریتم چریَن- ملورن/ گابو در نظریه گراف، یک روش با پیچیدگی زمانی خطی برای یافتن مؤلفه‌های همبندی قوی در یک گراف جهتدار است . این الگوریتم در سال ۱۹۹۶ توسط جوزف چِریَن وکورت ملورن ارائه شد و در سال ۱۹۹۹ توسط هارولد گابو بهبود یافت. الگوریتم گابو همانند الگوریتم مؤلفه‌های همبند قوی تارجان، تنها یک جستجوی عمق اول در گراف داده شده انجام می‌دهد، و از یک پشته برای نگهداری گره‌هایی کهبه مؤلفه‌ای اختصاص داده نشده‌اند استفاده می‌کند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گره‌ها را به یک مؤلفهٔ جدید منتقل می‌کند.الگوریتم تارجان از یک آرایه با اندیس گره‌ها شامل اعداد پیش‌ترتیب استفاده می‌کند، که به ترتیب دیده شدن در جستجوی عمق اول مقداردهی شده‌اند.از آرایهٔ پیش‌ترتیبی برای دانستن اینکه چه زمانی مولفهٔ همبندی جدید ایجا شود استفاده می‌گردد. الگوریتم گابو به جای استفاده از آرایه، از پشتهٔ دیگری به این منظور استفاده می‌کند. | ## بخش 3: الگوریتم مؤلفه قوی مبتنی بر مسیر | الگوریتم گابو با پشتیبانی دو پشتهٔ S و P یک جستجوی عمق اول بر روی گراف داده شدهٔ G انجام می‌دهد. پشتهٔ S تمامی گره‌هایی را تاکنون به یک مؤلفهٔ همبندی قوی اختصاص داده نشده‌اند، شامل می‌شود. پشتهٔ P شامل گره‌هایی است که هنوز اختصاص آن‌ها به مولفه‌های همبندیقوی متفاوت از هم، تعیین نشده‌است. همچنین در الگوریتم از یک شمارندهٔ C که تعداد گره‌های مشاهده شده تاکنون است، برای محاسبهٔ اعداد پیش‌ترتیب گره‌ها استفاده می‌شود. هنگامی که جستجوی عمق اول به یک گره v می‌رسد، الگوریتم مراحل زیر را به ترتیب انجام می‌دهد: عدد پیش‌ترتیب v را برابر C قرار می‌دهد، و مقدار C را یکی افزایش می‌دهد. برای هر یال از گره v به گره مجاور w: اگر عدد پیش‌ترتیب w هنوز مقداردهی نشده، به‌طور بازگشتی جستجو را روی w انجام می‌دهد؛ در غیر اینصورت، اگر w هنوز به یک مؤلفهٔ همبندی قوی اختصاص داده نشده: تا زمانی که عدد پیش‌ترتیب عنصر بالای پشته P، بزرگتر اکید عدد پیش‌ترتیب w است، عنصر بالای P را خارج می‌کند. اگر v عنصر بالای P بود: عناصر بالای S را تا زمانی که v خارج شود، خارج کرده و این عناصر را به یک مؤلفهٔ همبندی اختصاص می‌دهد. | ## جمع‌بندی | الگوریتم کلی شامل یک حلقه روی گره‌های گراف G است، که این جستجوی بازگشتی را برای گره‌هایی که هنوز عدد پیش‌ترتیب آن‌ها مقدار دهی نشده‌است، صدا می‌زند.