Chương 7Đồ 1 – Đồ thị, DFS, BFS.(Buổi 12).Giới 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ị đỉnh chỉ được xử lý một lần. Có hai đồ 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ừ này đến một đỉnh khác của đồ thị mà có số của đường đi là nhỏ nhấtCây phủ tối thiểu: tìm đồ thị con (không có ) kết nối tất cả các đỉnh của đồ thị và có 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 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 7: Đồ nghĩa đồ (v1, v2) là đường nối giữa hai đỉnh v1 (v1, v2) là đường nối từ đỉnh v1 đến v2Đồ thị (graph) là một cặp G = (V, E) trong đó 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 Đại học Bách 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 7: Đồ nghĩa đồ (a) Cạnh (v1, v2)v114v2(b) Cung (v1, v2)32(c) Đồ thị hữu . Cạnh, cung và đồ thị hữu Đại học Bách 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 7: Đồ khái cung (v1, v2):.v1 là đỉnh là đỉnh , v2 là hai đỉnh kề nhauNếu đỉnh v là đỉnh ngọn của một cung là đỉnh gốc của một cung nào thì v treo. Cung nối với đỉnh treo là cung treoCạnh nối với đỉnh treo là cạnh Đại học Bách 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 7: Đồ . | 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 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 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 . Cạnh, cung và đồ thị hữu hướng Trường Đại học Bách Khoa 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 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: Đồ .
