Câu hỏi:
11/07/2024 314Tì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.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa... kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 70k).
Quảng cáo
Trả lờ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
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.
Câu 2:
Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.
Câu 3:
Vẽ đồ thị vô hướng G = (V, E) sau:
V = [0, 1, 2, 3, 4]
E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}]
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 19 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 18 có đáp án
263 câu Trắc nghiệm tổng hợp ôn thi tốt nghiệp THPT môn Tin học Chủ đề F. Giải quyết vấn đề với sự trợ giúp của máy tính có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 16 có đáp án
Trắc nghiệm Tin học 12 KNTT Bài 17: Các mức ưu tiên của bộ chọn
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 21 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 15 có đáp án
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 20 có đáp án
Hãy Đăng nhập hoặc Tạo tài khoản để gửi bình luận