Co ban ve Duyet do thi - Thuat toan DFS - BFS.ppt

Tìm kiếm chiều sâu và tìm kiếm chiều rộng đều là các phương pháp tìm kiếm có hệ thống và chắc chắn tìm ra lời giải. Tuy nhiên, do bản chất là vét cạn nên với những bài toán có không gian lớn thì ta không thể dùng hai chiến lược này được

1. 1
Chương 3
CÁC THUẬT TOÁN TÌM KIẾM
TRÊN ĐỒ THỊ VÀ ỨNG DỤNG

2. 2
NỘI DUNG
3.1. Phép Tìm kiếm (duyệt) đồ thị(Thăm các đỉnh
của đồ thị)
- Tìm kiếm theo chiều sâu (DFS)
- Tìm kiếm theo chiều rộng(BFS)
3.2. Tìm đường đi và kiểm tra tính liên thông
3.2.1. Bài toán tìm đường đi giữa hai đỉnh
3.2.3. Tìm các thành phần liên thông của đồ thị

3. 3
3.1. Phép tìm kiếm(duyệt) một đồ thị
•Xét một đồ thị không định hướng G (V, E) và một
đỉnh v trong V của G, ta cần thăm tất cả các đỉnh trong G
mà có thể “với tới” được từ đỉnh v (nghĩa là thăm mọi nút
liên thông với v).
Ta chú ý tới 2 cách giải quết trên đây:
- Phép tìm kiếm theo chiều sâu (Depth first search)
- Phép tìm kiếm theo chiều rộng (Breadth first search)

4. 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,6,7
3:2,4,5,7
4:3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
1
7
2
6
3
5 4
3.1. Phép duyệt một đồ thị

5. 5
3.1.1. Tìm kiếm(duyÖt) theo chiều sâu
(Depth-First Search)
•Đỉnh xuất phát v được thăm. Tiếp theo đó một đỉnh ω
chưa được thăm, mà là lân cận của v, sẽ được chọn và
một phép tìm kiếm theo chiều sâu xuất phát từ ω lại
được thực hiện.
–Khi một đỉnh u đã được “với tới” mà mọi đỉnh lân cận của nó
đều đã được thăm rồi, thì ta sẽ quay ngược lên đỉnh cuối cùng
vừa được thăm (mà có đỉnh ω lân cận với nó chưa được thăm),
và một phép tìm kiếm theo chiều sâu xuất phát từ ω lại được
thực hiện.
–Phép tìm kiếm sẽ kết thúc khi không còn một nút nào chưa được
thăm mà vẫn có thể với tới được từ nút đã được thăm.

6. 6
3.1.1. Duyệt theo chiều sâu
•Trong mô tả thuật toán duyệt theo chiều sâu (Depth-
First Search) để thăm dò các đỉnh của đồ thị G dưới
đây,thuật ngữ “Danh sách kề của v” là để chỉ tất cả
các đỉnh w Є V sao cho (v,w) Є E.
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc
cạnh (v,w) nếu cần;
+ DFS(w);

7. 7
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: DFS(3)
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

8. 8
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

9. 9
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2, 1
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

10. 10
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2, 1, 5
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

11. 11
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2, 1,
5, 4
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

12. 12
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2, 1,
5, 4, 6
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:2,3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);

13. 13
•Thì thứ tự các đỉnh được duyệt bắt đầu từ
đỉnh 3 theo thuật toán trên như sau: 3, 2, 1,
5, 4, 6, 7
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,4,6,7
3:2,4,5,7
4:3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
Procedure DFS(V:Đỉnh)
a.Đánh dấu v là đã duyệt;
b.For each w Є Danh sách kề của v
if w Chưa được đánh dấu Then
+ Xử lý với đỉnh w hoặc cạnh (v,w) nếu cần;
+ DFS(w);
DFS(7)
DFS(6)
DFS(4)
DFS(5)
DFS(1)
DFS(2)
DFS(3)

14. 14
3.1.2. Thuật toán duyệt theo chiều rộng
•Ý tưởng
–Đỉnh xuất phát v
–ở đây cũng được thăm đầu tiên, nhưng có khác với
DFS ở chỗ là: sau đó các đỉnh chưa được thăm mà
là lân cận của v sẽ được thăm kế tiếp nhau,
•rồi mớ đến các đỉnh chưa được thăm là lân cận lần lượt
của các đỉnh này và cứ tương tự như vậy.

15. 15
7.3.2.Thuật toán duyệt theo chiều rộng
Trong mô tả thuật toán duyệt các đỉnh của đồ thị G theo chiều rộng
(Breadth-First-Seach) dưới đây,thủ tục “Lấy đỉnh u đứng đầu tiên
trong hàng đợi có nghĩa là lấy đỉnh đứng ở vị trí đầu tiên (được đưa vào
trước),sau khi lấy xong,phần tử này không còn trong hàng đợi nữa.
Procedure BFS (v:Đỉnh);
a) Đưa v vào hàng đợi H;
b) Đánh dấu v là đã duyệt;
c) While Hàng_doi <> ΦDo
+) Lấy đỉnh u đứng đầu tiên trong hàng đợi;
+) For each w Є Danh sách kề của u
If w Chưa được duyệt Then
1.Thêm w vào sau hàng đợi;
2.Đánh dấu w là đã duyệt;
3.Xử lý với đỉnh w hoặc cạnh (u,w) nếu cần;
Mỗi đỉnh được thăm sẽ được nạp vào queue chỉ một lần vì vậy câu lệnh while
lặp lại nhiều nhất n lần.

16. 16
1
7
2
6
3
5 4
Ví dụ 1. Đồ thị G = {V,E} có 7 đỉnh
V = {1,2,3,4,5,6,7} được cho bởi danh
sách như sau:
1:2,5,6,7
2:1,3,6,7
3:2,4,5,7
4:3,5,6,7
5:1,3,4,6,7
6:1,2,4,5,7
7:1,2,3,4,5,6
CX[1]= 1, CX[2]=1, CX[3]=1,CX[4]=1,CX[5]=1, CX[6]=0, CX[7]=1;
BFS(3), H:
3, 2, 4, 5, 7, 1, 6
•áp dụng thuật toán BFS cho đồ thị trong ví dụ 1,và bắt đầu từ đỉnh 3, ta được các đỉnh theo thứ tự sau :3,2,4,5,7,1,6.

17. 17
3.2. Tìm đường đi và kiểm tra tính liên thông
3.2.1. Bài toán tìm đường đi giữa hai đỉnh
–Giả sử t và s là 2 đỉnh nào đó trong đồ thị.
–Hãy tìm đường đi giữa hai đỉnh này.

18. 18
3.2. Tìm đường đi và kiểm tra tính liên thông
3.2.2. Tìm các thành phần liên thông của đồ
thị:
–Hãy cho biết đồ thị có bao nhiêu thành phần liên
thông và từng thành phần liên thông của nó gồm
những thành phần nào ?

19. 19

20. 20

21. 21

22. 22

23. 23

24. 24

25. 25

26. 26

27. 27

28. 28