THUẬT TOÁN ỨNG DỤNG PHAM QUANG DUNG Graphs 1 Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn Nội dung  Đồ thị và các thuật ngữ liên quan  Tìm kiếm theo chiều sâu  Tìm kiếm theo chiều rộng  Chu trình Euler  Thuật toán Dijkstra sử dụng hàng đợi ưu tiên  Thuật toán Kruskal sử dụng disjoint-set structure  Exercises 2 Đồ thị  Đối tượng toán học bao gồm các đỉnh (node) và các liên kết giữa các đỉnh (cạnh, cung)  Đồ thị G = (V,E), trong đó V là tập đỉnh, E là tập cạnh (cung)  (u,v)  E, chúng ta nói u kề với v 6 2 1 5 3 3 6 4 2 1 5 3 4 Undirected graph Directed graph  V = {1, 2, 3, 4, 5, 6}  V = {1, 2, 3, 4, 5, 6}  E = {(1, 3), (1,6), (2, 4), (2, 5),  E = {(1, 3), (1,6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5)} (6, 2), (3, 4), (6, 3), (4, 5)} Đồ thị  Bậc của một đỉnh là số đỉnh kề với nó deg(v) = #{u | (u, v)  E}  Bán bậc vào (bán bậc ra) của một đỉnh là số cung đi vào (đi ra) khỏi đỉnh đó trên đồ thị có hướng: deg-(v) = #{u | (u, v)  E}, deg+(v) = #{u | (v, u) E} 6 2 1 5 3 4 6 4 2 1 5 3 4 Undirected graph Directed graph  deg(1) = 2, deg(6) = 3  deg-(1) = 0, deg+(1) = 2 Đồ thị  Cho đồ thị G=(V, E) và 2 đỉnh s, t V, một đường đi từ s đến t trên G là chuỗi s = x0, x1, …, xk = t trong đó (xi, xi+1)E,  i = 0, 1, …, k-1 6 2 1 5 3 Path from 1 to 5:  1, 3, 4, 5  1, 6, 2, 5 5 6 2 1 4 5 3 Path from 1 to 5:  1, 3, 4, 5  1, 6, 4, 5 4 Đồ thị đặc biệt 1 3 1 1 2 3 2 4 6 3 2 5 4 Đồ thị đầy đủ 6 5 4 Đồ thị hai phía Đồ thị phẳng Đồ thị  Ma trận kề  Ma trận trọng số 6 2 3 1 1 2 3 4 5 6 7 5 4 1 2 3 4 5 6 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 0 1