وجود دور در گراف

Question

سلام دوستان

چجوری میتونم با استفاده از جستجوی اول سطح وجود دور در گراف را تشخیص بدم ؟

و اینکه بفهم تعداد دورها چند تا است ؟

Answer 1

وجود دور رو با BFS , DFS میشه تشخیص داد کافیه که BFS رو روی یک راس شروع کنی  بعد راس هایی که ازشون رد میشی رو مارک دار کنی اگر به همون راس اول رسیدی که دور داری

اگر نرسیدی باید یکی دیگه از راس هایی که مارک دار نشدن رو برداری و مرحله بالا رو دوباره تکرار کنی .

 

برای پیدا کردن تمام دور هایی که از یک راس به راس دیگه وصل میشن هم از الگوریتم هایی مثل این استفاده میکنن

http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

 

البته تمام دور های داخل گراف  رو بعید می دونم به این راحتی بشه پیدا کرد قکر کنم جزو مسایل NP-complete حساب میشه !

Comments

منظورت چیه دورهایی که از یک راس به راس دیگه وصل میشن ؟؟!!!!
...
کلا من راه حل اولت را خیلی متوجه نمیشم .. میشه درست توضیح بدی ؟
اخه تو جستجوی اول سطح تو تنها زمانی به راس های عقب برمیگردی که به بن بست بخوری

---

خب منظورم اینه که دور هایی که شامل 2 تا راس هستن.. اشتباه نوشتم ! ... :)

یکبار dfs رو اجرا می کنی اگر گراف به هم متصل باشه یکبار که dfs رو انجام میدی همه ی راس رو یک بار پیمایش می کنی  حالا وقتی که داری dfs رو انجام میدی اگر از یک راس دوبار رد شی (البته غیر از زمانی که به عقب بر می گردی ) یعنی دور داریم
اگر گراف به هم متصل نباشه پس گراف یک قسمت جدا هم داره پس یک بار دیگه هم باید bfs رو روی اون قسمت جدا انجام بدی  برای همین باید مارک دار بشن تا بدونیم از کدوم راس ها رد شدیم .

---

خب حالا به تعداد راس هایی که دوبار ازشون گذشتیم دور داریم ؟

---

اون تعدادی که بدست میاد همه ی دور ها نیست ولی حداقل به همون تعداد دور رو داریم

---

چرا همش بدست نمیاد ؟

---

با حالت عادی  bfs نمیشه
ولی  میشه با یکم عوض کردنش و نگه داری لیست راس هایی قبلی همه ی دور ها رو پیدا کرد مشکل اینه که
مرتبه زمانی bfs این جا برای ما b^d هستش ( b تعداد دفعات تقسیم شدن و d عمق گراف ) و این که ما نیاز به جست و جو داخل یک لیست دیگه هم هر مرحله که bfs میره جلو هم داریم یعنی اگر تعداد راس ها از 20-30 تا و دفعات تقسیم شدن شاخه ها از یکی بیشتر بشن این الگوریتم عملا  بی فایدست !