اگر یک گراف به صورت لیست مجاورتی پیاده سازی شود. چه زمانی طول میکشد تا درجه ورودی یک راس را محاسبه کنیم؟؟؟
لطفا راه حلی که جواب رو بدست آورید رو توضیح بدین
ممنون
اگر دنبال تعیین درجه ورودی راسی مثل w باشیم باید تمام لیست های مجاورتی رو بگردیم و تعداد گره هایی که مقدار w دارن رو بشمریم
(۰۵ دى ۱۳۹۰ ۰۸:۵۰ ب.ظ)mfXpert نوشته شده توسط: اگر دنبال تعیین درجه ورودی راسی مثل w باشیم باید تمام لیست های مجاورتی رو بگردیم و تعداد گره هایی که مقدار w دارن رو بشمریمپس مرتبه زمانیش دقیقا چند میشه؟؟؟
O(V+2E) میشه؟
بهترین کار اینه که لیست مجاورتی معکوس هم برای گرافهای جهت دار نگه داشت اما برای بدست اوردن درجه ورودی از روی لیست مجاورتی به صورت زیر عمل میکنیم .
درجه ورودی راس v برابر است با:
در تمام لیستها بجز لیست v جستجو کرده و راسهایی که شامل v هستنند را میشماریم .
از انجا که تعداد [tex]\left | V \right | - 1[/tex] لیست داریم(بجز لیستv)و هر لیست در بدترین حالت شامل [tex]\left | V \right |[/tex] راس هست(گراف کامل) لذا در بدترین حالت از مرتبه [tex]V^{2}[/tex] اما با لیست مجاورتی معکوس مرتبه ان همان [tex]O(|V|)[/tex]
میباشد
(۰۶ دى ۱۳۹۰ ۱۱:۵۴ ب.ظ)mjjoon نوشته شده توسط:Algorithm for in-degree
۱ For each u in V do
۲ in-deg[u] = 0
۳ For each u in V do
۴ for each v in Adj[u] do
۵ in-deg[v] = in-deg[v] + 1 // count # of edges to v
Steps 1 and 2 take O(|V|).
Steps 3 to 5 take O(max(|V|, |E|)) = O(|V| + |E|) time, since we have to scan all the adjacency lists (even if they
may be all empty), and there are |V| lists. Moreover, the sum of the lengths of all adjacency lists is O(|E|). Each
element in adjacency lists swill be examined once.
∴ O(|E| + |V|) + O(|V|) = O(|E| + |V|)
میشه بگید خط ۳ تا ۵ چه جوری میشه[tex]O(\left | E \right | \left | V \right |)[/tex]
(۰۵ دى ۱۳۹۰ ۰۹:۱۶ ب.ظ)pos نوشته شده توسط: O(V+2E) میشه؟من خودم نمیدونم چقد میشه ولی فکر میکنم باید خطی باشه و نمیدونم چه جوری
شما چه جوری بدست آوردید؟میشه توضیح بدید
توی لیست مجاورتی ما یک لیست داریم که شامل |v| راس گراف هست. هر راس هم یک لیست داره رئوس مجاور با اون رئس درش نگهداری می شوند که اندازه اش برابر با درجه درجه اون راس هست. خوب برای حل این مسئله باید تمام عناصر را بررسی که کنیم که تعدادشان میشه تعداد رئوسمان بعلاوه درجه هر راس یعنی درجه کل گراف که برابر با ۲e هست پس میشه:
O(v+2e)=O(v+E)