بله می شه و از مرتبه 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 رو که اجرا میکنی میاد ۱ ۲ و ۳ رو میبینه و حلقه تا ۴ پیش میره و روی ۴ دوباره اجرا میشه و ۴ ۵ ۶ رو میبینه، واسه ۵ ۶ هیچ کاری نمیکنه تا برسه ..... و شما میتونی هر بار که اون شرط حلقه برقرار بشه یه کانتر رو اضاف کنی تا بهت بگه چندا مولفه همبندی داری.

به صورت کاملا مفهومی شیرفهم شد
تشکر