مرتب‌سازی توپولوژیک و مؤلفه‌های قویاً‌متصل با استفاده از DFS

گراف‌های غیرچرخه‌ای جهت‌دار و ترتیب‌بندی وابستگی

یک Directed Acyclic Graph (DAG) یک گراف جهت‌دار، همان‌طور که پیش‌تر در این مجموعه معرفی شد، است که هیچ چرخه‌ای ندارد. DAG ها به‌طور طبیعی روابط وابستگی را مدل‌سازی می‌کنند: ترتیب کامپایل یک سیستم build، پیش‌نیازهای وظیفه یک پروژه، یا زنجیره‌های پیش‌نیاز یک کاتالوگ درسی همگی DAG تشکیل می‌دهند، جایی که یک یال از u به v یعنی u باید پیش از v اتفاق بیفتد.

مسئله مرتب‌سازی توپولوژیک

یک Topological Sort (مرتب‌سازی توپولوژیک) یک DAG یک ترتیب خطی از همه رأس‌هایش است طوری‌که برای هر یال (u, v)، u پیش از v در ترتیب ظاهر شود. این یک توالی معتبر برای انجام همه وظایف نمایانده‌شده توسط گراف در حالی که هر وابستگی را رعایت می‌کند فراهم می‌کند.

مثال: لباس‌پوشیدن، با وابستگی‌ها
جوراب → کفش
لباس‌زیر → شلوار
شلوار → کفش
شلوار → کمربند

یک مرتب‌سازی توپولوژیک معتبر:
لباس‌زیر، جوراب، شلوار، کفش، کمربند

(اغلب چند ترتیب معتبر وجود دارد؛
 این فقط یکی از آن‌هاست)

الگوریتم: DFS به‌علاوه زمان پایان معکوس

مرتب‌سازی توپولوژیک یک الگوریتم به‌طور قابل‌توجه ظریف دارد که مستقیماً روی زمان‌های پایان جستجوی عمق‌اول که پیش‌تر در این مجموعه بحث شد ساخته شده است.

TOPOLOGICAL-SORT(G):
  DFS(G) را فراخوانی کن تا زمان‌های پایان v.f برای هر رأس محاسبه شود
  همان‌طور که هر رأس پایان می‌یابد، آن را در ابتدای یک لیست پیوندی درج کن
  لیست پیوندی را برگردان

به‌طور معادل، این می‌تواند این‌طور توصیف شود: DFS را اجرا کن، و رأس‌ها را به ترتیب کاهشی زمان پایانشان خروجی بده.

چرا این رویکرد ساده کار می‌کند

استدلال درستی به یک ویژگی کلیدی متکی است: برای هر یال (u, v) در یک DAG، v باید پیش از u پایان یابد. این مستقیماً از طبقه‌بندی یال DFS که پیش‌تر در این مجموعه بحث شد پیروی می‌کند: از آنجا که گراف غیرچرخه‌ای است، یال (u, v) نمی‌تواند یک یال عقبی باشد (که یک چرخه ایجاد می‌کرد)، پس باید یک یال درختی، پیش‌رونده، یا متقاطع باشد، و در هرکدام از این موارد، زمان پایان v تضمین می‌شود زودتر از u باشد.

اگر (u, v) یک یال درختی یا پیش‌رونده باشد:
  v نواده u است، پس v باید پیش از u پایان یابد
  (DFS-VISIT برای u تا زمانی که همه فراخوانی‌های بازگشتی،
   شامل آن برای v، بازنگردند پایان نمی‌یابد)

اگر (u, v) یک یال متقاطع باشد:
  v باید از قبل کاملاً پایان یافته باشد
  پیش از اینکه DFS-VISIT مربوط به u حتی u را کشف کند،
  چون زیردرخت v ابتدا کاملاً کاوش شده بود

از آنجا که v.f < u.f برای هر یال (u, v) برقرار است، مرتب‌کردن رأس‌ها بر اساس زمان پایان کاهشی تضمین می‌کند u پیش از v برای هر یال ظاهر شود، که دقیقاً نیاز مرتب‌سازی توپولوژیک را برآورده می‌کند.

از آنجا که این الگوریتم صرفاً DFS با یک افزوده زمان-ثابت به‌ازای هر رأس (اضافه‌کردن به ابتدای یک لیست) است، در زمان Θ(V + E) اجرا می‌شود، که با کارایی خود DFS مطابقت دارد.

مؤلفه‌های قویاً‌متصل

در یک گراف جهت‌دار، یک Strongly Connected Component (SCC) یک مجموعه بیشینه از رأس‌ها است طوری‌که هر رأس در آن مجموعه می‌تواند از طریق یک مسیر جهت‌دار به هر رأس دیگر در آن مجموعه برسد. این مفهوم پیچیدگی معادلی در گراف‌های بدون‌جهت ندارد، جایی که اتصال ساده از قبل این مفهوم را در بر می‌گیرد؛ در گراف‌های جهت‌دار، دسترس‌پذیری متقابل یک ویژگی واقعاً متمایز و محدودکننده‌تر است.

مثال گراف جهت‌دار با SCC ها:
a → b → c → a   (دسترس‌پذیر متقابل: یک SCC {a, b, c})
c → d           (d از اولین SCC دسترس‌پذیر است)
d → e → d       (دسترس‌پذیر متقابل: SCC دیگر {d, e})

این گراف 2 مؤلفه قویاً‌متصل دارد:
{a, b, c} و {d, e}

الگوریتم کوساراجو: یک راه‌حل DFS دوعبوری ظریف

یافتن کارآمد SCC ها به یک الگوریتم به‌طور زیبا ساده متکی است که دقیقاً از دو عبور جستجوی عمق‌اول، همراه با Transpose (ترانهاده) گراف — همان گراف با جهت هر یال معکوس‌شده — استفاده می‌کند.

STRONGLY-CONNECTED-COMPONENTS(G):
  ۱. DFS(G) را فراخوانی کن تا زمان‌های پایان u.f برای هر رأس u محاسبه شود
  ۲. Gᵀ (ترانهاده G — هر یال را معکوس کن) را محاسبه کن
  ۳. DFS(Gᵀ) را فراخوانی کن، اما در حلقه اصلی، رأس‌ها را
     به ترتیب کاهشی u.f (از گام ۱) پردازش کن
  ۴. رأس‌های هر درخت در جنگل DFS حاصل
     (از گام ۳) را به‌عنوان یک SCC جداگانه خروجی بده

محاسبه گراف ترانهاده زمان Θ(V + E) با استفاده از یک لیست مجاورت (که پیش‌تر در این مجموعه بحث شد) می‌گیرد، صرفاً با معکوس‌کردن هر یال حین ساخت نمایش جدید. از آنجا که الگوریتم تعداد ثابتی فراخوانی DFS انجام می‌دهد، هرکدام زمان Θ(V + E)، به‌علاوه محاسبه ترانهاده، زمان اجرای کل Θ(V + E) است.

شهودی که پشت چرایی کارکردن این هست

درستی این الگوریتم به یک ویژگی ظریف اما قدرتمند متکی است: رأس با بالاترین زمان پایان از اولین عبور DFS باید متعلق به یک SCC "منبع" در گراف مؤلفه فشرده‌شده (گرافی که با کوچک‌کردن هر SCC به یک گره واحد تشکیل می‌شود) باشد — به این معنا که هیچ SCC دیگری یالی به آن ندارد. اجرای DFS روی گراف ترانهاده‌شده، شروع از رأس‌هایی با بالاترین زمان‌های پایان، تضمین می‌کند هر فراخوانی DFS-VISIT در عبور دوم دقیقاً یک SCC کامل را پیش از "گیرکردن" کاوش می‌کند، چون یال‌های معکوس‌شده جستجو را از فرار به رأس‌های متعلق به یک SCC متفاوت که از قبل کاملاً پردازش شده منع می‌کنند.

چرا این الگوریتم‌ها در عمل اهمیت دارند

مرتب‌سازی توپولوژیک زیربنای زمان‌بندهای وظیفه، سیستم‌های build (تعیین ترتیب کامپایل بر اساس وابستگی‌های فایل)، و ارزیابی فرمول صفحه‌گسترده (محاسبه سلول‌ها به ترتیبی که رعایت می‌کند کدام سلول‌ها به دیگران وابسته‌اند) است. مؤلفه‌های قویاً‌متصل در طراحی کامپایلر (شناسایی گروه‌های تابع متقابلاً بازگشتی)، تحلیل ساختارهای لینک وب، و تشخیص وابستگی‌های چرخه‌ای در بسته‌های نرم‌افزاری استفاده می‌شوند، جایی که یک SCC شامل بیش از یک رأس مستقیماً یک چرخه وابستگی مسئله‌ساز را نشان می‌دهد. هر دو الگوریتم یک موضوع تکرارشونده در این مجموعه را نشان می‌دهند: اطلاعات ساختاری غنی گرفته‌شده توسط زمان‌های کشف و پایان DFS، که ابتدا پیش‌تر در این مجموعه معرفی شد، پایه‌ای برای حل مسائلی که در نگاه اول به‌نظر می‌رسد ربط کمی به پیمایش ساده گراف دارند فراهم می‌کند.