تالار گفتمان مانشت
دور به طول زوج یا فرد؟ - نسخه‌ی قابل چاپ
دور به طول زوج یا فرد؟ - Mindhunter - 06 بهمن ۱۳۹۲ ۰۸:۲۱ ب.ظ

سلام دوستان برای پیدا کردن دور به طول فرد و دور به طول زوج در یک گراف از کدام الگوریتم استفاده میشود؟؟ BFS یا DFS?
پیچیدگی زمانی چه میشود؟؟
مرسیBig Grin

RE: دور به طول زوج یا فرد؟ - hoomanab - 06 بهمن ۱۳۹۲ ۰۸:۲۷ ب.ظ

BFS
O(E +V)

Sent from my SM-T210R using Tapatalk

RE: دور به طول زوج یا فرد؟ - Mindhunter - 06 بهمن ۱۳۹۲ ۰۸:۳۹ ب.ظ

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

Sent from my SM-T210R using Tapatalk

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

RE: دور به طول زوج یا فرد؟ - hoomanab - 06 بهمن ۱۳۹۲ ۰۸:۴۱ ب.ظ

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

Sent from my SM-T210R using Tapatalk

RE: دور به طول زوج یا فرد؟ - Mindhunter - 06 بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ

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

Sent from my SM-T210R using Tapatalk

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

RE: دور به طول زوج یا فرد؟ - hoomanab - 06 بهمن ۱۳۹۲ ۰۹:۰۷ ب.ظ

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

Sent from my SM-T210R using Tapatalk