زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۴۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟

ارسال:
  

Masoud05 پرسیده:

یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟

یافتن مولفه های همبند گراف جهتدار به چه روش و با چه مرتبه ای حل میشه؟

۳
ارسال:
  

arshad90 پاسخ داده:

RE: مولفه همبند

برای یافتن مولفه های متصل قوی در یک گراف جهتدار:

۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).

۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.

۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی f‌ها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.

ارسال:
  

reza_d500 پاسخ داده:

RE: مولفه همبند

(۱۰ بهمن ۱۳۸۹ ۱۱:۵۸ ب.ظ)arshad90 نوشته شده توسط:  برای یافتن مولفه های متصل قوی در یک گراف جهتدار:

۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).

۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.

۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی f‌ها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.

راه حلتون درست اما ...
چرا این کار رو میکنیم. دلیل برعکس کردن جهات، نزولی f ها چیه؟
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۳,۸۳۸ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۰۴۰ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۱,۱۹۸ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۱۹,۱۲۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۱,۸۸۷ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد روش های نوشتن عدد n ss311 ۲ ۲,۹۵۳ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۱,۷۹۱ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  مشاوره روش تحقیق و تحلیل آماری sirvan.t ۰ ۱,۹۰۸ ۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ
آخرین ارسال: sirvan.t
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۴۰۷ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close