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

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

ارسال:
  

homa پرسیده:

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

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

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

۰
ارسال:
  

pos پاسخ داده:

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

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

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

ارسال:
  

homa پاسخ داده:

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

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

۰
ارسال:
  

pos پاسخ داده:

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

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



پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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