فهرست همسایگی
در نظریهُ گراف یک فهرست همسایگی نمایش همهٔ یال‌های یک گراف به صورت مجموعه‌ای از فهرست‌هاست، اگر گراف بدون جهت باشد، هر واحد از این فهرست‌ها یک مجموعه از دو گره شامل دو سر یال مربوطه است.
کاربرد در علوم رایانه
نمایش فهرست همسایگی یک گراف (G=(V,E شامل یک آرایه‌ی Adj از |V| فهرست است، یعنی به ازای هر رأس در V یک فهرست. برای هر رأس u در مجموعه رأس‌های V، فهرستِ همسایگی [Adj[u شامل همهٔ رأس‌های v است به طوری که یال (u,v) در E وجود داشته باشد. به عبارتی دیگر، [Adj[u دربردارندهٔ همهٔ رأس‌هایی است که یک یال از u به آن‌ها در گراف G وجود دارد. این رأس‌ها در فهرست همسایگی با ترتیبی دلخواه چیده شده‌اند. شکل 1.b نمایش فهرست همسایگیِ گراف بدون جهتِ نشان داده شده در شکل 1.a است. مشابهاً شکل 2.b نمایش فهرست همسایگی گرافِ جهت‌دار نشان داده شده در شکل 2.a است.
خصوصیات فهرست همسایگی
اگر G یک گراف جهت‌دار باشد، مجموع طول‌های همه‌ی فهرست‌های همسایگی برابر با |E| است، چرا که یالی به شکل (u,v) با ظاهر شدنِ v در[Adj[u نمایش داده می‌شود. اما اگر G بدون جهت باشد، مجموع طول‌های همه‌ی فهرست‌های همسایگی برابر با «دوبرابرِ» |E|است، چرا که یالی بدون جهت به شکل (u,v) با ظاهر شدنِ v در [Adj[u و u در [Adj[v نمایش داده می‌شود. برای هر دو حالت (جهت دار و بدون جهت)، فهرست همسایگی ویژگی مطلوبی دارد و آن اینکه حافظهٔ مورد نیاز آن(Ѳ(V+E است.
نارسایی‌های فهرست همسایگی
یک اشکال عمدهٔ فهرست‌های همسایگی این است که راه سریع تری برای اینکه بدانیم یال داده شدهٔ (u,v) در گراف هست یا نه، وجود ندارد جزاینکه در فهرست [Adj[u به دنبال v بگردیم. این اشکال می‌تواند با استفاده از نمایش ماتریس همسایگی گراف اصلاح شود اما به هزینهٔ استفاده از حافظهٔ بیشتر!
منابع
- توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین (2001), "Chapter 26", مقدمه‌ای بر الگوریتم‌ها (2nd edition ed.), MIT Press and McGraw-Hill, p. 696–697, ISBN 0-262-03293-7