زمان کنونی: ۱۵ آذر ۱۴۰۳, ۱۱:۲۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

مرتب سازی توپولوژیکی

ارسال:
  

irpersian20 پرسیده:

مرتب سازی توپولوژیکی

با سلام
این مرتب سازی چرا باید حتما گراف جهت دار بدون دور باشد؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

artmiss پاسخ داده:

RE: مرتب سازی توپولوژیکی

در مرتب سازی توپولوژیکی هر گره زمانی ملاقات میشود که گره های پیشنیاز آن ملاقات شده باشد.
اصطلاح پیشنیاز در اینجا به این معناست: که وقتی از یک گره یالی به گره دیگری داریم گره ای که یال از آن خارج شده پیشنیاز گره ای است که یال به آن وارد میشود.
حالا چرا باید جهت دار باشه ؟ چون در این صورت بحث پیشنیاز منتفی میشه. یا میشه گفت یالی که جهت نداره دو طرفست در اینصورت هر دو پیشنیاز همند که باز هم نمیشه از طریق مرتب سازی توپولوژیکی ترتیبی برای انتخاب این دو گره داشت.
چرا نباید دور داشته باشه؟ شما در نظر بگیر سه راس که دور دارند به هیچ طریقی نمیشه از این سه راس راسی رو انتخاب کرد که پیشنیازاش برطرف شده باشه. حالا همین دورو گسترش بدی بازم میبینی که به هیچ طریقی یال های مربوط به دور قابل حذف نیستن.
نقل قول این ارسال در یک پاسخ

ارسال:
  

irpersian20 پاسخ داده:

RE: مرتب سازی توپولوژیکی

(۱۶ اردیبهشت ۱۳۹۴ ۰۳:۰۶ ق.ظ)artmiss نوشته شده توسط:  در مرتب سازی توپولوژیکی هر گره زمانی ملاقات میشود که گره های پیشنیاز آن ملاقات شده باشد.
اصطلاح پیشنیاز در اینجا به این معناست: که وقتی از یک گره یالی به گره دیگری داریم گره ای که یال از آن خارج شده پیشنیاز گره ای است که یال به آن وارد میشود.
حالا چرا باید جهت دار باشه ؟ چون در این صورت بحث پیشنیاز منتفی میشه. یا میشه گفت یالی که جهت نداره دو طرفست در اینصورت هر دو پیشنیاز همند که باز هم نمیشه از طریق مرتب سازی توپولوژیکی ترتیبی برای انتخاب این دو گره داشت.
چرا نباید دور داشته باشه؟ شما در نظر بگیر سه راس که دور دارند به هیچ طریقی نمیشه از این سه راس راسی رو انتخاب کرد که پیشنیازاش برطرف شده باشه. حالا همین دورو گسترش بدی بازم میبینی که به هیچ طریقی یال های مربوط به دور قابل حذف نیستن.

ممنون از پاسخ خوبتون
بعد یک سایت زده بود از روش DFS هم میشه حساب کرد . اون چطوره؟

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

gunnersregister پاسخ داده:

RE: مرتب سازی توپولوژیکی

سه رنگ به نودها میدیم: سفید (ملاقات نشده) خاکستری (قبلا ملاقات شده) سیاه (عدم امکان پیشروی از طریق این نود)

به روش DFS گراف رو پیمایش میکنیم. به هر نودی که بار اول میرسیم ، اگه سفید باشه یه زمان ملاقات اولیه d میدیم و اونو خاکستری میکنیم. اگه سیاه باشه اونو ملاقات نمیکنیم. اگه خاکستری باشه و امکان رفتن به نود دیگه ای از طریق این نود باشه این کار رو میکنیم و اگه امکان رفتن به نود دیگری از این نود ممکن نباشه اونو سیاه میکنیم و زمان اتمام ملاقات f رو براش تعیین میکنیم و به نود قبل از اوون (پدرش) برمیگردیم.
این کار رو تا هنگامی ادامه میدیم که تموم نودها سیاه بشن و زمان شروع ملاقات d و زمان اتمام ملاقات f تعیین بشه.
حالا یه ترتیب توپولوژیکی براساس زمان صعودی شروع ملاقاتها d داریم.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۳۵ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۲۶ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۶۱۴ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۲۳۰ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۲,۶۲۵ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work
  برگ برگ سازی Sanazzz ۱ ۲,۱۶۴ ۱۳ فروردین ۱۳۹۸ ۰۸:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  راهنمایی برای انتخاب موضوع قابل پیاده سازی در زمینه بیگ دیتا برای پایان نامه one hacker alone ۱ ۳,۳۰۲ ۱۸ بهمن ۱۳۹۷ ۰۶:۳۶ ب.ظ
آخرین ارسال: Happiness.72
  ابزار شبیه سازی پروتکل های امنیت شبکه - ابزار اسکایتر mavin1200 ۰ ۲,۳۸۳ ۰۱ آذر ۱۳۹۷ ۰۱:۵۰ ق.ظ
آخرین ارسال: mavin1200
  بهینه سازی چند هدفه فازی استوارژنتیک alighasemi ۰ ۲,۱۳۰ ۲۴ آبان ۱۳۹۷ ۰۴:۵۵ ب.ظ
آخرین ارسال: alighasemi
  منبع درس شبیه سازی کامپیوتری sepid ۵ ۷,۰۰۲ ۲۱ مهر ۱۳۹۷ ۱۲:۱۳ ق.ظ
آخرین ارسال: The BesT

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close