Trang 1
goupee.vn goupee.com THUẬT TOÁN ỨNG DỤNG PHAM QUANG DUNG Graphs Phạm Quang Dũng Bộ môn KHMT dungpq@soict.hust.edu.vn 1 fb.com/goupee.vn
Nội dung tài liệu
Trang 2
goupee.vn goupee.com 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 fb.com/goupee.vn
Trang 3
goupee.vn goupee.com Đồ 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 6 2 1 5 1 5 3 4 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), 3 (2, 6), (3, 4), (3, 6), (4, 5)}fb.com/goupee.vn (6, 2), (3, 4), (6, 3), (4, 5)}
Trang 4
goupee.vn goupee.com Đồ 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 6 2 1 5 1 5 3 4 3 4 Undirected graph Directed graph deg(1) = 2, deg(6) = 3 deg-(1) = 0, deg+(1) = 2 4 fb.com/goupee.vn
Trang 5
goupee.vn goupee.com Đồ 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 6 2 1 5 1 5 3 4 3 4 Path from 1 to 5: Path from 1 to 5: 1, 3, 4, 5 1, 3, 4, 5 1, 6, 2, 5 1, 6, 4, 5 5 fb.com/goupee.vn
Trang 6
goupee.vn goupee.com Đồ thị đặc biệt 1 3 1 1 4 2 3 2 6 3 2 5 4 5 4 Đồ thị đầy đủ Đồ thị hai phía Đồ thị phẳng 6 fb.com/goupee.vn
Trang 7
goupee.vn goupee.com Đồ thị Ma trận kề Ma trận trọng số 6 2 6 4 2 3 6 1 5 1 5 9 5 2 3 4 7 3 8 4 1 2 3 4 5 6 1 2 3 4 5 6 1 0 0 1 0 0 1 1 0 0 7 0 0 3 2 0 0 0 1 1 1 2 0 0 0 9 6 4 3 1 0 0 1 0 1 3 7 0 0 8 0 5 4 0 1 1 0 1 0 4 0 9 8 0 2 0 5 0 1 0 1 0 0 5 0 6 0 4 0 0 6 1 1 1 0 0 0 6 3 4 5 0 0 0 7 fb.com/goupee.vn
Trang 8
goupee.vn goupee.com Biểu diễn đồ thị Danh sách kề Với mỗi v V, A(v) là tập các bộ (v, u, w) trong đó w là trọng số cung (v, u) 4 A(1) = {(1, 6, 3), (1, 3, 7)} 3 6 2 6 A(2) = {(2, 4, 9), (2, 5, 6)} 1 5 9 5 2 A(3) = {(3, 4, 8)} 7 8 3 4 A(4) = {(4, 5, 2)} A(5) = {} A(6) = {(6, 3, 5), (6, 2, 4)} 8 fb.com/goupee.vn
Trang 9
goupee.vn goupee.com Duyệt đồ thị Thăm các đỉnh của đồ thị theo một thứ tự nào đó Mỗi đỉnh thăm đúng 1 lần Có 2 phương pháp chính Duyệt theo chiều sâu: Depth-First Search (DFS) Duyệt theo chiều rộng: Breadth-First Search (BFS) 9 fb.com/goupee.vn
Trang 10
goupee.vn goupee.com Depth-First Search (DFS) DFS(u): DFS bắt đầu thăm từ đỉnh u Nếu tồn tại một đỉnh v trong danh sách kề của u mà chưa được thăm → tiền hành thăm v và gọi DFS(v) Nếu tất cả các đỉnh kề với u đã được thăm → DFS quay lui trở lại đỉnh x từ đó thuật toán thăm u và tiến hành thăm các đỉnh khác kề với x (gọi DFS(x)) mà chưa được thăm. Lúc này, đỉnh u được gọi là đã duyệt xong 10 fb.com/goupee.vn
Trang 11
goupee.vn goupee.com Depth-First Search (DFS) Các thông tin liên quan đến mỗi đỉnh v p(v): là đỉnh mà từ đó, DFS thăm đỉnh v d(v): thời điểm đỉnh v được thăm nhưng chưa duyệt xong f(v): thời điểm đỉnh v đã duyệt xong color(v) WHITE: chưa thăm GRAY: đã được thăm nhưng chưa duyệt xong BLACK: đã duyệt xong 11 fb.com/goupee.vn
Trang 12
goupee.vn goupee.com Depth First Search - DFS DFS(u) { DFS() { t = t + 1; foreach (node u of V) { d(u) = t; color(u) = GRAY; color(u) = WHITE; foreach(adjacent node v to u) p(u) = NIL; { } if(color(v) = WHITE) { t = 0; p(v) = u; DFS(v); foreach(node u of V) { } if(color(u) = WHITE) { } DFS(u); t = t + 1; } f(u) = t; color(u) = BLACK; } } } 12 fb.com/goupee.vn
Trang 13
goupee.vn goupee.com Depth First Search - DFS 6 2 Node 1 2 3 4 5 6 7 1 5 d f 3 4 p - - - - - - - color W W W W W W W 7 13 fb.com/goupee.vn
Trang 14
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 d 1 f p - - - - - - - color G W W W W W W 6 2 1 5 3 4 14 fb.com/goupee.vn 7
Trang 15
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 d 1 2 f 3 p - - 1 - - - - color G W G W W W W 6 2 1 5 3 4 15 fb.com/goupee.vn 7
Trang 16
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 d 1 2 3 f 3 4 p - - 1 3 - - - color G W G G W W W 6 2 1 5 3 4 16 fb.com/goupee.vn 7
Trang 17
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 5 d 1 2 3 4 f 3 4 p - - 1 3 4 - - color G W G G G W W 6 2 1 5 3 4 17 fb.com/goupee.vn 7
Trang 18
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 5 d 1 2 3 4 f 5 3 4 p - - 1 3 4 - - color G W G G B W W 6 2 1 5 3 4 18 fb.com/goupee.vn 7
Trang 19
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 5 d 1 2 3 4 6 f 5 3 4 p - - 1 3 4 - 4 color G W G G B W G 7 6 2 1 5 3 4 19 fb.com/goupee.vn 7
Trang 20
goupee.vn goupee.com Depth First Search - DFS DFS(1) Node 1 2 3 4 5 6 7 1 5 d 1 2 3 4 6 f 5 7 3 4 p - - 1 3 4 - 4 color G W G G B W B 7 6 2 1 5 3 4 20 fb.com/goupee.vn 7
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!