Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge Adj trả lại danh sách E

Giải Chuyên đề Tin 12 Bài 12: Biểu diễn đồ thị - Kết nối tri thức

Vận dụng 2 trang 61 Chuyên đề Tin học 12: Cho danh sách kề Adj của đồ thị G. Viết hàm GraphEdge(Adj) trả lại danh sách E các cạnh của đồ thị G. Viết chương trình cho hai trường hợp riêng biệt, G là đồ thị vô hướng và G là đồ thị có hướng

Quảng cáo

Lời giải:

Để viết hàm GraphEdge(Adj) trả về danh sách các cạnh của đồ thị từ danh sách kề Adj, chúng ta cần xác định cách thức biểu diễn cạnh từ danh sách kề. Trong trường hợp đồ thị vô hướng, mỗi cạnh sẽ được biểu diễn một lần. Trong trường hợp đồ thị có hướng, mỗi cạnh sẽ được biểu diễn hai lần (một lần cho mỗi hướng).

Dưới đây là cách triển khai hàm này cho cả hai trường hợp:

Trường hợp đồ thị vô hướng:

def GraphEdgeUndirected(Adj):

edges = []

for i in range(len(Adj)):

for j in Adj[i]:

if j > i: # Chỉ thêm cạnh một lần, tránh trùng lặp

edges.append((i, j))

return edges

# Sử dụng:

Adj_undirected = [

[1, 2],

[0, 3],

[1, 2]

]

print(GraphEdgeUndirected(Adj_undirected))

- Trường hợp đồ thị có hướng:

def GraphEdgeDirected(Adj):

edges = []

for i in range(len(Adj)):

for j in Adj[i]:

edges.append((i, j))

return edges

# Sử dụng:

Adj_directed = [

[1, 2],

[3],

[]

]

print(GraphEdgeDirected(Adj_directed))

Trong cả hai trường hợp, chúng ta duyệt qua mỗi đỉnh trong danh sách kề Adj và tạo các cạnh tương ứng dựa trên thông tin trong danh sách kề. Trong trường hợp đồ thị vô hướng, chúng ta chỉ thêm cạnh một lần (đảm bảo tránh trùng lặp). Trong trường hợp đồ thị có hướng, chúng ta thêm cạnh theo cách thông thường. Cuối cùng, chúng ta trả về danh sách các cạnh đã tạo.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 12: Biểu diễn đồ thị hay, ngắn gọn khác: