Viết lại các hàm thiết lập đồ thị BuildGraph fname với tệp dữ liệu đầu vào là danh sách

Giải Chuyên đề Tin 12 Bài 13: Thực hành thiết lập đồ thị - Kết nối tri thức

Vận dụng 2 trang 64 Chuyên đề Tin học 12: Viết lại các hàm thiết lập đồ thị BuildGraph(fname) với tệp dữ liệu đầu vào là danh sách các cạnh của đồ thị. Đầu ra của hàm là dãy các giá trị V, E, A, Adj. Viết hàm cho cả hai trường hợp đồ thị vô hướng và đồ thị có hướng.

Quảng cáo

Lời giải:

Dưới đây là mã Python cho các hàm thiết lập đồ thị BuildGraph dựa trên danh sách các cạnh của đồ thị:

def BuildGraph(fname):

V = set()

E = []

with open(fname, 'r') as file:

for line in file:

edge = tuple(map(int, line.strip().split())) # Chuyển đổi dòng thành cạnh (u, v)

V.add(edge[0]) # Thêm đỉnh u vào tập đỉnh

V.add(edge[1]) # Thêm đỉnh v vào tập đỉnh

E.append(edge) # Thêm cạnh vào danh sách các cạnh

V = sorted(V) # Sắp xếp tập đỉnh

n = len(V)

# Khởi tạo ma trận kề và danh sách kề

A = [[0] * n for _ in range(n)] # Ma trận kề

Adj = [[] for _ in range(n)] # Danh sách kề

# Điền thông tin vào ma trận kề và danh sách kề

for edge in E:

u, v = edge

A[u][v] = 1 # Đánh dấu cạnh (u, v) trong ma trận kề

Adj[u].append(v) # Thêm v vào danh sách kề của u

return V, E, A, Adj

# Sử dụng hàm BuildGraph cho đồ thị vô hướng

V, E, A, Adj = BuildGraph('graph_edges.txt')

print("Đồ thị vô hướng:")

print("Tập đỉnh:", V)

print("Tập cạnh:", E)

print("Ma trận kề:")

for row in A:

print(row)

print("Danh sách kề:")

for i, neighbors in enumerate(Adj):

print(f"{i}: {neighbors}")

# Sử dụng hàm BuildGraph cho đồ thị có hướng

V, E, A, Adj = BuildGraph('digraph_edges.txt')

print("\nĐồ thị có hướng:")

print("Tập đỉnh:", V)

print("Tập cạnh:", E)

print("Ma trận kề:")

for row in A:

print(row)

print("Danh sách kề:")

for i, neighbors in enumerate(Adj):

print(f"{i}: {neighbors}")

- Trong mã trên:

- Hàm BuildGraph đọc tệp dữ liệu đầu vào và xây dựng các biểu diễn của đồ thị: tập đỉnh VVV, tập cạnh EEE, ma trận kề AAA, và danh sách kề Adj\text{Adj}Adj.

- Hàm đọc dữ liệu từ tệp dựa trên định dạng: mỗi dòng trong tệp biểu diễn một cạnh của đồ thị.

- Các biểu diễn của đồ thị được trả về cho cả hai trường hợp đồ thị vô hướng và có hướng.

Quảng cáo

Lời giải bài tập Chuyên đề Tin 12 Bài 13: Thực hành thiết lập đồ thị hay, ngắn gọn khác: