Tin học 12 · SGK Chuyên đề Khoa học máy tính

Bài 12. Biểu diễn đồ thị

BÀI 12 BIỂU DIỄN ĐỒ THỊ

Sau bài học này em sẽ:

Quan sát đồ thị Hình 12.1 và cho biết mỗi tệp dữ liệu sau có ý nghĩa gì.

Hình 12.1. Đồ thị và dữ liệu mô tả đồ thị

1. Mô hình dữ liệu đồ thị

Hoạt động 1

Tìm hiểu, thảo luận về các cách biểu diễn dữ liệu của một đồ thị G.

Có nhiều cách biểu diễn dữ liệu của một đồ thị, trong đó thường gặp ba cách sau:

Sử dụng danh sách các cạnh của đồ thị.
Sử dụng ma trận kề kích thước n × n.
Sử dụng danh sách kề.

Trong các cách trên yêu cầu có thêm giá trị n là số đỉnh hay kích thước của đồ thị. Sau đây, chúng ta cùng tìm hiểu tệp dữ liệu tương ứng với các cách biểu diễn đồ thị khác nhau.

a) Dữ liệu danh sách các cạnh của đồ thị

Tệp dữ liệu loại này (Hình 12.2) có dạng như sau:

b) Dữ liệu ma trận kề của đồ thị

Tệp dữ liệu loại này (Hình 12.3) có dạng sau:

c) Dữ liệu danh sách kề của đồ thị

Tệp dữ liệu loại này (Hình 12.4) có dạng sau:

Lưu ý: Yêu cầu thành phần đầu tiên của dòng thứ i là số i chỉ có ý nghĩa hình thức. Tuy nhiên, cách định nghĩa này là cần thiết khi đỉnh i của đồ thị là biệt lập, tức là không có các đỉnh kề. Khi đó dòng thứ i chỉ có đúng một giá trị.

Có nhiều cách thiết lập tệp dữ liệu biểu diễn đồ thị. Các cách thường dùng là tệp dữ liệu danh sách các cạnh, ma trận kề hoặc danh sách kề.

2. Thiết lập đồ thị từ tệp ma trận kề và tệp danh sách kề

Hoạt động 2: Tìm hiểu cách thiết lập đồ thị từ ma trận kề và danh sách kề

Tìm hiểu, thảo luận cách thiết lập đồ thị (dữ liệu của đồ thị) trong trường hợp tệp dữ liệu biểu diễn là ma trận kề hoặc danh sách kề.

a) Thiết lập đồ thị từ tệp ma trận kề

Tệp dữ liệu ma trận kề có dòng đầu tiên là n (số đỉnh của đồ thị), n dòng tiếp theo mô tả ma trận kề của đồ thị. Chương trình sau đây đọc tệp dữ liệu này để tạo dữ liệu biểu diễn đồ thị theo ma trận kề. Chương trình sẽ áp dụng cho cả đồ thị vô hướng và đồ thị có hướng. Hàm BuildGraph(fname) đọc dữ liệu từ tệp fname và trả về bộ dữ liệu V, A với V là danh sách các đỉnh, A là ma trận kề.

Chương trình 2a. Thiết lập đồ thị từ dữ liệu ma trận kề. Áp dụng cho đồ thị vô hướng và đồ thị có hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
A = []
for line in f:
A.append([int(ch) for ch in line.split()])  # bổ sung vào A
f.close()
return V, A

b) Thiết lập đồ thị từ tệp danh sách kề

Tệp dữ liệu danh sách kề có dòng đầu tiên là n (số đỉnh của đồ thị), n dòng tiếp theo mô tả danh sách kề của đồ thị. Chương trình sau đây đọc tệp dữ liệu đầu vào và tạo bộ dữ liệu biểu diễn đồ thị theo danh sách kề. Chương trình sẽ áp dụng cho cả đồ thị vô hướng và có hướng. Hàm BuildGraph(fname) sẽ đọc dữ liệu từ tệp có tên fname và trả về bộ dữ liệu V, Adj với V là danh sách các đỉnh, Adj là danh sách kề.

Chương trình 2b. Thiết lập đồ thị từ tệp dữ liệu danh sách kề. Áp dụng cho đồ thị vô hướng và đồ thị có hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
Adj = [[] for i in range(n)]  # thiết lập Adj gồm n dãy rỗng
for i in range(n):
line = [int(x) for x in f.readline().split()]
line = line[1:]  # lấy dãy các số từ vị trí thứ 2
Adj[i].extend(line)  # bổ sung vào hàng thứ i của Adj
f.close()
return V, Adj

Có thể thiết lập đồ thị từ tệp dữ liệu biểu diễn là ma trận kề hoặc danh sách kề. Các chương trình này có thể áp dụng cho cả đồ thị vô hướng và đồ thị có hướng.

3. Thiết lập đồ thị từ danh sách các cạnh

Hoạt động 3: Tìm hiểu cách thiết lập dữ liệu đồ thị từ tệp dữ liệu 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.

Tệp dữ liệu danh sách các cạnh có dòng đầu tiên là n (số đỉnh của đồ thị), các dòng tiếp theo mô tả danh sách các cạnh, mỗi dòng có hai số i, j cách nhau bởi dấu cách. Mỗi dòng ứng với một cạnh nối đỉnh i đến đỉnh j của đồ thị. Nếu đồ thị có hướng thì cần cập nhật một lần vào ma trận kề và danh sách kề của đồ thị. Nếu đồ thị vô hướng thì cần cập nhật hai lần: Ví dụ với cạnh (i, j) thì cần cập nhật cho ma trận kề A[i][j] = 1 và A[j][i] = 1, cập nhật cho danh sách kề là A[i].append(j) và A[j].append(i). Do vậy chương trình cho đồ thị vô hướng khác với chương trình cho đồ thị có hướng.

a) Trường hợp đồ thị vô hướng

Dữ liệu đầu vào của đồ thị được cho bởi tệp fname lưu thông tin danh sách các cạnh của đồ thị. Hàm BuildGraph(fname) đọc dữ liệu từ tệp fname và trả lại dữ liệu biểu diễn đồ thị.

Chương trình 3.1a. Thiết lập đồ thị biểu diễn bởi ma trận kề từ tệp dữ liệu danh sách các cạnh, áp dụng cho đồ thị vô hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
A = [[0 for i in range(n)] for j in range(n)]  # thiết lập ma trận n x n số 0
for line in f:
edge = [int(ch) for ch in line.split()]
i, j = edge[0], edge[1]  # đây là cạnh nối i và j
A[i][j] = 1
A[j][i] = 1
f.close()
return V, A

Chương trình 3.2a. Thiết lập đồ thị biểu diễn bởi danh sách kề từ tệp dữ liệu danh sách các cạnh, áp dụng cho đồ thị vô hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
Adj = [[] for i in range(n)]  # thiết lập Adj gồm n dãy rỗng
for line in f:
edge = [int(ch) for ch in line.split()]
i, j = edge[0], edge[1]  # đây là cạnh nối i và j
Adj[i].append(j)  # bổ sung j vào hàng thứ i của Adj
Adj[j].append(i)  # bổ sung i vào hàng thứ j của Adj
f.close()
return V, Adj

b) Trường hợp đồ thị có hướng

Chương trình 3.1b. Thiết lập đồ thị biểu diễn bởi ma trận kề từ tệp dữ liệu danh sách các cạnh, áp dụng cho đồ thị có hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
A = [[0 for i in range(n)] for j in range(n)]  # thiết lập ma trận n x n số 0
for line in f:
edge = [int(ch) for ch in line.split()]
i, j = edge[0], edge[1]  # đây là cạnh nối i đến j
A[i][j] = 1
f.close()
return V, A

Chương trình 3.2b. Thiết lập đồ thị biểu diễn bởi danh sách kề từ tệp dữ liệu danh sách các cạnh, áp dụng cho đồ thị có hướng.

def BuildGraph(fname):
f = open(fname)
n = int(f.readline())
V = [i for i in range(n)]
Adj = [[] for i in range(n)]  # thiết lập Adj gồm n dãy rỗng
for line in f:
edge = [int(ch) for ch in line.split()]
i, j = edge[0], edge[1]  # đây là cạnh nối i đến j
Adj[i].append(j)  # bổ sung j vào hàng thứ i của Adj
f.close()
return V, Adj

Các chương trình này được áp dụng riêng cho đồ thị vô hướng và đồ thị có hướng.

Bài 12. Biểu diễn đồ thị