۰
subtitle
ارسال: #۱
  
لیست مجاورتی ؟؟؟
سلام
یه قسمتی هست تو کتاب پورانه من درکش نکردم می نویسم اگه ممکنه کسی فهمید توضیح بده لطفا وممنون پیشاپیش
برای صرفه جویی در حافظه می توان روشی پیشنهاد کرد که link ها ذخیره نشوند. یک آرایه [n+2e+1] نود ، می توان استفتده کرد که نود i نقطه ی شروع لیست برای راس i را نشان می دهد و نود n به n+2e+1 مقدار دهی شده ، پس رئوسی که با راس i مجاور هستند در نودi تا نود ۱-(i+1) ذخیره شده اند.
بعد زیر ش یه مثال هم زده
ممنون می شم راهنمایی کنید
یه قسمتی هست تو کتاب پورانه من درکش نکردم می نویسم اگه ممکنه کسی فهمید توضیح بده لطفا وممنون پیشاپیش
برای صرفه جویی در حافظه می توان روشی پیشنهاد کرد که link ها ذخیره نشوند. یک آرایه [n+2e+1] نود ، می توان استفتده کرد که نود i نقطه ی شروع لیست برای راس i را نشان می دهد و نود n به n+2e+1 مقدار دهی شده ، پس رئوسی که با راس i مجاور هستند در نودi تا نود ۱-(i+1) ذخیره شده اند.
بعد زیر ش یه مثال هم زده
ممنون می شم راهنمایی کنید
۳
ارسال: #۲
  
RE: لیست مجاورتی ؟؟؟
سلام .
با توجه به توضیحی که توی کتاب نوشته روال کار به این صورت که :
در ابتدا همون طوری که گفته یک آرایه به طول n+2e+1 تشکیل میدیم که برای این مثال کتاب میشه ۲۳ و به ازای تعداد گره های گراف تعداد عناصر اولیه آرایه رو به رئوس گراف تخصیص میدیم که مثلا اینجا میشه از خانه ی ۰ تا ۷ آرایه {رئوس گراف G3 از ۰ تا ۷ شماره گذاری شدن}.
حالا از خانه ی ۲+۷ یعنی نهم رو به ترتیب به همسایه های رئوس گراف تخصیص میدیم . مثلا برای راس ۰ همسایه هاش رئوس ۱و۲ هستن پس توی خانه های ۹ و ۱۰ شماره ۱و۲ قرار میدیم پس همسایه های گره صفر از خانه ی ۹ شروع و تا ۱۰ ادامه دارن. خب حالا توی خانه ی شماره صفر آرایه{که مطابق راس ۰ هست} عدد ۹ رو ذخیره میکنیم یعنی همون خونه ی آغازین همسایه هاش و برای بقیه رئوس هم به همین شکل ادامه میدیم :
همسایه های راس شماره ۰ : خانه های ۹و۱۰
همسایه های راس شماره ۱ : خانه های ۱۱و۱۲
همسایه های راس شماره ۲ : خانه های ۱۳و۱۴
همسایه های راس شماره ۳ : خانه های ۱۵و۱۶
همسایه های راس شماره ۴ : خانه های ۱۷
همسایه های راس شماره ۵ : خانه های ۱۸و۱۹
همسایه های راس شماره ۶ : خانه های ۲۰و۲۱
همسایه های راس شماره ۷ : خانه های ۲۲
مثل خونه ۰ برای بقیه خونه های ۱تا ۷ هم شماره خانه ی شروع همسایه ها رو داخلش مینویسیم.
[tex]node[0]=9[/tex]
[tex]node[1]=11[/tex]
[tex]node[2]=13[/tex]
[tex]node[3]=15[/tex]
[tex]node[4]=17[/tex]
[tex]node[5]=18[/tex]
[tex]node[6]=20[/tex]
[tex]node[7]=22[/tex]
فقط یه نکته ای موند راجب خونه ۸ که داخل اون تعداد خونه های آرایه رو نوشته در واقع این خونه یه جور پایان کار پیمایش رو واسه الگوریتم هایی که ار این آرایه استفاده میکنن مشخص میکنه و همچنین با توجه به وجود این خونه اون فرمولی هم که گفته میتونیم با استفاده ازش مستقیما خانه ی ابتدا و انتهای همسایه های هر راس رو پیدا کرد مثلا برای راس ۰ از [tex]node[i] , node[i 1]-1[/tex] شامل خونه های رئوس مجاورشه که همون ۹ تا ۱۰ میشه.
با توجه به توضیحی که توی کتاب نوشته روال کار به این صورت که :
در ابتدا همون طوری که گفته یک آرایه به طول n+2e+1 تشکیل میدیم که برای این مثال کتاب میشه ۲۳ و به ازای تعداد گره های گراف تعداد عناصر اولیه آرایه رو به رئوس گراف تخصیص میدیم که مثلا اینجا میشه از خانه ی ۰ تا ۷ آرایه {رئوس گراف G3 از ۰ تا ۷ شماره گذاری شدن}.
حالا از خانه ی ۲+۷ یعنی نهم رو به ترتیب به همسایه های رئوس گراف تخصیص میدیم . مثلا برای راس ۰ همسایه هاش رئوس ۱و۲ هستن پس توی خانه های ۹ و ۱۰ شماره ۱و۲ قرار میدیم پس همسایه های گره صفر از خانه ی ۹ شروع و تا ۱۰ ادامه دارن. خب حالا توی خانه ی شماره صفر آرایه{که مطابق راس ۰ هست} عدد ۹ رو ذخیره میکنیم یعنی همون خونه ی آغازین همسایه هاش و برای بقیه رئوس هم به همین شکل ادامه میدیم :
همسایه های راس شماره ۰ : خانه های ۹و۱۰
همسایه های راس شماره ۱ : خانه های ۱۱و۱۲
همسایه های راس شماره ۲ : خانه های ۱۳و۱۴
همسایه های راس شماره ۳ : خانه های ۱۵و۱۶
همسایه های راس شماره ۴ : خانه های ۱۷
همسایه های راس شماره ۵ : خانه های ۱۸و۱۹
همسایه های راس شماره ۶ : خانه های ۲۰و۲۱
همسایه های راس شماره ۷ : خانه های ۲۲
مثل خونه ۰ برای بقیه خونه های ۱تا ۷ هم شماره خانه ی شروع همسایه ها رو داخلش مینویسیم.
[tex]node[0]=9[/tex]
[tex]node[1]=11[/tex]
[tex]node[2]=13[/tex]
[tex]node[3]=15[/tex]
[tex]node[4]=17[/tex]
[tex]node[5]=18[/tex]
[tex]node[6]=20[/tex]
[tex]node[7]=22[/tex]
فقط یه نکته ای موند راجب خونه ۸ که داخل اون تعداد خونه های آرایه رو نوشته در واقع این خونه یه جور پایان کار پیمایش رو واسه الگوریتم هایی که ار این آرایه استفاده میکنن مشخص میکنه و همچنین با توجه به وجود این خونه اون فرمولی هم که گفته میتونیم با استفاده ازش مستقیما خانه ی ابتدا و انتهای همسایه های هر راس رو پیدا کرد مثلا برای راس ۰ از [tex]node[i] , node[i 1]-1[/tex] شامل خونه های رئوس مجاورشه که همون ۹ تا ۱۰ میشه.
۰
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
اشتراک لیست | homa | ۱۵ | ۹,۲۹۱ |
۲۴ بهمن ۱۳۹۰ ۱۲:۲۱ ق.ظ آخرین ارسال: Maryam-X |
|
لیست مجاورتی | homa | ۱ | ۲,۳۴۹ |
۱۳ آذر ۱۳۹۰ ۰۹:۱۷ ب.ظ آخرین ارسال: مازیار صفایی |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close