سلام
آیا با dfs میتوان مولفه های همبندی را تشخیص داد یا فقط با bfs امکان داره؟
بله می شه و از مرتبه V+E
V:راس
E: یال
(۲۱ دى ۱۳۹۲ ۰۱:۴۲ ق.ظ)maxwel نوشته شده توسط: بله می شه و از مرتبه VEمیشه توضیحش را هم بدید چه جوریه که مفهومی گرفته باشم
V:راس
E: یال
مثلا bfs میدونم که وقتی همبند نباشه بعضی رئوس ملاقات نمیشه
ولی dfs که همه رئوس را ملاقات میکنه از کجا میشه فهمید؟
(۲۱ دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)masoud67 نوشته شده توسط: سلام
آیا با dfs میتوان مولفه های همبندی را تشخیص داد یا فقط با bfs امکان داره؟
شما دوتا رویه دارید، یکی DFS و دیگری DFS-VISIT. اگه شما الگوریتم dfs رو نگا بندازید توی یه حلقه از ۰ تا n-1 میاد اگه اون راس ملاقات نشده بود روی اون DFS-Visit رو اجرا میکنه و رویه dfs_visit هر چی راس که به اون راس راه داشته باشه رو میاد ملاقات میکنه، حالا اگه گراف شما همبند باشه این حلقه بار اول اجرا میشه و بار های بعدی دیگه اون شرطش درست نیست. ولی اگه گرافت مثلا نا همبند باشه و ۳ تا تیکه باشه و تکه اول ۱ ۲ ۳ باشن تکه دوم ۴ ۵ ۶ و تکه سوم ۷ ۸ ۹ بار اول که dfs_visit رو که اجرا میکنی میاد ۱ ۲ و ۳ رو میبینه و حلقه تا ۴ پیش میره و روی ۴ دوباره اجرا میشه و ۴ ۵ ۶ رو میبینه، واسه ۵ ۶ هیچ کاری نمیکنه تا برسه ..... و شما میتونی هر بار که اون شرط حلقه برقرار بشه یه کانتر رو اضاف کنی تا بهت بگه چندا مولفه همبندی داری.
(۲۱ دى ۱۳۹۲ ۰۲:۱۹ ق.ظ)Riemann نوشته شده توسط:به صورت کاملا مفهومی شیرفهم شد(21 دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)masoud67 نوشته شده توسط: سلام
آیا با dfs میتوان مولفه های همبندی را تشخیص داد یا فقط با bfs امکان داره؟
شما دوتا رویه دارید، یکی DFS و دیگری DFS-VISIT. اگه شما الگوریتم dfs رو نگا بندازید توی یه حلقه از ۰ تا n-1 میاد اگه اون راس ملاقات نشده بود روی اون DFS-Visit رو اجرا میکنه و رویه dfs_visit هر چی راس که به اون راس راه داشته باشه رو میاد ملاقات میکنه، حالا اگه گراف شما همبند باشه این حلقه بار اول اجرا میشه و بار های بعدی دیگه اون شرطش درست نیست. ولی اگه گرافت مثلا نا همبند باشه و ۳ تا تیکه باشه و تکه اول ۱ ۲ ۳ باشن تکه دوم ۴ ۵ ۶ و تکه سوم ۷ ۸ ۹ بار اول که dfs_visit رو که اجرا میکنی میاد ۱ ۲ و ۳ رو میبینه و حلقه تا ۴ پیش میره و روی ۴ دوباره اجرا میشه و ۴ ۵ ۶ رو میبینه، واسه ۵ ۶ هیچ کاری نمیکنه تا برسه ..... و شما میتونی هر بار که اون شرط حلقه برقرار بشه یه کانتر رو اضاف کنی تا بهت بگه چندا مولفه همبندی داری.
تشکر