BFS
O(E +V)

Sent from my SM-T210R using Tapatalk

(۰۶ بهمن ۱۳۹۲ ۰۸:۲۷ ب.ظ)hoomanab نوشته شده توسط:  BFS
O(E +V)

Sent from my SM-T210R using Tapatalk

توی یکی از کوییزهای دانشگاه MIT گفته هم از bfs و هم از dfs برای پیدا کردن دور در گراف غیر جهت دار استفاده میشه!!!!!

درسته. اما با یک بار bfs میشه اینکار رو کرد. با n بار dfs هم میشه.

Sent from my SM-T210R using Tapatalk

(۰۶ بهمن ۱۳۹۲ ۰۸:۴۱ ب.ظ)hoomanab نوشته شده توسط:  درسته. اما با یک بار bfs میشه اینکار رو کرد. با n بار dfs هم میشه.

Sent from my SM-T210R using Tapatalk

پس یعنی دور به طول زوج یا فرد رو میشه با یکبار BFS ویا Nبار DFS بدست آورد، بسیییییار متشکرم

میشه یک شمارنده گذاشت برای هر راس که تعداد یال های مسیر رو بشماره و با رسیدن به یال عقبگرد معلوم شه دور زوج بوده یا فرد. البته این اه حل الان به ذهنم رسید و از درست یا غلط بودنش مطمین نیستم.
ولی dfs با همون n بار باید حل شه

Sent from my SM-T210R using Tapatalk