فهرست مجاورت

در نظریهُ گراف یک فهرست مجاورت نمایش همهٔ یال‌های یک گراف به صورت مجموعه‌ای از فهرست‌هاست، اگر گراف بدون جهت باشد، هر واحد از این فهرست‌ها یک مجموعه از دو گره شامل دو سر یال مربوطه است.

کاربرد در علوم رایانه

شکل 1

شکل 2

نمایش فهرست مجاورت یک گراف (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, Ronald L. Rivest, and کلیفورد استین. “Chapter 26”. In مقدمه‌ای بر الگوریتم‌ها. 2nd edition ed. MIT Press and McGraw-Hill, 2001. 696–697. ISBN 0-262-03293-7.