۰
subtitle
ارسال: #۱
مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر
تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از 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]
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟
الگوریتم اینه:
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]
۰
ارسال: #۲
RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر
برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کن
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
ارسال: #۳
RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر
(۲۹ آبان ۱۳۹۳ ۰۸:۴۴ ب.ظ)Pakniat نوشته شده توسط: برای بدست آوردن ترتیب توپولوژیکی عناصر ابتدا DFS رو یکبار برای بدست آوردن Finishing time گره ها اجرا کنبله، این الگوریتم اصلی هست.
بعد بر اساس ماکزیمم مقدار finishing time باید عناصر رو به ترتیب در یک صف قرار بدی
بعد از ابتدای صف عناصر رو انتخاب کن و ترتیب توپولوژیکی گراف بدست میاد
زمان این روال ضریب ثابتی از اجرای DFS هست
اینو میدونم.
منظورم مرتبه ی الگوریتمی هست که نوشتم.
این الگوریتم اینجوریه که میاد گره ای رو که درجه ورودیش صفر هست رو پیدا میکنه و حذف میکنه و.....
۰
ارسال: #۴
RE: مرتبه زمانی مرتب سازی توپولوژیک از روشی دیگر
(۲۹ آبان ۱۳۹۳ ۰۳:۱۳ ب.ظ)Ametrine نوشته شده توسط: تو کتاب های پارسه و مدرسان یه روش دیگه هم علاوه بر استفاده از DFS توضیح داده شده.
تو هر کتاب مرتبه ی این روش رو متفاوت نوشته!
کدوم درسته؟
مدرسان : [tex]O(V^2)[/tex]
پارسه : [tex]O(V E)[/tex]
فک کنم یکیشون بر حسب ماتریس مجاورت گفته یکی دیگه بر حسب لیست مجاورتی.
( O(v+e نباید باشه، چون پیچیدگی dfs تتا هستش نه O
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close