فهرست مجاورت

نمایش فهرست مجاورت یک گراف (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 بگردیم. این اشکال می‌تواند با استفاده از نمایش ماتریس مجاورت گراف اصلاح شود اما به هزینهٔ استفاده از حافظهٔ بیشتر!