نمایش لیست مجاورت (Adjacency List Representation)

لیست مجاورت یک ساختار داده است که برای نمایش گراف‌ها استفاده می‌شود. در این روش، هر رأس (گره) گراف، لیستی از رأس‌های مجاور خود (یعنی رأس‌هایی که با آن یال دارند) را ذخیره می‌کند. در این مقاله قصد داریم تا این مفهوم را با مثال های تصویری شرح دهیم.

• لیست مجاورت برای گراف جهت‌دار
• لیست مجاورت برای گراف بدون جهت
• لیست مجاورت برای گراف جهت‌دار و وزن‌دار
• لیست مجاورت برای گراف بدون جهت و وزن‌دار
• ویژگی‌های لیست مجاورت
• کاربردهای لیست مجاورت
• مزایای استفاده از لیست مجاورت
• معایب استفاده از لیست مجاورت

۱. لیست مجاورت برای گراف جهت‌دار
(Directed Graph)

فرض کنید مشابه شکل اول، یک گراف جهت‌دار و بدون وزن با ۳ رأس و ۳ یال داریم. در این حالت، لیست مجاورت گراف به صورت زیر نمایش داده می‌شود:

# تابعی برای افزودن یال بین دو رأس
def addEdge(adj, u, v):
    adj[u].append(v)

# تابعی برای نمایش لیست مجاورت
def displayAdjList(adj):
    for i in range(len(adj)):
        print(f"{i}: ", end="")
        for j in adj[i]:
            print(f"{j} ", end="")
        print()

def main():
    # ایجاد گراف با ۳ رأس
    V = 3
    adj = [[] for _ in range(V)]

    # افزودن یال‌ها
    addEdge(adj, 1, 0)
    addEdge(adj, 1, 2)
    addEdge(adj, 2, 0)

    print("Adjacency List Representation:")
    displayAdjList(adj)

if __name__ == "__main__":
    main()

خروجی:

Adjacency List Representation:
0: 
1: 0 2 
2: 0 

در این مثال، رأس ۱ به رأس‌های ۰ و ۲ متصل است، و رأس ۲ به رأس ۰ متصل می‌باشد.

۲. لیست مجاورت برای گراف بدون جهت
(Undirected Graph)

در گراف‌های بدون جهت، هر یال ارتباط دوطرفه دارد. بنابراین اگر یالی بین رأس‌های ۱ و ۲ وجود داشته باشد، هم در لیست رأس ۱ و هم در لیست رأس ۲ ذخیره می‌شود:

def addEdge(adj, u, v):
    adj[u].append(v)
    adj[v].append(u)

def displayAdjList(adj):
    for i in range(len(adj)):
        print(f"{i}: ", end="")
        for j in adj[i]:
            print(f"{j} ", end="")
        print()

def main():
    V = 3
    adj = [[] for _ in range(V)]

    addEdge(adj, 1, 0)
    addEdge(adj, 1, 2)
    addEdge(adj, 2, 0)

    print("Adjacency List Representation:")
    displayAdjList(adj)

if __name__ == "__main__":
    main()

خروجی:

Adjacency List Representation:
0: 1 2 
1: 0 2 
2: 1 0 

۳. لیست مجاورت برای گراف جهت‌دار و وزن‌دار
(Directed & Weighted Graph)

در گراف‌های وزن‌دار، هر یال علاوه بر مقصد، یک مقدار وزن نیز دارد. در این حالت هر یال به‌صورت یک زوج مرتب (رأس مقصد، وزن) در لیست ذخیره می‌شود.

def addEdge(adj, u, v, w):
    adj[u].append((v, w))

def displayAdjList(adj):
    for i in range(len(adj)):
        print(f"{i}: ", end="")
        for j in adj[i]:
            print(f"{{{j[0]}, {j[1]}}} ", end="")
        print()

def main():
    V = 3
    adj = [[] for _ in range(V)]

    addEdge(adj, 1, 0, 4)
    addEdge(adj, 1, 2, 3)
    addEdge(adj, 2, 0, 1)

    print("Adjacency List Representation:")
    displayAdjList(adj)

if __name__ == "__main__":
    main()

خروجی:

Adjacency List Representation:
0: 
1: {0, 4} {2, 3} 
2: {0, 1} 

۴. لیست مجاورت برای گراف بدون جهت و وزن‌دار
(Undirected & Weighted Graph)

در گراف‌های بدون جهت و وزن‌دار، هر یال بین دو رأس، با مقدار وزن در هر دو جهت ذخیره می‌شود:

def addEdge(adj, u, v, w):
    adj[u].append((v, w))
    adj[v].append((u, w))

def displayAdjList(adj):
    for i in range(len(adj)):
        print(f"{i}: ", end="")
        for j in adj[i]:
            print(f"{{{j[0]}, {j[1]}}} ", end="")
        print()

def main():
    V = 3
    adj = [[] for _ in range(V)]

    addEdge(adj, 1, 0, 4)
    addEdge(adj, 1, 2, 3)
    addEdge(adj, 2, 0, 1)

    print("Adjacency List Representation:")
    displayAdjList(adj)

if __name__ == "__main__":
    main()

خروجی:

Adjacency List Representation:
0: {1, 4} {2, 1} 
1: {0, 4} {2, 3} 
2: {1, 3} {0, 1} 

ویژگی‌های لیست مجاورت (Characteristics)

• در نمایش لیست مجاورت، لیستی است که در دل خود شامل لیست های دیگر می شود.
• هر رأس دارای لیستی است که شامل تمام همسایه‌های آن رأس می‌باشد.
• اندازه‌ی کل ساختار داده برابر با تعداد رأس‌های گراف است.
• برای یافتن همه‌ی همسایه‌های یک رأس فقط به زمان O(n) (تعداد همسایگان آن رأس) نیاز داریم.

کاربردهای لیست مجاورت (Applications)

• در بسیاری از الگوریتم‌های گراف مانند الگوریتم دایکسترا (Dijkstra)، جستجوی عمق‌اول (DFS) و جستجوی عرض‌اول (BFS)، نمایش به‌صورت لیست مجاورت باعث افزایش سرعت اجرا می‌شود.
• این روش پرتکرارترین و پرکاربردترین نمایش گراف است، زیرا دسترسی و پیمایش تمام یال‌ها در آن ساده و سریع است.

مزایای لیست مجاورت (Advantages)

• ساختاری ساده و قابل‌درک دارد.
• برای گراف‌های خلوت (Sparse Graphs)، فضای حافظه‌ی کمتری نسبت به ماتریس مجاورت نیاز دارد.
• پیمایش یال‌های گراف در این روش بسیار آسان و کارآمد است.
• افزودن یک رأس جدید نسبت به روش ماتریسی ساده‌تر است.
• بسیاری از الگوریتم‌های گراف مانند BFS و DFS در این نمایش با زمان خطی (O(V+E)) اجرا می‌شوند. همچنین الگوریتم‌های Prim و Dijkstra نیز در این روش سریع‌تر پیاده‌سازی می‌شوند.

معایب لیست مجاورت (Disadvantages)

• بررسی اینکه آیا بین دو رأس خاص یالی وجود دارد یا نه، زمان‌بر است زیرا باید لیست همسایه‌ها را پیمایش کنیم.
• برای گراف‌های تراکم‌بالا (Dense Graphs) چندان مناسب نیست، چون تعداد یال‌ها زیاد است و دسترسی مستقیم در آن دشوارتر از ماتریس مجاورت است.