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

Bài giảng Lý thuyết đồ thị: Chương 3 - Tôn Quang Toại

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:31

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

Bài giảng Lý thuyết đồ thị: Chương 3 Tìm kiếm trên đồ thị, cung cấp cho người đọc những kiến thức như: Một số khái niệm; Thuật toán tìm kiếm theo chiều rộng; Thuật toán tìm kiếm theo chiều sâu. Mời các bạn cùng tham khảo!

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 Lý thuyết đồ thị: Chương 3 - Tôn Quang Toại

  1. CHƯƠNG 3 TÌM KIẾM TRÊN ĐỒ THỊ Tôn Quang Toại Khoa CNTT, Đại học Ngoại ngữ ‐ Tin học TP.HCM
  2. Nội dung Một số khái niệm Thuật toán tìm kiếm theo chiều rộng Thuật toán tìm kiếm theo chiều sâu Ứng dụng
  3. Một số khái niệm Đường đi, chu trình Tính liên thông 2 đỉnh liên thông Đồ thị vô hướng liên thông Đồ thị có hướng Liên thông mạnh Miền liên thông Đỉnh khớp, cạnh cầu
  4. Một số khái niệm Đường đi (Path): Đường đi từ đỉnh x đến đỉnh y trong đồ thị G=(V, E) là một dãy các đỉnh liên tiếp nối đỉnh x đến đỉnh y:  trong đó: Độ dài đường đi: Là số cạnh của đường đi Đường đi đơn (simple): Là đường đi qua mỗi cạnh tối đa 1 lần.
  5. Một số khái niệm Chu trình (Cycle): Là đường đi có đỉnh đầu trùng với đỉnh cuối Chu trình đơn: Mỗi cạnh xuất hiện tối đa 1 lần trong chu trình
  6. Một số khái niệm Hai đỉnh liên thông: Hai đỉnh x, y được gọi là liên thông với nhau nếu có đường đi từ x đến y. Đồ thị liên thông: Đồ thị vô hướng G=(V, E)  được gọi là đồ thị liên thông nếu thì x liên thông với y.
  7. Một số khái niệm Đồ thị liên thông mạnh: Đồ thị có hướng G=(V,  A) được gọi là đồ thị liên thông mạnh nếu thì x liên thông với y. Thành phần liên thông: Là tập đỉnh liên thông với nhau và nếu bổ sung thêm 1 đỉnh khác thì không liên thông
  8. Một số khái niệm Cạnh cầu: Cho đồ thị G=(V, E). Cạnh gọi là cầu nếu xóa cạnh e thì số thành phần liên thông tăng lên Đỉnh khớp: Cho đồ thị G=(V, E). Đỉnh gọi là khớp nếu xóa các cạnh liên thuộc với v thì số thành phần liên thông tăng lên ít nhất là 2.
  9. Tìm kiếm trên đồ thị Tìm kiếm trên đồ thị: Cho đồ thị G=(V, E) và 1  đỉnh . Tìm kiếm trên đồ thị là phương pháp xuất phát từ đỉnh s, và theo các cạnh liên thuộc để viếng thăm (duyệt) các đỉnh của đồ thị sao cho mỗi đỉnh được viếng thăm 1 lần, nhằm tìm nghiệm của bài toán Ví dụ: Kiểm tra xem có đường đi từ đỉnh u đến đỉnh v không?  Kiểm tra đồ thị có liên thông hay không
  10. Tìm kiếm trên đồ thị Trong chương này chúng ta sẽ tìm hiểu hai thuật toán tìm kiếm cơ bản trên đồ thị: Thuật toán tìm kiếm theo chiều rộng (Breadth First Search ‐ BFS) Thuật toán tìm kiếm theo chiều sâu (Depth First Search ‐ DFS)  
  11. Tìm kiếm trên đồ thị theo chiều sâu Thuật toán tìm kiếm theo chiều sâu (DFS):  Input: G(V, E) và đỉnh Output: Dãy đỉnh được viếng thăm Bước 1: Viếng thăm đỉnh s  Bước 2: Tìm đỉnh u: u kề với s và u chưa được viếng thăm • Nếu có đỉnh u thì đặt s=u và quay về Bước 1 • Nếu không có đỉnh u thì quay về đỉnh trước đỉnh s, và tìm hướng đi khác. • Thuật toán dừng khi không thể quay về đỉnh trước.
  12. Tìm kiếm trên đồ thị theo chiều sâu Cài đặt: Cấu trúc dữ liệu Đồ thị: Giả sử đồ thị lưu trong danh sách kề LinkedList[] v; Dùng mảng bool[] visited để đánh dấu đỉnh đã viếng thăm hay chưa: • visited[i] = true: đỉnh i đã viếng thăm • visited[i] = false: đỉnh i chưa viếng thăm bool[] visited;
  13. Tìm kiếm trên đồ thị theo chiều sâu Cài đặt bằng Đệ quy void DFS(int s) { if (visited[s] == true) return; // Bước 1 visited[s] = true; // process node s:… // Bước 2 foreach (int u in v[s]) DFS(u); }
  14. Tìm kiếm trên đồ thị theo chiều sâu Cài đặt bằng Stack // Dùng stack void DFS(int s) { 1. Đánh dấu s đã viếng thăm 2. Đưa s vào stack 3. while stack chưa rỗng { { Đánh dấu v đã viếng thăm Đẩy u vào lại stack Đẩy v vào stack } } }
  15. Tìm kiếm trên đồ thị theo chiều rộng Thuật toán tìm kiếm theo chiều rộng (BFS):  Input: G(V, E) và đỉnh Output: Dãy đỉnh được viếng thăm Bước 1: Gọi S1={s}, viếng thăm các đỉnh trong S1 Bước 2: Tìm các đỉnh (gọi là S2) kề với một trong những đỉnh S1, và chưa được viếng thăm, rồi viếng thăm các đỉnh trong S2 Bước 3: Tìm các đỉnh (gọi là S3) kề với một trong những đỉnh S2 và chưa được viếng thăm, rồi viếng thăm các đỉnh trong S3 … Cho đến khi không thể tìm thêm các đỉnh để viếng thăm
  16. Tìm kiếm trên đồ thị theo chiều rộng 0 4 5 6 Ví dụ: 3 5 6 1 2 0 4 3 0 4 5 6 1 2 3 1 2 0 4 5 6 0 4 5 6 3 1 2 3 1 2
  17. Tìm kiếm trên đồ thị theo chiều rộng Nhận xét Những đỉnh gần với s nhất sẽ được viếng thăm  trước Các đỉnh chỉ được viếng thăm duy nhất 1 lần
  18. Tìm kiếm trên đồ thị theo chiều rộng Cài đặt: Cấu trúc dữ liệu Đồ thị: Giả sử đồ thị lưu trong danh sách kề LinkedList[] v; Dùng mảng bool[] visited để đánh dấu đỉnh đã viếng thăm hay chưa: • visited[i] = true: đỉnh i đã viếng thăm • visited[i] = false: đỉnh i chưa viếng thăm bool[] visited;
  19. Tìm kiếm trên đồ thị theo chiều rộng Cài đặt: Cấu trúc dữ liệu Dùng queue để lưu trật tự các đỉnh được xử lý • Đỉnh mới sẽ được thêm vào cuối queue • Đỉnh ở đầu queue sẽ là đỉnh kế tiếp được xử lý Queue q;
  20. Tìm kiếm trên đồ thị theo chiều rộng Cài đặt bằng hàng đợi void BFS(int s) { visited[s]=true; q.Enqueue(s); // Process node s while(q.Count!=0) { s = q.Dequeue(); foreach (int u in v[s]) { if (visited[u]) continue; visited[u]=true; q.Enqueue(u); // Process node u } } }
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
2=>2