با داشتن تعداد یال ها در O(V) می توان در یک گراف ساده و بدون جهت سیکل را تشخیص دارد درسته یا غلطه ؟ چرا؟
(۲۳ بهمن ۱۳۹۳ ۱۲:۳۸ ب.ظ)mino_master نوشته شده توسط: با داشتن تعداد یال ها در O(V) می توان در یک گراف ساده و بدون جهت سیکل را تشخیص دارد درسته یا غلطه ؟ چرا؟درسته!
اگه تعداد یالها از تعداد راسها بیشتر مساوی باشه که قطعا دور داریم! O(1
اگه کمتر باشه، با یک بار حرکت روی یالها میشه فهمید دور داره یا نه. O(E = O(V
حالا شما بیا ثابت کن این بزرگترین سوال چالشی ساختمان داده هست!