Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Phạm Thanh An

Chương 5 trình bày những kiến thức căn bản về lý thuyết đồ thị, cách biểu diễn, một số thuật toán trên đồ thị; đánh giá thuật toán và một số ứng dụng của đồ thị. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ThS. Phạm Thanh An Chương 5: ĐỒ THỊ Ths. Phạm Thanh An Bộ môn Khoa học máy tính ­ Khoa CNTT Trường Đại học Ngân hàng TP.HCM LOGO Mục tiêu của chương  Trình bày những kiến thức căn bản về lý  thuyết đồ thị, cách biểu diễn, một số thuật  toán trên đồ thị  Đánh giá thuật toán  Một số ứng dụng của đồ thị Định nghĩa Anchorage Boston Minneapolis Seattle Hartford SF Austin Atlanta Định nghĩa  Đồ thị G = (V,E)  V = tập hợp hữu hạn các phần tử (đỉnh hay nút)  E V × V, tập hữu hạn các cạnh (cung) a b Đỉnh c Cung d e Các khái niệm  Nếu (x,y)   E • x gọi là đỉnh gốc, y là ngọn • Nếu x ≡ y, (x,y) gọi là khuyên  Một dãy u1,u2,…,un,  ui   V (i=1,n) gọi là một  đường, nếu (ui­1,ui)   E  Độ dài đường: length(u1,u2,…,un)=n  (u1,u2,…,un) đường đi đơn, nếu ui≠uj, 1< i≠j Các khái niệm (tt)  Chu trình (cycle) = (u1,u2,…,un), u1≡ un  Đồ thị định hướng (directed graph)  (x,y) E : (x,y) ≠ (y,x)  Đồ thị vô hướng  (x,y) E : (y,x) E  (x,y) ≡ (y,x) Các khái niệm (tt)  CBDC là một chu trình B B A C A C Đường đi đơn D D Chu trình Các khái niệm (tt) Đồ thị vô hướng Đồ thị định hướng Các khái niệm (tt)  Tính liên thông (connectivity)  Trong đồ thị G, hai đỉnh x,y gọi là liên thông (connected), nếu có một đường từ x đến y  Đồ thị G liên thông, nếu (x,y) E, đường đi từ x đến y  Đồ thị G gọi là có trọng số, nếu mỗi cung được  gán một giá trị số đặc trưng Các khái niệm (tt) Đồ thị liên thông Đồ thị không liên thông Các khái niệm (tt)  Đồ thị có trọng số 0 10 20 1 1 2 4 5 3 Biểu diễn đồ thị  Biểu diễn bằng ma trận kề  Adjacency matrice  Biểu diễn bằng danh sách kề  Adjacency list Biểu diễn bằng ma trận kề  Xét G=(V,E) với V={x1,…,xn}  Biểu diễn G bằng ma trận A=(aij), i,j=1..n  aij=1, nếu Ǝ (xi,xj)  E  aij=0, nếu !Ǝ (xi,xj)  E Biểu diễn bằng ma trận kề(tt) A[i][j] 0 1 2 3 0 0 0 1 1 0 1 1 0 1 1 1 2 1 1 0 1 2 3 0 1 1 0 3 0     1     1     0 1     0     1     1 A =  1     1     0     1 0     1     1     0 Biểu diễn bằng ma trận kề(tt) A[i][j] 0 1 2 3 0 0 1 1 1 0 1 0 0 0 1 2 0 0 0 1 1 2 3 0 0 0 0 3 0     1     1     1 0     0     0     1 A =  0     0     0     1 0     0     0     0 Biểu diễn bằng ma trận kề(tt) x2 0 1 1 0 0 x1 x3 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 x5 x4 1 0 0 1 0 Biểu diễn bằng ma trận kề (tt) x2 0 1 1 0 0 x1 x3 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 x5 x4 1 0 0 1 1 Biểu diễn bằng ma trận kề (tt) A[i][j] 0 1 2 3 0 0 20 10 1 1 20 0 0 5 0 2 10 0 0 4 20 10 3 1 5 4 0 1 1 2 5  0     20     10     1 4 20     0       0      5 3 A =  10     0       0      4  1      5       4      0 Biểu diễn bằng ma trận kề (tt)  Chú ý  Đối với đồ thị không định hướng, ma trận kề là ma trận đối xứng  Đối với đồ thị định hướng, số lượng phần tử 0 khá lớn  Đối với đồ thị có trọng số, thay thế giá trị 1 bằng giá trị trọng số Biểu diễn đồ thị bằng danh sách kề  Là một mảng các danh sách  Ở đây, n hàng của ma trận kề thay thế bằng n  danh sách liên kết động  Mỗi đỉnh của G có một danh sách, mỗi nút  trong danh sách thể hiện các đỉnh lân cận của  nút này  Cấu trúc mỗi nút • id: tên đỉnh (chỉ số, danh hiệu) • next: con trỏ đến nút kế tiế ...