Question

Đã trả lời bởi chuyên gia

Answer 1

Để 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],

[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.

...Xem thêm

Answer 2