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

Giảm giá 50% sách VietJack đánh giá năng lực các trường trên Shopee Mall

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.

Quảng cáo

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

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

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:

Quảng cáo

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Tài liệu cho giáo viên: Giáo án, powerpoint, đề thi giữa kì cuối kì, đánh giá năng lực, thi thử THPT, HSG, chuyên đề, bài tập cuối tuần..... độc quyền VietJack, giá hợp lí

Sách VietJack thi THPT quốc gia 2025 cho học sinh 2k7:

ĐỀ THI, GIÁO ÁN, GÓI THI ONLINE DÀNH CHO GIÁO VIÊN VÀ PHỤ HUYNH LỚP 12

Bộ giáo án, đề thi, bài giảng powerpoint, khóa học dành cho các thầy cô và học sinh lớp 12, đẩy đủ các bộ sách cánh diều, kết nối tri thức, chân trời sáng tạo tại https://tailieugiaovien.com.vn/ . Hỗ trợ zalo VietJack Official