۱-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف جهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
۲-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف غیرجهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
(۱۰ دى ۱۳۹۲ ۰۴:۳۴ ق.ظ)pooyaa نوشته شده توسط: ۱-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف جهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
۲-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف غیرجهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
- جهتدار و وزن دار بودنش اهمیت ندارد.
- کافی است الگوریتم DFS را به این صورت تغییر دهید که در حلقه for از تابع به نام DFS_visit هرگاه یال بیرون آمده قهوه ای بود، شمارنده را یکی زیاد کنید. مرتبه آن دقیقا برابر مرتبه DFS می باشد یعنی برابر :
[tex]\theta (E V)[/tex]
(۱۰ دى ۱۳۹۲ ۰۵:۲۱ ق.ظ)Morris نوشته شده توسط:(10 دى ۱۳۹۲ ۰۴:۳۴ ق.ظ)pooyaa نوشته شده توسط: ۱-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف جهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
۲-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف غیرجهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
- جهتدار و وزن دار بودنش اهمیت ندارد.
- کافی است الگوریتم DFS را به این صورت تغییر دهید که در حلقه for از تابع به نام DFS_visit هرگاه یال بیرون آمده قهوه ای بود، شمارنده را یکی زیاد کنید. مرتبه آن دقیقا برابر مرتبه DFS می باشد یعنی برابر :
[tex]\theta (E V)[/tex]
سلام
توضیح شما درسته اما برای DFS جهتدار میشه" e+n " اما اگه درجه هرگره دقیقا ۲ باشه میشه" n "