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

درجه ورودی راس در گراف

ارسال:
  

homa پرسیده:

درجه ورودی راس در گراف

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

لطفا راه حلی که جواب رو بدست آورید رو توضیح بدین
ممنون

۰
ارسال:
  

pos پاسخ داده:

درجه ورودی راس در گراف

توی لیست مجاورتی ما یک لیست داریم که شامل |v| راس گراف هست. هر راس هم یک لیست داره رئوس مجاور با اون رئس درش نگهداری می شوند که اندازه اش برابر با درجه درجه اون راس هست. خوب برای حل این مسئله باید تمام عناصر را بررسی که کنیم که تعدادشان میشه تعداد رئوسمان بعلاوه درجه هر راس یعنی درجه کل گراف که برابر با ۲e هست پس میشه:
O(v+2e)=O(v+E)

۰
ارسال:
  

mfXpert پاسخ داده:

درجه ورودی راس در گراف

اگر دنبال تعیین درجه ورودی راسی مثل w باشیم باید تمام لیست های مجاورتی رو بگردیم و تعداد گره هایی که مقدار w دارن رو بشمریم

ارسال:
  

homa پاسخ داده:

RE: درجه ورودی راس در گراف

(۰۵ دى ۱۳۹۰ ۰۸:۵۰ ب.ظ)mfXpert نوشته شده توسط:  اگر دنبال تعیین درجه ورودی راسی مثل w باشیم باید تمام لیست های مجاورتی رو بگردیم و تعداد گره هایی که مقدار w دارن رو بشمریم
پس مرتبه زمانیش دقیقا چند میشه؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

pos پاسخ داده:

درجه ورودی راس در گراف

O(V+2E) میشه؟



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) ss311 ۰ ۶۵۵ ۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ
آخرین ارسال: ss311
  تعداد مسیرها در گراف ss311 ۰ ۶۱۶ ۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ
آخرین ارسال: ss311
  فاصله دو راس(دکتری ۹۷) ss311 ۱ ۷۱۳ ۱۷ خرداد ۱۳۹۸ ۰۶:۱۱ ب.ظ
آخرین ارسال: Jooybari
  طراحی گرافیکی simaakbari ۰ ۸۴۲ ۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ
آخرین ارسال: simaakbari
  کوتاه ترین مسیر در گراف Sanazzz ۳ ۱,۵۹۱ ۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ
آخرین ارسال: Sanazzz
  درخواست کتاب شبکه کراس راس ویرایش هفتم fallah_o68 ۱ ۱,۹۰۱ ۰۷ مهر ۱۳۹۷ ۱۲:۱۲ ق.ظ
آخرین ارسال: mraict@gmail.com
  کتاب خوب در باره نظریه گراف ماهی ۲۵۸ ۰ ۷۴۸ ۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ
آخرین ارسال: ماهی ۲۵۸
  تعداد گره های برگ با توجه به درجه نودها rad.bahar ۱ ۱,۰۹۴ ۱۰ تیر ۱۳۹۷ ۰۹:۳۹ ب.ظ
آخرین ارسال: سید علی اصغر
  یافتن مسیر در گراف کامل دو بخشی Sepideh96 ۳ ۱,۳۵۷ ۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ
آخرین ارسال: αɾια
  رنگ آمیزی راسهای گراف ss311 ۲ ۹۳۳ ۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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