بررسی همبند بودن گراف

Question

از چه الگوریتمی میشه برای تعیین همبند بودن یا نبودن ۱ گراف استفاده کرد؟

Answer 1

شما اگه الگوریتمهایی مثل bfs , dfs رو بلد باشین کافیه از یک نود شروع کنین و بر اساس یکی از این پیمایشها فرزندان و بقیه نودها رو پیمایش کنین و هروقت به یه نود رسیدین تعیین کنین که اون نودو پیمایش کردین مثلا با یه سوییچ یا پرچم که بولین هست . در آخر ببینین اگه تمام نودها پیمایش شده بودن یعنی اون مقدار برای همه آونها true بود پس همبنده

Comments

خب همین رو که من هم نوشته بودم!

Answer 2

الکوریتم زیاد داره مثلا پرایم.

یک برنامه بازگشتی باید بنویسی که بیاد به تمام نودهایی که بهش وصله فلگی ست کنه. دور بعدی باید تک تک این نودهایی که فلگ دارند همین کار رو کنند تا دیگه نود فلگ دار بررسی نشده باقی نمونه. اگر نودی مونده باشه که فلگ نداشته باشه همبند نیست.

Comments

فکر نکنم پرایم مناسب باشه و کارش این باشه
پرایم برای تعیین درخت پوشای مینیمم هست و هزینش n2 هست
بهتره از همون روشهای پیشمایش مرسوم bfs dfs استفاده بشه

Answer 3

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