- Đồ thị và cuối cùng là Sắp xếp và tìm kiếm.. - CHƯƠNG 5: ĐỒ THỊ (GRAPH). - Đồ thị là một cấu trúc dữ liệu rời rạc nhưng lại có ứng dụng hiện đại. - 9 Các phương pháp biểu diễn đồ thị trên máy tính.. - 9 Các thuật toán tìm kiếm trên đồ thị.. - 9 Đồ thị Euler &. - đồ thị hamilton.. - NHỮNG KHÁI NIỆM CƠ BẢN CỦA ĐỒ THỊ. - Các loại đồ thị. - Đồ thị (Graph) là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. - Mạng loại này có thể biểu diễn bằng một đơn đồ thị vô hướng.. - Đơn đồ thị vô hướng G = <V, E>. - Với mạng loại này, chúng ta không thể dùng đơn đồ thị vô hướng để biểu diễn. - Đồ thị loại này là đa đồ thị vô hướng.. - Đa đồ thị vô hướng G = <V, E>. - Giả đồ thị vô hướng được mô tả như trong hình 5.3.. - Giả đồ thị vô hướng G = <V, E>. - Đơn đồ thị có hướng được mô tả như trong hình 5.4.. - Đơn đồ thị có hướng G = <V, E>. - Đồ thị có hướng trong hình 5.4 không chứa các cạnh bội. - Đa đồ thị có hướng G = <V, E>. - Một số thuật ngữ cơ bản của đồ thị. - Hai đỉnh u và v của đồ thị vô hướng G =<V, E>. - được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G. - Hình 5.6 Đồ thị vô hướng G.. - Xét đồ thị trong hình 5.6, ta có. - Đường đi, chu trình, đồ thị liên thông. - Dễ dàng nhận thấy (a, d, c, f, e) là đường đi đơn độ dài 4, (d, e, c, a) không là đường đi vì (e,c) không phải là cạnh của đồ thị. - Đường đi trên đồ thị.. - BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH. - Việc chọn cấu trúc dữ liệu nào để biểu diễn đồ thị có tác động rất lớn đến hiệu quả thuật toán. - Biểu diễn đồ thị trong hình 5.8 dưới đây bằng ma trận kề.. - Đồ thị vô hướng G . - Ma trận kề của đồ thị có hướng là không đối xứng.. - Tìm ma trận kề của đồ thị có hướng trong hình 5.9.. - Đồ thị có hướng G. - Ma trận kề của đồ thị có trọng số trong hình 5.10.. - Đồ thị trọng số G. - Danh sách cạnh (cung) của đồ thị vô hướng, đồ thị có hướng, đồ thị trọng số:. - Danh sách cạnh cung hình Đồ thị có hướng Danh sách trọng số. - CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ. - Những thuật toán như vậy được gọi là thuật toán tìm kiếm trên đồ thị. - Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện. - Chú ý: Thuật toán tìm kiếm theo chiều sâu dễ dàng áp dụng cho đồ thị có hướng. - Áp dụng thuật toán tìm kiếm theo chiều sâu với đồ thị trong hình sau:. - Đồ thị vô hướng G Kết quả duyệt . - queue – hàng đợi lưu trữ các đỉnh sẽ được duyệt của đồ thị;. - Áp dụng thuật toán tìm kiếm theo chiều rộng với đồ thị trong hình 5.11 ta nhận được kết quả như sau:. - Kiểm tra tính liên thông của đồ thị. - Một đồ thị có thể liên thông hoặc có thể không liên thông. - Nếu đồ thị là liên thông (số thành phần liên thông là 1), chúng ta chỉ cần gọi tới thủ tục DFS() hoặc BFS() một lần. - Tìm đường đi giữa hai đỉnh bất kỳ của đồ thị. - Dưới đây là toàn văn chương trình tìm đường đi giữa hai đỉnh của đồ thị.. - Đồ thị được gọi là đồ thị Euler nếu nó có chu trình Euler. - Đồ thị có đường đi Euler được gọi là nửa Euler.. - Xét các đồ thị G1, G2, G3 trong hình 5.12.. - Đồ thị vô hướng G1, G2, G3.. - Đồ thị vô hướng liên thông G=<V, E>. - {loại cạnh (x,y) khỏi đồ thị};. - Đồ thị vô hướng G.. - Một đồ thị không có chu trình Euler nhưng vẫn có thể có đường đi Euler. - Để tìm tất cả các đường đi Euler của một đồ thị n đỉnh, m cạnh, ta có thể dùng kỹ thuật đệ qui như sau:. - Đường đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần được gọi là đường đi Hamilton. - Đồ thị chứa đường đi Hamilton được gọi là đồ thị nửa Hamilton.. - của đồ thị G = (V, E). - Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. - Đồ thị không có chu trình được gọi là rừng.. - là đồ thị vô hướng n đỉnh. - G là đồ thị vô hướng liên thông không có chu trình.. - Cho G là đồ thị vô hướng liên thông. - là đồ thị vô hướng liên thông. - là đồ thị vô hướng liên thông có trọng số. - Tìm một cây bao trùm trên đồ thị. - Tìm kiếm theo chiều sâu, áp dụng cho bài toán xây dựng cây bao trùm của đồ thị vô hướng liên thông G=(V, E). - là đồ thị vô hướng liên thông với tập đỉnh V = {1, 2. - là một cây bao trùm của đồ thị G. - Tìm cây bao trùm nhỏ nhất của đồ thị trong hình 5.16.. - Đồ thị vô hướng liên thông G=(V, E). - Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh;. - <Đồ thị không liên thông>;. - Chọn s là một đỉnh nào đó của đồ thị;. - H = (V H , T) là cây khung nhỏ nhất của đồ thị;. - Xét đồ thị có hướng G=<V, E>. - 9 Nắm vững những khái niệm và định nghĩa cơ bản của đồ thị.. - 9 Hiểu được các phương pháp biểu diễn đồ thị trên máy tính.. - cài đặt nhuần nhuyễn các thuật toán tìm đường đi ngẵn nhất giữa các cặp đỉnh của đồ thị trọng số.. - Cho trước ma trận kề của đồ thị. - Hãy viết chương trình tạo ra danh sách kề của đồ thị đó.. - Mỗi ô có thể coi là một đỉnh của đồ thị. - Mỗi ô có thể coi là một đỉnh của đồ thị . - Lý thuyết đồ thị. - Chương 5: ĐỒ THỊ (GRAPH) ...103. - Những khái niệm cơ bản của đồ thị...103. - Các loại đồ thị ...103. - Một số thuật ngữ cơ bản của đồ thị...106. - Biểu diễn đồ thị trên máy tính ...107. - Các thuật toán tìm kiếm trên đồ thị ...110. - Kiểm tra tính liên thông của đồ thị...112. - Tìm đường đi giữa hai đỉnh bất kỳ của đồ thị ...113. - Tìm một cây bao trùm trên đồ thị...120
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt