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

Ra mắt Sách 20 đề THPT quốc gia form 2025 toán, văn, anh.... (từ 80k/1 cuốn)

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:

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