Em hãy nhắc lại định nghĩa mảng hai chiều và cách khai báo mảng hai chiều
Em hãy nhắc lại định nghĩa mảng hai chiều và cách khai báo mảng hai chiều trong ngôn ngữ Python. Theo em, có thể sử dụng mảng hai chiều để biểu diễn một đồ thị được không?
Giải Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị - Chân trời sáng tạo
Khởi động trang 53 Chuyên đề Tin học 12: Em hãy nhắc lại định nghĩa mảng hai chiều và cách khai báo mảng hai chiều trong ngôn ngữ Python. Theo em, có thể sử dụng mảng hai chiều để biểu diễn một đồ thị được không?
Lời giải:
Định nghĩa mảng hai chiều và cách khai báo mảng hai chiều trong Python
Định nghĩa mảng hai chiều
Mảng hai chiều là một cấu trúc dữ liệu cho phép lưu trữ các phần tử trong một bảng có hàng và cột. Mỗi phần tử trong mảng hai chiều có thể được truy cập bằng cách sử dụng hai chỉ số: chỉ số hàng và chỉ số cột.
Cách khai báo mảng hai chiều trong Python
Trong Python, có nhiều cách để khai báo và sử dụng mảng hai chiều, nhưng phổ biến nhất là sử dụng danh sách lồng nhau (nested lists). Dưới đây là một số cách để khai báo mảng hai chiều trong Python:
1. Sử dụng danh sách lồng nhau:
# Khai báo mảng hai chiều 3x3
array = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Truy cập phần tử tại hàng 1, cột 2
element = array[1][2] # Giá trị là 6
2. Sử dụng vòng lặp để tạo mảng hai chiều:
# Tạo mảng hai chiều 3x3 với các giá trị ban đầu là 0
rows, cols = 3, 3
array = [[0 for _ in range(cols)] for _ in range(rows)]
Sử dụng mảng hai chiều để biểu diễn đồ thị
Có thể sử dụng mảng hai chiều để biểu diễn một đồ thị. Một trong những cách phổ biến để làm điều này là sử dụng ma trận kề (adjacency matrix).
Ma trận kề
Ma trận kề là một mảng hai chiều dùng để biểu diễn các cạnh của đồ thị. Nếu đồ thị có n đỉnh, thì ma trận kề là một ma trận vuông n x n trong đó phần tử ở hàng i và cột j có giá trị 1 nếu có cạnh nối từ đỉnh i đến đỉnh j, và 0 nếu không có cạnh nối.
Dưới đây là cách khai báo và sử dụng ma trận kề trong Python để biểu diễn đồ thị:
1. Khai báo ma trận kề cho đồ thị vô hướng:
# Số lượng đỉnh
n = 5
# Khai báo ma trận kề n x n với các giá trị ban đầu là 0
graph = [[0 for _ in range(n)] for _ in range(n)]
# Thêm cạnh (1, 2) vào đồ thị
graph[1][2] = 1
graph[2][1] = 1
# Thêm cạnh (0, 3) vào đồ thị
graph[0][3] = 1
graph[3][0] = 1
2. Khai báo ma trận kề cho đồ thị có hướng:
# Số lượng đỉnh
n = 5
# Khai báo ma trận kề n x n với các giá trị ban đầu là 0
graph = [[0 for _ in range(n)] for _ in range(n)]
# Thêm cạnh có hướng từ 1 đến 2 vào đồ thị
graph[1][2] = 1
# Thêm cạnh có hướng từ 0 đến 3 vào đồ thị
graph[0][3] = 1
Lời giải bài tập Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị hay, chi tiết khác: