intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thị

Chia sẻ: Đinh Gấu | Ngày: | Loại File: PPT | Số trang:24

84
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nhằm giúp các bạn có thêm tài liệu phục vụ nhu cầu học tập và nghiên cứu về Công nghệ thông tin, mời các bạn cùng tham khảo nội dung "Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thị" dưới đây. Nội dung bài giảng cung cấp cho các bạn những kiến thức về đồ thị, khái niệm về đồ thị, biểu diễn đồ thị, phép duyệt đồ thị và tìm đường đi ngắn nhất. Hy vọng đây là tài liệu tham khảo hữu ích cho các bạn.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - Chương 6: Đồ thị

  1. CHƯƠNG 6 ĐỒ THỊ 1
  2. Chương 6: Đồ thị 6.1 Định nghĩa và các khái niệm 6.2 Biểu diễn đồ thị 6.3 Phép duyệt đồ thị 6.4 Tìm đường đi ngắn nhất   2
  3. 6.1­Định nghĩa và khái niệm Đồ thị là một cấu trúc rời rạc gồm các đỉnh và  các cạnh (vô hướng hoặc có hướng) nối các  đỉnh đó . Nhiều bài toán thuộc những lĩnh vực rất khác  nhau có thể giải được bằng mô hình đồ thị:  biểu diễn sự cạnh tranh các loài trong một  môi trường sinh thái, hai máy tính có được  nối với nhau bằng một đường truyền thông  hay không. tìm đường đi ngắn nhất giữa hai  thành phố, lập lịch thi, phân chia kênh cho  các đài truyền hình …   3
  4. 6.1­Định nghĩa và khái niệm Khi mô hình hoá bằng đồ thị: đỉnh biểu thị  các đối tượng được xem xét (người, tổ  chức, địa danh,...), cạnh đồ thị là những  đoạn thẳng (hoặc cong) hay những mũi tên  nối một số điểm với nhau, tượng trưng  cho một quan hệ nào đó giữa các đối  tượng. Các loại đồ thị : Một đơn đồ thị G = (V, E) gồm một tập  khác rỗng V mà các phần tử của nó gọi là  các đỉnh và một tập E là các cạnh gồm các  cặp không có thứ tự của các đỉnh phân  biệt.   4
  5. 6.1­Định nghĩa và khái niệm Một đơn đồ thị có hướng G = (V, E) gồm  một tập khác rỗng V mà các phần tử của  nó gọi là các đỉnh và một tập E các cặp có  thứ tự gồm 2 phần tử khác nhau của V  gọi là các cung. Một đa đồ thị G = (V, E) giống như đơn đồ  thị, có thể có cạnh bội (có nhiều hơn hai  cạnh tương ứng với một cặp đỉnh) và  khuyên (cạnh nối đỉnh với chính nó).   5
  6. 6.1­Định nghĩa và khái niệm v1 v2 v3 v4 v5 v6   6
  7. 6.1­Định nghĩa và khái niệm Các thuật ngữ về đồ thị : Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được  gọi là liền kề nếu (u,v) E. Nếu e = (u,v) thì e gọi là  cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được  gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là  các điểm đầu mút của cạnh e. Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là  số các cạnh liên thuộc với nó. Khuyên tại một đỉnh  được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô  lập nếu deg(v)=0    7
  8. 6.1­Định nghĩa và khái niệm v1 v2 v3 v4 v5 v6 v7   8
  9. 6.1­Định nghĩa và khái niệm Bậc vào (t.ư. bậc ra) của đỉnh v trong đồ thị có hướng  G, ký hiệu degt(v) (t.ư. dego(v)), là số các cung có đỉnh  cuối (đỉnh đầu) là v. Đỉnh có bậc vào và bậc ra cùng bằng 0 gọi là đỉnh cô  lập. Đỉnh có bậc vào bằng 1 và bậc ra bằng 0 gọi là  đỉnh treo, cung có đỉnh cuối là đỉnh treo gọi là cung  treo Cho G =(V, E) là một đồ thị có hướng. Khi đó  deg t (v) deg o (v) | E | v V v V   9
  10. 6.2­ Biểu diễn đồ thị 621. Ma trận kề: Cho đồ thị vô hướng  G=(V,E), v1, v2, ..., vn là các đỉnh và e1, e2, ..., em là  các cạnh của G. Ma trận kề của G là ma trận A {( aij ) : i, j 1,2,..., n } aij bằng 1 nếu cạnh (i,j)  E và bằng 0 nếu ngược  lại. Rõ ràng ma trận kề của đồ thị vô hướng là  đối xứng. Ngoài ra, aij có thể gán một số nào đó gọi là trọng  số. Lúc đó, ta có ma trận trọng số. Nhược điểm là luôn phải dùng n2 đơn vị bộ nhớ để  lưu trữ ma trận kề.   10
  11. 6.2­ Biểu diễn đồ thị e6 v1 v2 v3 e3 e4 e1 e5 e2 0 0 0 1 1 v4 v5 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 0 1 0 Ví dụ: Ma trận kề của đồ thị    11
  12. 6.2­ Biểu diễn đồ thị 622. Danh sách kề: Mỗi đỉnh v của đồ thị có  danh sách lưu trữ các đỉnh kề với nó, ký hiệu  Ke(v): Ke(v)={ u V: (v,u) E} Người ta có thể dùng mảng hoặc danh sách liên  kết cho Ke(v). Chúng ta phải dùng m+n đơn vị  bộ nhớ để lưu trữ danh sách k e ề. 6 v1 v2 v3 e3 e4 e1 e5 e2 v4 v5   12
  13. 6.3­ Duyệt đồ thị Tìm kiếm theo chiều sâu:  void main() {  for v   V do chuaxet[v]:=true;        for v   V do if  (chuaxet[v]) then DFS(v); } void DFS(v) {    thamdinh(v); chuaxet[v]:=false;  for u   Ke(v) do if  (chuaxet[u]) DFS(u); }   13
  14. 6.3­ Duyệt đồ thị 3 6 4 2 5 7 1 10 8 9 11 12 Kết quả tìm kiếm theo  chiều sâu: 1, 2, 10, 4,  13 3, 5, 8, 6, 7, 9, 12, 11,  13    14
  15. 6.3­ Duyệt đồ thị Đặc điểm: ­ Mỗi đỉnh được thăm đúng 1 lần. ­ Mỗi lần quay về chương trình chính, thuật  toán se tạo ra một thành phần liên thông  mới. ­ Độ phức tạp của thuật toán là O(n+m).   15
  16. 6.3­ Duyệt đồ thị Tim kiem theo chieu rong:  void main() { for (v   V) chuaxet[v]:=true;        for (v   V) do if  (chuaxet[v])    BFS(v); }   16
  17. 6.3­ Duyệt đồ thị void BFS(v) { Queue:= ; Queue  v; (*nap v vao Queue *)     chuaxet[v]:=false; while (Queue ≠  ) {   p  Queue;  thamdinh(p);  for (u   Ke(p))         if  (chuaxet[u]) {Queue  u; chuaxet(u):=false;} } }   17
  18. 6.4­ Đường đi ngắn nhất Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là  một số nguyên dương trong đồ thị G=(V,E) là  một dãy các cạnh (hoặc cung) e1, e2, ..., en của  đồ thị sao cho e1=(x0,x1),e2=(x1,x2), ...,en=(xn­1,xn),  với x0=u và xn=v. Trong đồ thị đơn, ta ký hiệu  đường đi này bằng dãy các đỉnh x0, x1, ..., xn. Nếu mỗi cung được đặt tương ứng một số thực  a(xi,xj) gọi là trọng số, lúc đó độ dài đường đi là: a(xi­1,xj)  với i=1 đến n   18
  19. 6.4­ Đường đi ngắn nhất Thuật toán Dijkstra: ­Đầu vào: Đồ thị G=(V,E) biểu diễn bằng  ma trận trọng số a[u,v] với u,v   V ­Điều kiện: a[u,v] >= 0 ­Đầu ra: Khoảng cách từ đỉnh s (đỉnh bắt  đầu cho trước) đến tất cả các đỉnh còn  lại ký hiệu d[v]. truoc[v] ghi nhận đỉnh đi  trước v trong đường đi ngắn nhất từ s  đến v. ­Ký hiệu: T là tập hợp chứa các đỉnh có  nhãn tạm thời.   19
  20. 6.4­ Đường đi ngắn nhất void dijkstra() {for (v   V)   {d[v]=a[s,v]; truoc[v]=s;} d[s]=0; T= V \ {s}; while (T≠ ) {tìm đỉnh u   T thỏa mãn d[u]=min{d[z]: z    T} T= T \ {u}; //cố định nhãn của đỉnh u   20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2