فهرست مجاورت

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