یافتن مولفه های همبند گراف جهتدار به چه روش و با چه مرتبه ای حل میشه؟
برای یافتن مولفه های متصل قوی در یک گراف جهتدار:
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
(۱۰ بهمن ۱۳۸۹ ۱۱:۵۸ ب.ظ)arshad90 نوشته شده توسط: برای یافتن مولفه های متصل قوی در یک گراف جهتدار:
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
راه حلتون درست اما ...
چرا این کار رو میکنیم. دلیل برعکس کردن جهات، نزولی f ها چیه؟