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

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

ارسال:
  

homa پرسیده:

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

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

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

۰
ارسال:
  

pos پاسخ داده:

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

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

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

ارسال:
  

homa پاسخ داده:

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

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

۰
ارسال:
  

pos پاسخ داده:

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

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



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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