سلام
گراف بدون جهت [tex]G(V,E)[/tex] مفروض است.میخواهیم مشخص کنیم آیا گراف شامل حلقه است یا نه. کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
۱-[tex]O(|E|)[/tex]
۲-[tex]O(|V|*|E|)[/tex]
۳-[tex]O(|V|)[/tex]
۴-[tex]O(|V| |E|)[/tex]
من در اینجوری مسئله های یکم مشکل دارم و تحلیلم قوی نیست. اگه میشه یکی واسم تحلیل کنه سوالو.ممنون
طبق قانون : درصورتی گراف بدون دور است که dfs آن یال پشتی ندهد
برای این سوال هم dfs انجام میدیم اگه یال پشتی داد یعنی دور داره و اگه نداد پس نداره
dfs هم در زمان خطی انجام میشه در زمان( O (v انجام میشه
(۱۴ آذر ۱۳۹۲ ۰۸:۰۰ ب.ظ)tabassomesayna نوشته شده توسط: سلام
گراف بدون جهت [tex]G(V,E)[/tex] مفروض است.میخواهیم مشخص کنیم آیا گراف شامل حلقه است یا نه. کوچکترین حد بالای زمان اجرای سریع ترین الگوریتم برای حل این مسئله کدام است ؟
۱-[tex]O(|E|)[/tex]
۲-[tex]O(|V|*|E|)[/tex]
۳-[tex]O(|V|)[/tex]
۴-[tex]O(|V| |E|)[/tex]
من در اینجوری مسئله های یکم مشکل دارم و تحلیلم قوی نیست. اگه میشه یکی واسم تحلیل کنه سوالو.ممنون
برای تحلیل این مساله نیاز به دو گام است :
در گام اول : E>v-1 اگر اینگونه باشد ، قطعا در گراف دور داریم.
در گام دوم : اگر رابطه بالا صدق نکنه ، پس E کمتر یا مساوی V هست . بنابراین با بکارگیری DFS ، میتونیم به مرتیه(O ( V+E برسیم که چون E کوچکتر V هست پس میشه همون (O(V . علت به کارگیری DFS هم جناب ۲۰۱۳محمد توضیح دادند