Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge A trả lại danh sách E
Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.
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 1 trang 61 Chuyên đề Tin học 12: Cho ma trận kề A của đồ thị vô hướng G. Viết hàm GraphEdge(A) trả lại danh sách E các cạnh của đồ thị G.
Lời giải:
Để viết hàm GraphEdge(A) trả về danh sách các cạnh của đồ thị vô hướng từ ma trận kề A, chúng ta có thể sử dụng phương pháp duyệt qua ma trận kề và tạo danh sách các cạnh dựa trên các phần tử có giá trị 1.
Dưới đây là cách triển khai hàm này bằng Python:
def GraphEdge(A):
n = len(A)
edges = []
for i in range(n):
for j in range(i+1, n): # Chỉ cần duyệt nửa phần tam giác trên của ma trận
if A[i][j] == 1: # Nếu có cạnh nối từ đỉnh i đến đỉnh j
edges.append((i, j)) # Thêm cạnh vào danh sách cạnh
return edges
# Ví dụ sử dụng
A = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
print(GraphEdge(A)) # In danh sách các cạnh của đồ thị G
Trong hàm này, chúng ta duyệt qua mỗi phần tử của ma trận kề A. Nếu phần tử A[i][j] có giá trị 1 (tức là có cạnh nối từ đỉnh i đến đỉnh j), chúng ta thêm cạnh (i,j) vào danh sách các cạnh. Chúng ta chỉ cần duyệt qua nửa phần tam giác trên của ma trận kề để tránh lặp lại việc đếm các cạnh hai lần. Cuối cùng, chúng ta trả về danh sách các cạnh đã tạ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:
Câu hỏi 1 trang 57 Chuyên đề Tin học 12: Vẽ đồ thị có tệp dữ liệu ma trận kề Hình 12.5 ....
Câu hỏi 2 trang 59 Chuyên đề Tin học 12: Khi nào ma trận kề A chỉ gồm toàn số 0? ....