Chuyên đề Tin 12 CTST Bài 3.2. Biểu diễn đồ thị

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

Dựa vào ma trận kề trong Hình 3, bạn có thể vẽ đồ thị vô hướng với 5 đỉnh được đánh số từ 0 đến 4. Các cạnh của đồ thị sẽ được nối dựa trên các giá trị ‘1’ trong ma trận:

Đỉnh 0 nối với đỉnh 3

Đỉnh 1 nối với đỉnh 2

Đỉnh 1 nối với đỉnh 3

Đỉnh 2 nối với đỉnh 3

Đỉnh 2 nối với đỉnh 4

Đây là cách biểu diễn trực quan giúp bạn dễ dàng nhận biết mối liên kết giữa các đỉnh trong đồ thị mà không cần đến hình ảnh cụ thể.

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

Dựa vào danh sách kề từ Bảng 6, bạn có thể vẽ đồ thị có hướng với các đỉnh A, B, C, D, và E. Các mũi tên sẽ được vẽ theo hướng từ đỉnh này sang đỉnh kề của nó:

Từ đỉnh A đến đỉnh B và D

Từ đỉnh B đến đỉnh A và C

Từ đỉnh C đến đỉnh B và E

Từ đỉnh D đến đỉnh A và E

Từ đỉnh E đến đỉnh C và D

Đồ thị này thể hiện mối quan hệ hướng từ giữa các đỉnh, phổ biến trong việc biểu diễn các mô hình dữ liệu và phân tích mạng trong khoa học máy tính.  

Dựa vào mô tả của đồ thị G7 (Hình 7), dưới đây là cách biểu diễn bằng ma trận kề và danh sách kề:

Ma trận kề cho G7:

Danh sách kề cho G7:

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

Đỉnh 1: [2, 5]

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

Đỉnh 3: [0, 4]

Đỉnh 4: [0, 5]

Đỉnh 5: [3, 4]

Rất tiếc, mô tả cho đồ thị G6 (Hình 6) không được cung cấp, vì vậy em không thể thực hiện biểu diễn cho đồ thị đó. Nếu bạn có thông tin về đồ thị G6, hãy cung cấp và em sẽ giúp bạn biểu diễn nó.

Ví dụ về cách viết chương trình để xuất ra màn hình ma trận kề biểu diễn cho từng đồ thị: