Duyệt đồ thị

Lý thuyết đồ thị
NGUYỄN TUẤN ANH, ĐH MỎ ĐỊA CHẤT
[email protected]
www.humg.edu.vn/cntt
01.68.638.16.92
http://baigiang.violet.vn


Chương 3

CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG

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.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 quyế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)
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
3.1. Phép duyệt một đồ thị
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.
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);
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)
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);
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
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);
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
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);
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
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);
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
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);
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
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);
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
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)

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.
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.
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.
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.
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 ?