(۱۰ دى ۱۳۹۲ ۰۴:۳۴ ق.ظ)pooyaa نوشته شده توسط:  ۱-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف جهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
۲-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف غیرجهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟

- جهتدار و وزن دار بودنش اهمیت ندارد.
- کافی است الگوریتم DFS را به این صورت تغییر دهید که در حلقه for از تابع به نام DFS_visit هرگاه یال بیرون آمده قهوه ای بود، شمارنده را یکی زیاد کنید. مرتبه آن دقیقا برابر مرتبه DFS می باشد یعنی برابر :

$\theta (E V)$

(۱۰ دى ۱۳۹۲ ۰۵:۲۱ ق.ظ)Morris نوشته شده توسط:  

(10 دى ۱۳۹۲ ۰۴:۳۴ ق.ظ)pooyaa نوشته شده توسط:  ۱-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف جهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟
۲-الگوریتمی که بتونه تعداد دورهای موجود در یک گراف غیرجهتدار وزن دار رو پیدا کنه حداقل از چه مرتبه ای خواهد بود؟بی وزن چطور؟

- جهتدار و وزن دار بودنش اهمیت ندارد.
- کافی است الگوریتم DFS را به این صورت تغییر دهید که در حلقه for از تابع به نام DFS_visit هرگاه یال بیرون آمده قهوه ای بود، شمارنده را یکی زیاد کنید. مرتبه آن دقیقا برابر مرتبه DFS می باشد یعنی برابر :

$\theta (E V)$

سلام
توضیح شما درسته اما برای DFS جهتدار میشه" e+n " اما اگه درجه هرگره دقیقا ۲ باشه میشه" n "