تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از DFS توضیح داده شده.
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟
الگوریتم اینه:
Find a node v with no incoming edges and order it first
Delete v from G
Recursively compute a topological ordering of G-(v)
and append this order after v
مدرسان : [tex]O(V^2)[/tex]
پارسه : [tex]O(V E)[/tex]
برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کن
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
(۲۹ آبان ۱۳۹۳ ۰۸:۴۴ ب.ظ)Pakniat نوشته شده توسط: برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کنبله، این الگوریتم اصلی هست.
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
اینو میدونم.
منظورم مرتبه ی الگوریتمی هست که نوشتم.
این الگوریتم اینجوریه که میاد گره ای رو که درجه ورودیش صفر هست رو پیدا میکنه و حذف میکنه و.....
(۲۹ آبان ۱۳۹۳ ۰۳:۱۳ ب.ظ)Ametrine نوشته شده توسط: تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از DFS توضیح داده شده.
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟
مدرسان : [tex]O(V^2)[/tex]
پارسه : [tex]O(V E)[/tex]
فک کنم یکیشون بر حسب ماتریس مجاورت گفته یکی دیگه بر حسب لیست مجاورتی.
( O(v+e نباید باشه، چون پیچیدگی dfs تتا هستش نه O