Chọn cách biểu diễn đồ thị từ các mối quan hệ

Lan quản lý 5 trạm sách và 5 tuyến đường hai chiều giữa chúng. Một trạm mới có thể chưa nối với tuyến nào. Lan muốn biết mỗi trạm nối trực tiếp với những trạm nào, rồi kiểm tra nhanh một cặp trạm. Nếu chỉ lưu tên các tuyến trên giấy, mỗi câu hỏi lại phải dò từ đầu.

Một đồ thị mô tả các đối tượng và quan hệ giữa chúng

Mỗi trạm của Lan là một đỉnh (vertex). Mỗi tuyến nối hai trạm là một cạnh (edge). Tập các đỉnh cùng tập các cạnh tạo thành đồ thị (graph). Số đỉnh thường ký hiệu là n, số cạnh là m. Hai đỉnh được gọi là kề nhau (adjacent) khi có cạnh nối trực tiếp chúng.

Lan đánh số trạm từ 1 đến 5. Dữ liệu gồm các cặp 1 2, 1 3, 2 4, 3 4, 4 5. Hình sau dùng đúng năm cặp đó. Mỗi nét nối biểu diễn một tuyến, không phải khoảng cách trên bản đồ.

Trạm 1 kề trạm 2 và 3. Trạm 5 chỉ kề trạm 4. Có thể đi từ 1 đến 5 qua các tuyến, nhưng 1 và 5 không kề nhau. Một đỉnh không thuộc cạnh nào là đỉnh cô lập (isolated vertex). Nó vẫn thuộc đồ thị nếu đề đã cho số đỉnh.

Bạn cần xác định quan hệ trước khi chọn cấu trúc. Hai người kết bạn thường tạo quan hệ hai chiều. Điều kiện học bài A trước bài B chỉ cho phép đi từ A sang B. Một tuyến đường cũng có thể có chiều dài; khi đó mỗi cạnh mang thêm một giá trị.

Đoạn sau giữ nguyên các cạnh đầu vào để quan sát dữ liệu. Nó đọc n, m, rồi đọc đúng m cặp.

5 5
1 2
1 3
2 4
3 4
4 5

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v = map(int, input().split())
    edges.append((u, v))
print("so dinh:", n)
print("cac canh:", edges)

so dinh: 5
cac canh: [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]

Mỗi cặp chứa hai số nguyên, không chứa danh sách mọi tuyến liên tiếp. Chi phí đọc và lưu là O(m) thời gian và O(m) bộ nhớ. Khi m = 5, vòng lặp thực hiện đúng 5 lần. Số đỉnh vẫn được giữ riêng, kể cả khi một đỉnh không xuất hiện trong cặp nào.

Hướng cạnh quyết định cách ghi quan hệ

Trong đồ thị vô hướng (undirected graph), cạnh giữa u và v có thể đi theo cả hai chiều. Trong đồ thị có hướng (directed graph), cạnh u -> v đi từ u đến v. Cạnh ngược v -> u chỉ tồn tại nếu đề cũng cho cạnh đó.

Ví dụ, bốn môn có quan hệ tiên quyết. Cần học môn 1 trước môn 2 và môn 3. Môn 2 lại cần học trước môn 4. Hình vẽ dùng mũi tên theo chiều phải học trước.

Môn 1 có hai cạnh đi ra. Môn 4 có một cạnh đi vào. Không suy ra cạnh 4 -> 2 từ cạnh 2 -> 4. Cũng không tự thêm cạnh 1 -> 4: đó là quan hệ gián tiếp, không phải một cạnh trong dữ liệu.

Đoạn sau lưu các môn học ngay sau mỗi môn. Dòng g[u].append(v) chỉ thêm chiều được cho.

4 3
1 2
1 3
2 4

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
for u in range(1, n + 1):
    print(u, g[u])

1 [2, 3]
2 [4]
3 []
4 []

Danh sách của đỉnh 4 rỗng vì không có cạnh đi ra từ 4. Điều này không có nghĩa là không có cạnh đi vào 4. Nếu cần tìm tiền nhiệm trực tiếp, bạn có thể xây thêm một danh sách theo chiều ngược. Mỗi cạnh phải được đưa vào danh sách phù hợp đúng một lần.

Danh sách kề lưu hàng xóm của từng đỉnh

Danh sách kề (adjacency list) là một danh sách các danh sách. Phần tử g[u] chứa những đỉnh nối trực tiếp từ u. Với cạnh vô hướng u v, bạn thêm v vào g[u] và u vào g[v]. Đây là hai bản ghi cho cùng một cạnh, không phải hai tuyến khác nhau.

Chương trình sau dựng lại hình năm trạm. Thứ tự hàng xóm trong kết quả phụ thuộc thứ tự đọc các cạnh.

5 5
1 2
1 3
2 4
3 4
4 5

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
for u in range(1, n + 1):
    print(u, ":", *g[u])

1 : 2 3
2 : 1 4
3 : 1 4
4 : 2 3 5
5 : 4

Sau khi đọc cạnh 1 2, hàng g[1] có 2 và hàng g[2] có 1. Từng cạnh còn lại được xử lý giống vậy. Do mỗi cạnh xuất hiện ở hai đầu, mọi hàng xóm trực tiếp đều có trong đúng hàng. Các hàng không chứa cạnh không được cho.

Mảng có n + 1 hàng vì các đỉnh đánh số từ 1. Hàng 0 được bỏ trống để nhãn trùng chỉ số. Nếu đề đánh số từ 0 đến n - 1, dùng range(n) và chỉ cần n hàng. Không tự thay đổi nhãn nếu chưa đổi cả đầu vào lẫn đầu ra.

Một lỗi Python thường gặp là nhân danh sách rỗng. Khi đó các hàng cùng trỏ tới một đối tượng. Ví dụ dưới đây cho thấy cập nhật hàng 1 làm hàng 2 cũng thay đổi.

g = [[]] * 4
g[1].append(3)
print(g[1])
print(g[2])
print(g[1] is g[2])

[3]
[3]
True

Tạo từng hàng bằng biểu thức [[] for _ in range(n + 1)] để chúng độc lập. Đoạn sau cập nhật cùng dữ liệu nhưng không làm đổi hàng bên cạnh.

g = [[] for _ in range(4)]
g[1].append(3)
print(g[1])
print(g[2])
print(g[1] is g[2])

[3]
[]
False

Khởi tạo n + 1 hàng tốn O(n). Đọc và thêm m cạnh tốn O(m) lần thêm. Với đồ thị vô hướng có n = 100000, m = 200000, tổng số phần tử hàng xóm là 400000. Bộ nhớ và thời gian dựng có bậc O(n + m), dù chi phí thực tế của từng đối tượng Python vẫn cần tính đến.

Muốn liệt kê hàng xóm của u, bạn chỉ duyệt g[u]. Chi phí bằng số bản ghi trong hàng đó. Nhưng phép v in g[u] có thể phải dò hết hàng. Vì vậy, danh sách kề tốt để liệt kê, còn nhiều câu hỏi kiểm tra cạnh cần cân nhắc cấu trúc khác.

Bậc cho biết số cạnh đi vào hoặc đi ra

Với đồ thị vô hướng không có khuyên, bậc (degree) của một đỉnh là số cạnh kề nó. Trong danh sách kề, bậc bằng len(g[u]) khi mỗi cạnh được thêm hai đầu. Tổng bậc bằng 2m: mỗi cạnh đóng góp một đơn vị cho mỗi đầu mút.

Chương trình sau in bậc theo thứ tự nhãn, kể cả trạm cô lập số 6.

6 5
1 2
1 3
2 4
3 4
4 5

n, m = map(int, input().split())
degree = [0] * (n + 1)
for _ in range(m):
    u, v = map(int, input().split())
    degree[u] += 1
    degree[v] += 1
print(*degree[1:])
print("tong:", sum(degree))

2 2 2 3 1 0
tong: 10

Tổng bậc là 10 vì có 5 cạnh. Hàng của đỉnh 6 bằng 0. Nếu chỉ cần bậc mà không cần danh sách hàng xóm, mảng đếm này tiết kiệm hơn việc lưu từng hàng. Mỗi cạnh được xử lý một lần, nên chi phí là O(n + m) thời gian và O(n) bộ nhớ.

Trong đồ thị có hướng, bán bậc ra (out-degree) đếm cạnh bắt đầu tại đỉnh. Bán bậc vào (in-degree) đếm cạnh kết thúc tại đỉnh. Tổng bán bậc ra bằng m, và tổng bán bậc vào cũng bằng m.

4 3
1 2
1 3
2 4

n, m = map(int, input().split())
incoming = [0] * (n + 1)
outgoing = [0] * (n + 1)
for _ in range(m):
    u, v = map(int, input().split())
    outgoing[u] += 1
    incoming[v] += 1
for u in range(1, n + 1):
    print(u, incoming[u], outgoing[u])

1 0 2
2 1 1
3 1 0
4 1 0

Đỉnh 1 có hai cạnh ra và không có cạnh vào. Đỉnh 4 có một cạnh vào và không có cạnh ra. Đảo hai mảng đếm sẽ trả lời một câu hỏi khác với đề yêu cầu.

Một khuyên (self-loop) là cạnh nối một đỉnh với chính nó. Theo quy ước bậc vô hướng thông dụng, khuyên đóng góp 2 vào bậc. Đoạn thêm hai chiều ở trên cũng thêm hai lần vào cùng một hàng. Với cạnh có hướng u -> u, nó đóng góp một cạnh vào và một cạnh ra.

Cạnh song song (parallel edges) là nhiều cạnh cùng nối một cặp đầu mút theo cùng hướng. Danh sách kề giữ được số lần xuất hiện; một tập hợp chỉ giữ sự hiện diện. Vì vậy hãy đọc kỹ đề nói đếm cạnh, đếm hàng xóm phân biệt hay chỉ hỏi có cạnh.

Trọng số phải đi cùng đúng đầu mút

Trọng số (weight) là dữ liệu gắn với cạnh, chẳng hạn chiều dài hoặc phí. Bạn có thể lưu mỗi hàng xóm dưới dạng tuple gồm (v, w). Với tuyến hai chiều có cùng chi phí, thêm (v, w) vào g[u] và (u, w) vào g[v].

Ví dụ sau cho ba tuyến đường, trong đó giá trị cuối là chiều dài. Đường 1–3 có chiều dài bằng 0; 0 vẫn là một trọng số hợp lệ.

3 3
1 2 7
1 3 0
2 3 4

n, m = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    g[u].append((v, w))
    g[v].append((u, w))
for v, w in g[1]:
    print("den", v, "dai", w)

den 2 dai 7
den 3 dai 0

Mỗi lần lặp cuối lấy đúng một cặp đã lưu. Trọng số 7 đi cùng đỉnh 2, còn trọng số 0 đi cùng đỉnh 3. Cách lưu này không tính đường ngắn nhất; nó chỉ chuẩn bị dữ liệu. Cạnh có hướng chỉ cần thêm vào hàng của đầu xuất phát.

Ma trận kề đổi bộ nhớ lấy truy vấn cạnh trực tiếp

Ma trận kề (adjacency matrix) là bảng hai chiều. Ô a[u][v] cho biết có cạnh từ u sang v hay không. Với đồ thị vô hướng, bạn đánh dấu cả a[u][v] và a[v][u]. Bảng vì thế đối xứng qua đường chéo chính.

Đoạn sau tạo bảng cho bốn đỉnh, rồi trả lời hai câu hỏi có cạnh. Giá trị 1 nghĩa là có cạnh và 0 nghĩa là chưa có cạnh.

4 3
1 2
2 4
3 4

n, m = map(int, input().split())
a = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    a[u][v] = a[v][u] = 1
print(a[1][4])
print(a[2][4])
for u in range(1, n + 1):
    print(*a[u][1:])

0
1
0 1 0 0
1 0 0 1
0 0 0 1
0 1 1 0

Tra một ô theo chỉ số tốn O(1). Muốn liệt kê hàng xóm, bạn phải xét cả n ô trong hàng, kể cả ô không có cạnh. Khởi tạo bảng tốn O(n²) bộ nhớ và thời gian. Khi n = 100000, bảng có khoảng 10 tỷ ô, quá lớn cho giới hạn bộ nhớ thông thường.

Một bảng 0/1 không phân biệt được một cạnh với hai cạnh song song. Nếu cần số cạnh, ô có thể là bộ đếm. Nếu cần lưu trọng số có thể bằng 0, đừng dùng 0 làm dấu vắng cạnh. Bạn có thể dùng None cho ô chưa có cạnh và lưu số nguyên cho cạnh đã cho.

n = 3
a = [[None] * (n + 1) for _ in range(n + 1)]
a[1][2] = 0
print(a[1][2] is not None)
print(a[1][3] is not None)
print(a[1][2])

True
False
0

Ô a[1][2] chứa 0 nên phép kiểm tra có cạnh vẫn đúng. Ô a[1][3] chứa None nên không có cạnh. Nếu có cạnh song song với nhiều trọng số, bạn phải quyết định lưu tất cả hay chỉ một giá trị theo yêu cầu. Ví dụ, bài yêu cầu trọng số nhỏ nhất thì cập nhật ô bằng giá trị nhỏ hơn.

Danh sách cạnh thích hợp khi xử lý từng tuyến

Danh sách cạnh (edge list) lưu mỗi cạnh thành một bản ghi. Với đồ thị có trọng số, bản ghi có thể là (u, v, w). Cách này hữu ích khi cần xét hoặc sắp xếp mọi cạnh. Nó không tự nhóm các cạnh theo đỉnh.

Ví dụ sau sắp các tuyến theo chi phí, rồi in từng bản ghi. Hàm sorted tạo thứ tự mới; nó không thay đổi ý nghĩa của cạnh.

edges = [(1, 2, 7), (1, 3, 0), (2, 3, 4)]
ordered = sorted(edges, key=lambda edge: edge[2])
for u, v, w in ordered:
    print(u, v, w)

1 3 0
2 3 4
1 2 7

Lưu danh sách cạnh tốn O(m) bộ nhớ. Duyệt tất cả cạnh tốn O(m); sắp xếp tốn O(m log m). Nếu hỏi hàng xóm của một đỉnh, phải lọc các cạnh, mất O(m) trong cách lưu này. Đồ thị vô hướng cần xét cả hai đầu khi lọc.

Bạn cũng có thể chuyển từ danh sách cạnh sang danh sách kề. Mỗi bản ghi được thêm vào hàng tương ứng. Không cần duyệt lại toàn bộ danh sách cho từng đỉnh.

n = 4
edges = [(1, 2), (2, 3), (2, 4)]
g = [[] for _ in range(n + 1)]
for u, v in edges:
    g[u].append(v)
    g[v].append(u)
print(*sorted(g[2]))

1 3 4

Khi vòng lặp kết thúc, mỗi cạnh đã được thêm vào hai hàng đầu mút. Hàng của 2 chứa đúng ba đỉnh nối trực tiếp. Việc dựng tốn O(n + m); bước sắp xếp hàng 2 tốn thêm O(d log d) với d là số hàng xóm trong hàng đó.

Chọn cấu trúc theo thao tác cần làm

Không có cấu trúc nào tốt nhất cho mọi câu hỏi. Hãy đọc cả giới hạn lẫn thao tác cần thực hiện trước khi chọn.

Ở đây deg(u) là số bản ghi trong hàng kề của u. Chi phí của tập hợp là trung bình, không phải cam kết thời gian cố định cho mọi trường hợp. Số cạnh thực tế và chi phí đối tượng Python quyết định bộ nhớ dùng thực tế.

Nếu n = 100000 và m = 200000, danh sách kề lưu 400000 bản ghi hàng xóm cho đồ thị vô hướng. Ma trận cần khoảng 10 tỷ ô. Nếu n = 200 và bạn cần kiểm tra một triệu cặp, ma trận có 40000 ô và trả lời trực tiếp từng cặp. Phải đối chiếu thêm giới hạn máy trước khi kết luận một chương trình chắc chắn đủ bộ nhớ.

Nếu dùng tập kề cho đồ thị vô hướng, thêm cả hai chiều. Cạnh nhập lặp lại không tạo thêm phần tử. Ví dụ sau trả lời hai câu hỏi và cho thấy số lượng hàng xóm phân biệt.

g = [set() for _ in range(4)]
for u, v in [(1, 2), (1, 2), (1, 3)]:
    g[u].add(v)
    g[v].add(u)
print(2 in g[1])
print(3 in g[2])
print(len(g[1]))

True
False
2

Kết quả đếm hai hàng xóm phân biệt của đỉnh 1, dù dữ liệu có ba cạnh. Nếu đề yêu cầu bậc tính cả cạnh song song, len(g[1]) trong ví dụ này không đủ. Khi cần vừa truy vấn nhanh vừa giữ số cạnh, dùng bộ đếm theo cặp hoặc lưu thêm thông tin.

Lỗi thường gặp

Tóm tắt

• Đỉnh là đối tượng; cạnh biểu diễn quan hệ trực tiếp, có thể có hướng và trọng số.
• Danh sách kề nhóm hàng xóm theo đỉnh và dùng O(n + m) bộ nhớ.
• Ma trận kề cho phép hỏi một ô trực tiếp, nhưng cần O(n²) bộ nhớ.
• Danh sách cạnh phù hợp khi duyệt hoặc sắp xếp toàn bộ cạnh.
• Xác định rõ cách xử lý đỉnh cô lập, khuyên, cạnh trùng và trọng số 0.

Kiểm tra nhanh

Đọc thêm

• Python: cấu trúc dữ liệu — danh sách, tập hợp và cách sử dụng.