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.

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.

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:

• Khởi động trang 62 Chuyên đề Tin học 12: Em hãy trao đổi, thảo luận và trả lời một số câu hỏi sau: Nếu đồ thị là vô hướng thì ma trận kề ....

• Luyện tập 1 trang 64 Chuyên đề Tin học 12: Trong Nhiệm vụ 1, hàm In_danh_sach_dinh_ke() lấy thông tin từ ma trận ....

• Luyện tập 2 trang 64 Chuyên đề Tin học 12: Trong Nhiệm vụ 2, chúng ta có thể thấy các đỉnh kề không được in ra theo thứ tự tăng dần ....

• Vận dụng 1 trang 64 Chuyên đề Tin học 12: Cây nhị phân có thể được coi là đồ thị vô hướng, các nút của cây sẽ tương ứng ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---