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 và giải thuật: Chương 8 - Đỗ Bích Diệp

Chia sẻ: Nguyên Phương | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST
Báo xấu
57
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 8: Cấu trúc đồ thị" cung cấp cho các bạn sinh viên các kiến thức: Các khái niệm cơ bản, biểu diễn đồ thị, duyệt đồ thị, bài toán áp dụng. Đây là một tài liệu hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu tham khảo và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - Đỗ Bích Diệp

  1. Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu và Giải thuật 1843 ORD SFO 802 7 4 1 337 1233 LAX DFW Chương VIII: Cấu trúc Đồ thị Đỗ Bích Diệp - Khoa CNTT Chương VIII: Đồ thị z Nội dung 1. Các khái niệm cơ bản 2. Biểu diễn đồ thị 1. Ma trận lân cận 2. Danh sách lân cận 3. Duyệt đồ thị 4. Bài toán áp dụng 1. Tìm cây khung cực tiểu 2. Tìm đường đi ngắn nhất 3. Bài toán bao đóng truyền ứng 4. Bài toán sắp xếp tô pô Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 1
  2. Cấu trúc dữ liệu và Giải thuật Đồ thị – Một đồ thị G = (V, E) trong đó z V: tập các đỉnh (vertices) z E: tập các cung (edges) nối các đỉnh trong V – Một cung e = (u,v) là một cặp đỉnh – Ví dụ: a b V= {a,b,c,d,e} E= c {(a,b),(a,c),(a,d), (b,e),(c,d),(c,e), d e (d,e)} Đỗ Bích Diệp - Khoa CNTT Các khái niệm liên quan – Đồ thị có hướng và Đồ thị vô hướng 1 2 1 2 5 3 4 3 4 Trong một cung, thứ tự của Trong một cung, thứ tự của các đỉnh là quan trọng các đỉnh là không quan trọng Cung (u,v) khác với cung (v,u) Cung (u,v) cũng giống như cung (v,u) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 2
  3. Cấu trúc dữ liệu và Giải thuật Các khái niệm liên quan z Bậc của một đỉnh (Degree): Là số cung kề với đỉnh – Trong một đồ thị có hướng, một đỉnh có thể có z Bậc trong (in-degree) z Bậc ngoài (out-degree) – Ví dụ: z Đỉnh 1 có bậc 3 z Đỉnh 1 có bậc trong là 1 và bậc ngoài là 2 1 2 3 4 Đỗ Bích Diệp - Khoa CNTT Các khái niệm liên quan z Đỉnh lân cận (Adjacent vertices) 1 2 – Trong đồ thị z 1, 2 là lân cận của nhau z 1,3 là lân cận của nhau 3 4 z …. z Cung kề (Incident edges) – Nếu có cung (u,v) thì cung này là cung kề của hai đỉnh u và v Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 3
  4. Cấu trúc dữ liệu và Giải thuật Các khái niệm liên quan z Đường đi – Dãy các đỉnh v1,v2,. . .vk mà tồn tại cung (vi, vi+1) trong đồ thị ( i = 1 .. k-1) 1 2 z Đường đi đơn – Đường đi với các đỉnh không lặp lại z Chu trình 3 4 – Đường đi đơn với đỉnh đầu và cuối trùng nhau z Độ dài đường đi Path : 1, 2, 4, 3, 1, 4 – Số cung trên đường đi z Đồ thị con Đỗ Bích Diệp - Khoa CNTT Các khái niệm liên quan z Đồ thị liên thông (Connected Graph) 1 2 1 2 5 3 4 3 4 5 Đồ thị liên thông 1 2 1 2 3 3 4 Đồ thị không liên thông Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 4
  5. Cấu trúc dữ liệu và Giải thuật Các khái niệm liên quan z Đồ thị trọng số (Weight Graph) 5 60 1 2 140 100 100 3 4 110 Đỗ Bích Diệp - Khoa CNTT Kiểu dữ liệu trừu tượng Đồ thị z Dữ liệu: Một tập không rỗng các đỉnh chứa các phần tử có kiểu nhất định, một tập không rỗng các cung có thể biểu diễn các phần tử có kiểu nhất định z Các thao tác cơ bản – Graph create() – endVertices(e) – insertVertex( o) – opposite(v, e) – insertEdge(u, v, o) – areAdjacent(v, w) – removeVertex(v) – adjacentVertices(v) – removeEdge(e ) – incidentEdges(v) – vertices() – edges() – numVertices() – numEdges() Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 5
  6. Cấu trúc dữ liệu và Giải thuật Một số tính chất của đồ thị 1. Nếu một đồ thị G có m cung thì tổng bậc của các đỉnh trong G sẽ là 2m 2. Nếu một đồ thị có hướng có m cung thì tổng bậc trong của các đỉnh , tổng bậc ngoài của các đỉnh đều là m 3. Nếu đồ thị G là đồ thị đơn giản, G có n đỉnh và m cung thì 1. Nếu G là đồ thị vô hướng m ≤ n(n-1)/2 2. Nếu G là đồ thị có hướng thì m ≤ n(n-1) Đỗ Bích Diệp - Khoa CNTT Biểu diễn đồ thị – Biểu diễn bằng ma trận lân cận z Đánh số các đỉnh trong tập V từ 1 đến n z Ma trận biểu diễn đồ thị A (n x n) – Aij = 1 nếu trong G tồn tại cung (i,j) – Aịj = 0 nếu trong G không tồn tại cung đó z Với đồ thị vô hướng thì nếu Aij = 1 thì Aji = 1 z A được gọi là ma trận lân cận của G Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 6
  7. Cấu trúc dữ liệu và Giải thuật Biểu diễn đồ thị bằng ma trận lân cận z Ví dụ 1 2 ⎡0 1 0 1⎤ ⎢0 ⎥ 0 0 1⎥ ⎢ ⎢1 1 0 0⎥ 3 4 ⎢ ⎥ ⎣0 1 1 0⎦ ⎡0 1 1 0 1⎤ ⎢1 0 1 0 0⎥⎥ 1 2 ⎢ 5 ⎢1 1 0 1 0⎥ ⎢ ⎥ ⎢ 0 0 1 0 1⎥ 3 4 ⎢⎣1 0 0 1 0⎥⎦ Đỗ Bích Diệp - Khoa CNTT Biểu diễn đồ thị bằng danh sách lân cận – Biểu diễn bằng danh sách lân cận z Mỗi đỉnh trong đồ thị sẽ ứng với một danh sách móc nối chứa các đỉnh lân cận của nó z Mỗi nút trong danh sách có quy cách VERTEX LINK – VERTEX chứa giá trị tương ứng với số thứ tự của đỉnh lân cận – LINK chứa con trỏ trỏ tới nút tiếp theo trong danh sách z Mỗi danh sách như vậy có một nút đầu danh sách z Các nút đầu này là các phần tử của một vector V có kích thước n. Phần tử V[i] ứng với danh sách lân cận của nút thứ i Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 7
  8. Cấu trúc dữ liệu và Giải thuật Biểu diễn đồ thị bằng danh sách lân cận z Ví dụ 1 2 V[1] 2 4 V[2] 4 V[3] 1 2 3 4 V[4] 2 3 z 1: (2,4) 2: (4) 3: (1, 2) 4: (2, 3) Đỗ Bích Diệp - Khoa CNTT Biểu diễn đồ thị bằng danh sách lân cận V[1] 2 3 5 1 2 1 V[2] 3 5 V[3] 1 2 4 3 4 V[4] 3 5 V[5] 1 4 z 1: (2,3,5) 2: (1,3) 3: (1,2,4) 4: (3,5) 5: (1,4) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 8
  9. Cấu trúc dữ liệu và Giải thuật Phép duyệt đồ thị z Cho một đồ thị G(V,E) và một đỉnh v thuộc V. Duyệt đồ thị là thăm mọi đỉnh liên thông với v – Có 2 phương pháp z Phương pháp duyệt theo chiều sâu (Depth First Search) z Phương pháp duyệt theo chiều rộng ( Breadth First Search) Đỗ Bích Diệp - Khoa CNTT Duyệt theo chiều sâu Algorithm DFS(G, v) Input đồ thị G và đỉnh bắt đầu duyệt v trong G Output đánh dấu các cung trong G trong phần đồ thị liên thông với đỉnh v thành hai loại cung khám phá (discovery edges) và cung quay lui (back edges) setLabel(v, VISITED) // đỉnh v đã được thăm for all e ∈ G.incidentEdges(v) if getLabel(e) = UNEXPLORED w ← opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) DFS(G, w) else setLabel(e, BACK) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 9
  10. Cấu trúc dữ liệu và Giải thuật Duyệt đồ thị theo chiều sâu A A Đỉnh chưa thăm A Đỉnh đã thăm B D E Cung chưa thăm Cung khám phá C Cung quay lui A A B D E B D E C C Bắt đầu xuất phát từ A Đỗ Bích Diệp - Khoa CNTT Duyệt đồ thị theo chiều sâu A A B D E B D E C C Tất cả các cung kề của D đã duyệt Xét tiếp các cung kề của đỉnh C A A B D E B D E C C Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 10
  11. Cấu trúc dữ liệu và Giải thuật Duyệt đồ thị theo chiều sâu z Duyệt theo chiều sâu trên đồ thị có hướng – Đi theo chiều của các cung trên đồ thị D E B C A Đỗ Bích Diệp - Khoa CNTT Duyệt đồ thị theo chiều rộng Algorithm BFS(G, s) Q = một queue rỗng Q.enqueue(s) setLabel(s, VISITED) while not Q.isEmpty() v = Q.dequeue() for all e ∈ G.incidentEdges(v) if getLabel(e) = UNEXPLORED w ← opposite(v,e) if getLabel(w) = UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, VISITED) Q.enqueue(w) else setLabel(e, BACK) Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 11
  12. Cấu trúc dữ liệu và Giải thuật Duyệt đồ thị theo chiều rộng L0 A Đỉnh chưa thăm A A Đỉnh đã thăm L1 B C D Cung chưa thăm Cung khám phá E F Cung quay lui L0 L0 A A L1 L1 B C D B C D E F E F Đỗ Bích Diệp - Khoa CNTT Duyệt đồ thị theo chiều rộng L0 L0 A A L1 L1 B C D B C D L2 E F E F L0 L0 A A L1 L1 B C D B C D L2 L2 E F E F Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 12
  13. Cấu trúc dữ liệu và Giải thuật Duyệt đồ thị theo chiều rộng L0 L0 A A L1 L1 B C D B C D L2 L2 E F E F L0 A L1 B C D L2 E F Đỗ Bích Diệp - Khoa CNTT Duyệt đồ thị theo chiều sâu z Duyệt đồ thị theo chiều rộng trên đồ thị có hướng D E B C A Đỗ Bích Diệp - Khoa CNTT Đỗ Bích Diệp - Khoa CNTT - ĐHBK HN 13
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

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