سلام بچه ها خسته نباشید.کسی میتونه جواب این سوالو برام توضیح بده؟؟
وجود دور در گراف بدون جهت را در بهترین حالت با چه مرتبه ای ،میتوان به دست اورد؟؟
۱-[tex]O(|E| |V|)[/tex]
۲-[tex]O(|V|)[/tex]
۳-[tex]O(|E||V|)[/tex]
۴-[tex]O(|E|Log|V|)[/tex]
___________________________________________________________________________
جواب گزینه ۲ میشه
قطعا همه قبول داریم که یاگزینه ۱ درسته یاگزینه۲/اما گزینه ۲ درسته چون صرفا وجود دور رامی خواهیم بررسی کنیم وبا انجام پیمایش اول عمق بدون نیازبه بررسی تمام یالها می توانیم این کاررا انجام دهیم.ما نیازبه دوری به طول حداکثر V داریم.
گزینه ۱
بهترینشو نمیدونم دقیقا ولی این چیزی بود ک ب ذهنم اومد.
از روش جستجوی اول عمق استفاده شده است. ابتدا تمام گره ها برچسب white می گیرند. سپس هر گرهی که مشاهده می شود برچسب gray می گیرد و زمانی که تمام فرزندانش مشاهده شدند برچسب black می گیرد. اگر در حین جستجو به یک گره با برچسب gray رسیدیم، به این معنی است که در گراف دور وجود دارد. زمان اجرای الگوریتم تشخیص دور در گراف برابر با زمان اجرای الگوریتم جستجوی اول عمق است یعنی V+E است.
پ.ن:داخل stackoverflow هم خوندم ک برای پیدا کردن تعداد دور از الگوریتم مولفه های متصل قوی استفاده میکنیم
گفتم نکته گفته باشملطفا جناب King2 میشه در موردگزینه ای ک گفتید بیشتر توضیح بدید ممنون
(۲۹ آذر ۱۳۹۳ ۰۳:۳۹ ب.ظ)monji_421 نوشته شده توسط: گزینه ۱
بهترینشو نمیدونم دقیقا ولی این چیزی بود ک ب ذهنم اومد.
از روش جستجوی اول عمق استفاده شده است. ابتدا تمام گره ها برچسب white می گیرند. سپس هر گرهی که مشاهده می شود برچسب gray می گیرد و زمانی که تمام فرزندانش مشاهده شدند برچسب black می گیرد. اگر در حین جستجو به یک گره با برچسب gray رسیدیم، به این معنی است که در گراف دور وجود دارد. زمان اجرای الگوریتم تشخیص دور در گراف برابر با زمان اجرای الگوریتم جستجوی اول عمق است یعنی V+E است.
پ.ن:داخل stackoverflow هم خوندم ک برای پیدا کردن تعداد دور از الگوریتم مولفه های متصل قوی استفاده میکنیم
لطفا جناب King2 میشه در موردگزینه ای ک گفتید بیشتر توضیح بدید ممنون
به نظرم نکته دراینه که ما به دنبال اولین جایی هستیم که به یک راس gray برسیم.بنابراین الزاما تمام یالها پیمایش نمی شوند بلکه برای داشتن دورکافی است که تعداد V یال مجزاداشته باشیم.درچنین گرافی قطعا دوروجوددارد.
(۲۹ آذر ۱۳۹۳ ۰۵:۲۶ ب.ظ)King2 نوشته شده توسط:(29 آذر ۱۳۹۳ ۰۳:۳۹ ب.ظ)monji_421 نوشته شده توسط: گزینه ۱
بهترینشو نمیدونم دقیقا ولی این چیزی بود ک ب ذهنم اومد.
از روش جستجوی اول عمق استفاده شده است. ابتدا تمام گره ها برچسب white می گیرند. سپس هر گرهی که مشاهده می شود برچسب gray می گیرد و زمانی که تمام فرزندانش مشاهده شدند برچسب black می گیرد. اگر در حین جستجو به یک گره با برچسب gray رسیدیم، به این معنی است که در گراف دور وجود دارد. زمان اجرای الگوریتم تشخیص دور در گراف برابر با زمان اجرای الگوریتم جستجوی اول عمق است یعنی V+E است.
پ.ن:داخل stackoverflow هم خوندم ک برای پیدا کردن تعداد دور از الگوریتم مولفه های متصل قوی استفاده میکنیم
لطفا جناب King2 میشه در موردگزینه ای ک گفتید بیشتر توضیح بدید ممنون
به نظرم نکته دراینه که ما به دنبال اولین جایی هستیم که به یک راس gray برسیم.بنابراین الزاما تمام یالها پیمایش نمی شوند بلکه برای داشتن دورکافی است که تعداد V یال مجزاداشته باشیم.درچنین گرافی قطعا دوروجوددارد.
جناب کینگ باهاتون موافقم .ممنون
جناب میلاد میشه بگید کدوم جواب درسته؟؟؟
سلام .جناب King2 میشه درباره جواب یکم بیشتر توضیح بدید.ممنون میشم
(۲۹ آذر ۱۳۹۳ ۰۷:۰۹ ب.ظ)miladcr7 نوشته شده توسط: سلام .جناب King2 میشه درباره جواب یکم بیشتر توضیح بدید.ممنون میشم
برای توضیح بیشتر می تونم بگم ما نیازی به پیمایش تمام لیست مجاورتی نداریم.بلکه همین که به V یال مجزابرسیم کافیه که بگیم گراف حتما دور دارد.
جواب گزینه ۲میشه. اگر گراف جهت دار باشه گزبنه یک درسته...