Câu hỏi:
11/07/2024 107
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.
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
Trả lời:
Giải bởi Vietjack
Để 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],
[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],
[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.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
Sổ tay lớp 12 các môn Toán, Lí, Hóa, Văn, Sử, Địa, KTPL (chương trình mới)
Đã bán 1,5k
₫ 70.000
₫ 36.000
Tổng ôn lớp 12 môn Toán, Lí, Hóa, Văn, Anh, Sinh Sử, Địa, KTPL (Form 2025)
Đã bán 1,1k
₫ 70.000
₫ 36.000
Bình luận
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?
Một đơn đồ thị, vô hướng có n đỉnh, có thể có số cạnh lớn nhất là bao nhiêu?
Xem đáp án »
11/07/2024
1,016
Câu 2:
Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?
Từ ma trận kề A của đồ thị G có thể tính được số các cạnh của đồ thị không? Nếu được thì tính bằng cách nào?
Xem đáp án »
11/07/2024
291
Câu 4:
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.
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.
Xem đáp án »
26/06/2024
188
Câu 6:
Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.
Tìm hiểu, thảo luận cách thiết lập dữ liệu của đồ thị trong trường hợp tệp dữ liệu biểu diễn danh sách các cạnh.
Xem đáp án »
11/07/2024
178
Câu 7:
Khẳng định dãy Adj[i] có số lượng phần tử bằng số các phần tử có giá trị 1 của hàng thứ i của ma trận kề A là đúng hay sai?
Khẳng định dãy Adj[i] có số lượng phần tử bằng số các phần tử có giá trị 1 của hàng thứ i của ma trận kề A là đúng hay sai?
Xem đáp án »
26/06/2024
155
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 24 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 22 có đáp án
-
Trắc nghiệm tổng hợp Tin học năm 2023 có đáp án (Phần 4)
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 25 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 20 có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 16 có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận
-
-
Bình luận