Từ danh sách kề ở Bảng 6. Hãy vẽ đồ thị có hướng tương ứng.

Đị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

Danh sách kề là một cách biểu diễn đồ thị thông qua việc liệt kê các đỉnh kề với mỗi đỉnh. Dưới đây là danh sách kề cho các đồ thị trong Hình 4 và Hình 5:

Hình 4 - Đồ thị G4:

Đỉnh 0: [1, 3]

Đỉnh 1: [0, 2, 3]

Đỉnh 2: [1, 3, 4]

Đỉnh 3: [0, 1, 2]

Đỉnh 4: 2

Hình 5 - Đồ thị G5:

Đỉnh 0: [1, 2, 3]

Đỉnh 1: [0, 5]

Đỉnh 2: [0, 6]

Đỉnh 3: [0, 4]

Đỉnh 4: 3

Đỉnh 5: 1

Đỉnh 6: 2

Danh sách này giúp ta dễ dàng nhận biết các đỉnh nào kề nhau trong đồ thị mà không cần nhìn vào hình ảnh cụ thể của đồ thị.