مولفهٔ قویاً هم‌بند مجموعه‌ای از گره‌هایِ گرافِ جهت‌دار است که هر دو عضوِ آن از یکدیگر دسترس‌پذیر باشند. این گروه‌بندی با فهرستِ گره‌هایِ مسدود یا یک درختِ پیمایش یکی نیست. در این تمرین، دو گروهِ چرخه‌ای، یک وابستهٔ بیرونی و یک گرهِ منزوی را افراز می‌کنیم و سپس گرافِ فشردهٔ مولفه‌ها را می‌سازیم.
دو چرخه با یک راهِ یک‌طرفه
شش گرهٔ اصیلA،B،C،D،E وU داریم. یال‌هایِ A→B وB→A گروهِ اول را می‌سازند؛ C→D وD→C گروهِ دوم را. ازBبهC وازDبهE هم یال داریم. U منزوی است. ازگروهِ اول می‌توان به گروهِ دوم رسید،اما راهِ برگشت ازگروهِ دوم به اول نداریم؛ پس صرفِ وجودِ مسیر،مجوزِ ادغامِ دو گروه نیست.
انتظارِ مستقلِ این گراف چهار مولفه است: [A,B]،[C,D]،[E] و[U]. گرهٔE ازدو چرخه اثر می‌گیرد،اما عضوِ هیچ‌یک نیست. U نیز با نداشتنِ یال حذف نمی‌شود. نام‌ها فقط دفترِ آموزشی‌اند و وظیفه،سامانه یا مشتریِ واقعی را نشان نمی‌دهند.
دو گذرِ محدود،یک افراز
پیاده‌سازیِ اصیلِ ما ابتدا DFS را رویِ گرافِ معکوس اجرا و ترتیبِ پایان را نگه می‌دارد. درگذرِ دوم،گره‌ها را با ترتیبِ معکوسِ آن پایان‌ها رویِ گرافِ اصلی بررسی می‌کند؛ هر پیمایشِ تازه یک گروه را جمع می‌کند. این ساختار بر تعریفِ روشِ Kosaraju–Sharir در منبعِ اصلی متکی است،اما Java یا کتابخانهٔگراف در این تمرین اجرا نشده است.
برایِ خواندنِ خروجی،عضوهایِ هر گروه و خودِ گروه‌ها مرتب می‌شوند و شناسهٔعددیِ نمایشی می‌گیرند. این شماره‌ها هویتِ جهان‌شمولِ مولفه نیستند. تغییرِ ترتیبِ بازدید در پیاده‌سازیِ دیگر می‌تواند همان افراز را با شماره‌هایِ دیگر نشان دهد؛ برابریِ گروه‌ها مهم‌تر ازعددِ برچسب است.
گرافِ مولفه‌ها چه چیزی را حفظ می‌کند؟
هر مولفه را یک گره می‌گیریم. یالِ داخلِ مولفه کنار می‌رود و یال‌هایِ تکراریِ بینِ دو مولفه یک بار نگه داشته می‌شوند. درمثالِ ما،گرافِ فشرده دو یال دارد: [A,B]→[C,D] و[C,D]→[E]. مولفهٔ[U] همچنان جدا حاضر است. این تبدیل نامِ گره‌ها و رابطهٔبینِ گروه‌ها را نشان می‌دهد،نه رفعِ خودکارِ چرخهٔداخلِ آن‌ها.
| مولفه | راهِ دوطرفه درونِ گروه | ارتباطِ بیرونیِ نمونه |
|---|---|---|
| [A,B] | A↔B | راه به[C,D] |
| [C,D] | C↔D | راه به[E] |
| [E] | تک‌عضوی | بدونِ خروجی |
| [U] | تک‌عضوی | منزوی |
برایِ کنترلِ بدون‌چرخه‌بودنِ گرافِ فشرده،Kahnِ مستقل رویِ indegree آن اجرا می‌شود و همهٔچهارمولفه درخروجی می‌آیند. چند ترتیبِ معتبر ممکن است وجود داشته باشد؛ قاعدهٔنمایشِ ما ترتیبِ معناییِ یگانه یا زمان‌بندیِ بهینه ایجاد نمی‌کند.
افراز را با دسترسیِ همهٔزوج‌ها بسنجیم
یک BFSِ جدا ازهرگره،مجموعهٔگره‌هایِ دسترس‌پذیر را می‌سازد. برایِ هر۳۶زوجِ گرافِ اصلی بررسی می‌کنیم: برچسبِ مولفه برابر است اگر و فقط اگر راه درهردوجهت وجود دارد. همچنین هرگره باید دقیقاًیک بار در افراز باشد. تنها برابرشدنِ تعدادِ گروه‌ها برایِ این کنترل کافی نیست.
درآزمونِ محدودِ دیگر،همهٔ۵۱۲گرافِ جهت‌دارِ سه‌گرهی با امکانِ self-loop ساخته و باهمین oracle بررسی می‌شوند. تک‌عضویِ دارایِ حلقه وگرهِ منزوی درfixtureِ جدا هم حاضرند. این پوششِ کاملِ جهانِ سه‌گرهی است،نه اثباتِ ماشینیِ همهٔگراف‌ها یا benchmarkِ زمان.
تک‌عضوی هم مولفه است؛اما الزاماً چرخه ندارد
هرگره به خودش با مسیرِ صفر‌یالی دسترس دارد؛ پس گرهِ منزوی هم مولفهٔتک‌عضوی است. اگر بخواهیم دربارهٔچرخهٔواقعیِ آن حرف بزنیم،وجودِ self-loop یا مسیرِ با دست‌کم یک یال را جدا می‌سنجیم. مثالِ Xباself-loop وUبدونِ آن دو گروهِ تک‌عضوی می‌دهد؛ یکسان‌بودنِ اندازه،رفتارِ چرخه را یکی نمی‌کند.
مرتب‌سازیِ توپولوژیک نشان می‌دهد گرهٔمسدود الزاماًعضوِ چرخه نیست؛ اینجا گروه‌هایِ دسترسیِ دوطرفه را کامل می‌سازیم. BFS وDFS نیز پیمایشِ یک مبدأ را توضیح می‌دهند. ادامه در مبانی هوش مصنوعی؛ این کدِ Python۳٫۱۲٫۱۴،گرافِ کوچکِ بازگشتی می‌خواهد و اجرایِ workflow یا تحلیلِ خودکارِ محصولِ اپرا را اعلام نمی‌کند.
فایل تمرین و منبع
کد مستقلِ تمرینِ محدود · تمام خروجیِ واقعیِ همین تمرین؛ JSON
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.