الگوریتم مؤلفه قوی مبتنی بر مسیر

الگوریتم مولفه قوی مبتنی بر مسیر در نظریه گراف برای پیدا کردن مولفه‌های قویا همبند یک گراف جهت‌دار استفاده می‌شود. قبل از این الگوریتم، الگوریتم کساراجو و الگوریتم تارژان نیز به همین منظور ارائه شده‌است.
مفاهیم
گراف قویا همبند
به گراف جهت‌داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد.
مانند شکل زیر:
گراف قویا همبند
مولفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه‌ای از راس‌ها گویند که قویا همبند هستند.
یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
مولفه‌های قویا همبند
الگوریتم
فرض کنید گراف G داده شده‌است. در این الگوریتم راس‌های گراف را از ۱ تا n و مولفه‌های قویا همبند را با شروع از n+۱ شماره‌گذاری می‌کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می‌باشد در نظر می‌گیریم و در این گراف مسیر P را به صورت زیر می‌سازیم:
ابتدا یک راس دلخواه از گراف را در نظر می‌گیریم و از این راس در جهت کاملا دلخواه حرکت می‌کنیم تا یکی از دو حالت زیر رخ دهد:
اگر به راسی رسیدیم که قبلا در مسیر P وجود داشت، تمام گره‌های بین این راس که تاکنون پیموده شده‌است را هم در گراف H و هم در مسیر p منقبض می‌کنیم. یعنی همه آن‌ها را به عنوان یک راس در نظر می‌گیریم.
اگر به راسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مولفه قویا همبند معرفی می‌کنیم.
این الگوریتم از الگوریتم جستجوی عمق اول و همچنین دو پشته برای نمایش مسیر P استفاده می‌کند. پشته S که شامل دنباله راس‌های مسیر P است و پشته B که شامل کران‌های راس‌های منقبض شده‌است. در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مولفه قویا همبند را ذخیره می‌کند. به عبارت دقیق‌تر این ارائه به صورت زیر تعریف می‌شود:
Iv=۰ هرگاه گره v در مسیر P نباشد.
Iv=j هرگاه گره v اکنون در مسیر P باشد و Sj=v.
Iv=c هرگاه مولفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.
این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:
Algorithm STRONG(G)
۱ empty stacks S and B
۲ for v ∈ V do Iv=۰
۳ c=n
۴ for v ∈ V do if Iv=۰ then DFS(v)
Algorithm DFS(G)
۱ PUSH(v,S);Iv=TOP(S);PUSH(Iv,B);/*add v to the end of P*/
۲ for edges (v,w) ∈ E do
۳ if Iw=۰ then DFS(w)
۴ else /*contract if necessary*/
۵ while Iw<BTOP(B) do POP(B)
۶ if Iv=BTOP(B) then {/*number vertices of the next strong component*/
۷ POP(B);increase c by 1
۸ while Iv≤TOP(S) do IPOP(S)=c
در قضیه زیر برهان درستی و همچنین پیچیدگی این الگوریتم آمده‌است:
قضیه
هنگامی که (STRONG(G متوقف شود هر راس v ∈ V به مولفه قویا همبندی که توسط Iv شماره گذاری شده‌است تعلق دارد. همچنین زمان و حافظه مصرفی (O(m+n می‌باشند.
برای اثبات قضیه فوق می‌توانید به ۱ مراجعه کنید.
الگوریتم‌های مرتبط
برای دیدن الگوریتم‌های مرتبط با این الگوریتم می‌توانید به الگوریتم کساراجو و الگوریتم مولفه‌های همبند قوی تارجان مراجعه کنید.
الگوریتم گابو
الگوریتم چرین- ملورن/ گابو در نظریه گراف، یک روش با پیچیدگی زمانی خطی برای یافتن مولفه‌های همبندی قوی در یک گراف جهتدار است
. این الگوریتم در سال ۱۹۹۶ توسط جوزف چرین وکورت ملورن ارائه شد و در سال ۱۹۹۹ توسط هارولد گابو بهبود یافت.
الگوریتم گابو همانند الگوریتم مولفه‌های همبند قوی تارجان، تنها یک جستجوی عمق اول در گراف داده شده انجام می‌دهد،
و از یک پشته برای نگهداری گره‌هایی کهبه مولفه‌ای اختصاص داده نشده‌اند استفاده می‌کند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گره‌ها را به یک مولفه جدید منتقل می‌کند.الگوریتم تارجان از یک آرایه با اندیس گره‌ها شامل اعداد پیش‌ترتیب استفاده می‌کند، که به ترتیب دیده شدن در جستجوی عمق اول مقداردهی شده‌اند.از آرایه پیش‌ترتیبی برای دانستن اینکه چه زمانی مولفه همبندی جدید ایجا شود استفاده می‌گردد. الگوریتم گابو به جای استفاده از آرایه، از پشته دیگری به این منظور استفاده می‌کند.
الگوریتم گابو با پشتیبانی دو پشته 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 است، که این جستجوی بازگشتی را برای گره‌هایی که هنوز عدد پیش‌ترتیب آن‌ها مقدار دهی نشده‌است، صدا می‌زند.