Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất
Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.
Giải Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị - Kết nối tri thức
Hoạt động 3 trang 53 Chuyên đề Tin học 12: Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.
Lời giải:
Có hai cách biểu diễn dữ liệu đồ thị trên máy tính mà bạn có thể xem xét:
- Ma trận kề: Mỗi hàng và cột tương ứng với một đỉnh, và giá trị tại hàng i, cột j là 1 nếu có cạnh nối giữa đỉnh i và j, ngược lại là 0.
- Danh sách kề: Mỗi đỉnh liệt kê các đỉnh mà nó kết nối trực tiếp.
Đồ thị (a) - Cấu trúc hình sao:
- Ma trận kề:
- Danh sách kề:
Đỉnh 0: 1, 2, 3, 4
Đỉnh 1: 0
Đỉnh 2: 0
Đỉnh 3: 0
Đỉnh 4: 0
Đồ thị (b) - Cấu trúc liên kết nhiều hơn:
- Ma trận kề:
- Danh sách kề:
Đỉnh 0: 1, 3
Đỉnh 1: 0, 2, 4
Đỉnh 2: 1, 3
Đỉnh 3: 0, 2, 4
Đỉnh 4: 1, 3
Lời giải bài tập Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị hay, ngắn gọn khác:
Câu hỏi 2 trang 51 Chuyên đề Tin học 12: Vẽ đồ thị vô hướng G = (V, E) sau: V = [0, 1, 2, 3, 4] ....
Câu hỏi 1 trang 53 Chuyên đề Tin học 12: Khi nào một đỉnh của đồ thị có bậc bằng 0? ....