Đang chuẩn bị liên kết để tải về tài liệu:
CTDLGT_Chuong_7_Phan_1_Graph_DFS_BFS

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Chương 7Đồ thị.Phần 1 – Đồ thị, DFS, BFS.(Buổi 12).Giới thiệu.Chương này trình bày các bài toán của đồ thị:.Duyệt đồ thị: đi qua tất cả các định của đồ thị và.mỗi đỉnh chỉ được xử lý một lần. Có hai cách.duyệt đồ thị là tìm kiếm theo chiều sâu (DFS –.Depth-First Search) và tìm kiếm theo chiều rộng.(BFS – Breadth-First Search)Tìm đường đi ngắn nhất: tìm đường đi từ một.đỉnh này đến một đỉnh khác của đồ thị mà có tổng.trọng số của đường đi là nhỏ nhấtCây phủ tối thiểu: tìm đồ thị con (không có chu.trình) kết nối tất cả các đỉnh của đồ thị và có tổng.trọng số của các cạnh là nhỏ nhấtSắp thứ tự bộ phận (topological sorting)Trường Đại học Bách Khoa Tp.HCM.Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải thuật.Chương 7: Đồ thị.2.Định nghĩa đồ thị.Cạnh (v1, v2) là đường nối giữa hai đỉnh v1 và.v2Cung (v1, v2) là đường nối từ đỉnh v1 đến v2Đồ thị (graph) là một cặp G = (V, E) trong đó V.là tập các đỉnh và E là tập các cạnh (hoặc cung).giữa hai đỉnhNếu E là tập các cạnh thì G là đồ thị vô hướngNếu E là tạp các cung thì G là đồ thị hữu hướng.Trường Đại học Bách Khoa Tp.HCM.Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải thuật.Chương 7: Đồ thị.3.Định nghĩa đồ thị.0.v1v2(a) Cạnh (v1, v2)v114v2(b) Cung (v1, v2)32(c) Đồ thị hữu hướng.Hình 7.1. Cạnh, cung và đồ thị hữu hướng.Trường Đại học Bách Khoa Tp.HCM.Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải thuật.Chương 7: Đồ thị.4.Các khái niệm.Với cung (v1, v2):.v1 là đỉnh gốc.v2 là đỉnh ngọn.v1, v2 là hai đỉnh kề nhauNếu đỉnh v là đỉnh ngọn của một cung mà.không là đỉnh gốc của một cung nào thì v là.đỉnh treo. Cung nối với đỉnh treo là cung treoCạnh nối với đỉnh treo là cạnh treo.Trường Đại học Bách Khoa Tp.HCM.Khoa Khoa học và Kỹ thuật Máy tính.© 2011Nguyễn Trung TrựcCấu trúc dữ liệu và Giải thuật.Chương 7: Đồ thị.5. | Chương 7 Đồ thị Phần 1 – Đồ thị, DFS, BFS (Buổi 12) Giới thiệu Chương này trình bày các bài toán của đồ thị: Duyệt đồ thị: đi qua tất cả các định của đồ thị và mỗi đỉnh chỉ được xử lý một lần. Có hai cách duyệt đồ thị là tìm kiếm theo chiều sâu (DFS – Depth-First Search) và tìm kiếm theo chiều rộng (BFS – Breadth-First Search). Tìm đường đi ngắn nhất: tìm đường đi từ một đỉnh này đến một đỉnh khác của đồ thị mà có tổng trọng số của đường đi là nhỏ nhất. Cây phủ tối thiểu: tìm đồ thị con (không có chu trình) kết nối tất cả các đỉnh của đồ thị và có tổng trọng số của các cạnh là nhỏ nhất. Sắp thứ tự bộ phận (topological sorting). Trường Đại học Bách Khoa Tp.HCM Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 2 Định nghĩa đồ thị Cạnh (v1, v2) là đường nối giữa hai đỉnh v1 và v2. Cung (v1, v2) là đường nối từ đỉnh v1 đến v2. Đồ thị (graph) là một cặp G = (V, E) trong đó V là tập các đỉnh và E là tập các cạnh (hoặc cung) giữa hai đỉnh. Nếu E là tập các cạnh thì G là đồ thị vô hướng. Nếu E là tạp các cung thì G là đồ thị hữu hướng. Trường Đại học Bách Khoa Tp.HCM Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 3 Định nghĩa đồ thị 0 v1 v2 (a) Cạnh (v1, v2) v1 1 4 v2 (b) Cung (v1, v2) 3 2 (c) Đồ thị hữu hướng Hình 7.1. Cạnh, cung và đồ thị hữu hướng Trường Đại học Bách Khoa Tp.HCM Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ thị 4 Các khái niệm Với cung (v1, v2): v1 là đỉnh gốc v2 là đỉnh ngọn v1, v2 là hai đỉnh kề nhau Nếu đỉnh v là đỉnh ngọn của một cung mà không là đỉnh gốc của một cung nào thì v là đỉnh treo. Cung nối với đỉnh treo là cung treo. Cạnh nối với đỉnh treo là cạnh treo. Trường Đại học Bách Khoa Tp.HCM Khoa Khoa học và Kỹ thuật Máy tính © 2011 Nguyễn Trung Trực Cấu trúc dữ liệu và Giải thuật Chương 7: Đồ .