Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Đỗ Bích Diệp (tt)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 8: Cấu trúc đồ thị" trình bày các nội dung: Cây và Rừng trong lý thuyết đồ thị, bài toán tìm cây khung cực tiểu, giải thuật Kruskal - MST, giải thuật Prim - MST, bài toán tìm đường đi ngắn nhất, giải thuật Dijkstra,... Đây là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Đỗ Bích Diệp (tt)Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu và Giải thuật Chương V: Đồ thị (phần 2) Cây và Rừng trong lý thuyết đồ thị – Cây z Một đồ thị vô hướng liên thông z Không có chu trình Cây – Rừng z Một tập các cây phân biệt RừngĐỗ Bích Diệp - Khoa CNTT - ĐHBKHN 1Cấu trúc dữ liệu và Giải thuật Cây khung – Cho một đồ thị vô hướng, liên thông G z Cây khung trên G là cây có chứa tất cả các đỉnh trong G 1 1 1 2 3 2 2 3 3 6 6 6 4 4 4 5 5 5 Đồ thị Cây khung Cây khung Bài toán tìm cây khung cực tiểu z Cho một đồ thị vô hướng, liên thông có trọng số z Giá trị của một cây khung là tổng trọng số của các cung trong cây z Tìm một cây khung với giá trị nhỏ nhất trên đồ thị 6 6 5 5 9 2 8 2 10 4 4 Đồ thị đầu vào Cây khung cực tiểuĐỗ Bích Diệp - Khoa CNTT - ĐHBKHN 2Cấu trúc dữ liệu và Giải thuật Giải thuật Kruskal - MST z Ý tưởng – Lần lượt thêm vào cây khung cần tìm các cung có trọng số nhỏ nhất có được tại một thời điểm nếu cung đó không tạo thành chu trình trên phần cây khung đang tạm có Giải thuật Kruskal-MST 1 1 1 7 10 2 3 8 2 2 3 3 3 3 10 14 6 4 6 4 6 4 12 16 7 7 7 5 7 5 5 Đồ thị ban đầu Bước 1 Bước 2Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 3Cấu trúc dữ liệu và Giải thuật Giải thuật Kruskal – MST 1 1 ...