Khóa học Python từ Cơ bản đến Nâng cao

Bài 12.1 - Biểu diễn đồ thị bằng Adjacency List trong Python

Trong lập trình, biểu diễn dữ liệu dưới dạng đồ thị (graph) là một trong những kỹ năng cực kỳ quan trọng. Có nhiều cách để lưu trữ một đồ thị, nhưng danh sách kề (adjacency list) là một trong những cách phổ biến nhất, đơn giản và hiệu quả.

Đồ thị là gì?

• Đồ thị (graph) gồm tập hợp các đỉnh (nodes/vertices) và các cạnh (edges) kết nối chúng.
• Có thể là:
  • Đồ thị vô hướng (undirected): cạnh không có hướng.
  • Đồ thị có hướng (directed): cạnh có hướng đi từ một đỉnh đến đỉnh khác.
  • Có trọng số hoặc không trọng số.

Adjacency List là gì?

Đây là cách lưu trữ mà mỗi đỉnh sẽ ánh xạ đến một danh sách các đỉnh kề với nó.

Ví dụ:
Giả sử bạn có đồ thị vô hướng với các cạnh:

A - B
A - C
B - D
C - D

Danh sách kề sẽ là:

{
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Triển khai bằng Python

Ví dụ 1: Đồ thị vô hướng không trọng số

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Giải thích: Mỗi khóa là một đỉnh, giá trị là danh sách các đỉnh kề với nó.

Tạo đồ thị từ danh sách cạnh

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('C', 'D')
]

graph = {}

for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)  # Vì là đồ thị vô hướng

Giải thích: Duyệt qua từng cạnh (u, v), thêm v vào danh sách kề của u, và ngược lại.

Ví dụ 2: Đồ thị có hướng

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('C', 'D')
]

graph = {}

for u, v in edges:
    graph.setdefault(u, []).append(v)

Giải thích: Không thêm v -> u vì là đồ thị có hướng.

Duyệt đồ thị (DFS & BFS)

DFS với adjacency list:

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start)

    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Giải thích: Dùng đệ quy để đi sâu vào các đỉnh kề chưa được thăm.

BFS với adjacency list:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph.get(node, []))

Giải thích: BFS duyệt theo chiều rộng, sử dụng hàng đợi (queue).

Ví dụ tổng hợp

edges = [
    ('A', 'B'),
    ('A', 'C'),
    ('B', 'D'),
    ('C', 'D')
]

# Tạo adjacency list
graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)

print("DFS:")
dfs(graph, 'A')

print("\nBFS:")
bfs(graph, 'A')

Kết quả:

DFS:
A
B
D
C

BFS:
A
B
C
D

Ưu điểm của adjacency list

• Tiết kiệm bộ nhớ: Chỉ lưu các cạnh thực sự tồn tại.
• Hiệu quả cho đồ thị thưa (sparse graphs).
• Dễ sử dụng và cập nhật.

Lưu ý

• Nếu bạn cần kiểm tra nhanh xem 2 đỉnh có nối với nhau không, bạn cần duyệt danh sách kề. Với bài toán có nhiều truy vấn như vậy, bạn có thể dùng adjacency matrix (ma trận kề) thay vì list.
• Với đồ thị có trọng số, ta có thể lưu dưới dạng:

  graph = {
    'A': [('B', 5), ('C', 2)],
    'B': [('A', 5), ('D', 1)],
    ...
  }
  

Tổng kết

• Adjacency list là cách biểu diễn đồ thị phổ biến, đơn giản và hiệu quả.
• Bạn có thể sử dụng cấu trúc dữ liệu này để cài đặt các thuật toán như: DFS, BFS, Dijkstra, Topological Sort,...
• Hãy luyện tập bằng cách tự tạo đồ thị từ input và duyệt qua nó bằng các thuật toán đã học.