Bài giảng Toán rời rạc 2 - Chương 2: Các thuật toán tìm kiếm trên đồ thị

CHꢀƠNG 2. CÁC THUꢁT TOÁN TỊM KÍM TRÊN Đꢂ THꢃ

Đặt bài toán:

Input: Đồ thị G = (V, E) gồm n đỉnh, m cạnh;

Một đỉnh u  G;

Output: Thứ tự thăm các đỉnh v  G bắt đầu từ đỉnh u;

1

2.1 Thuꢄt toán tìm kiếm theo chiều sâu (Depth - first Search)

2.1.1 Giới thiệu thuꢄt toán

- Bước khởi tạo: Tất cả các đỉnh v  G chưa được xét (vs[v]= 0);

- Bước 1: Tìm kiếm theo chiều sâu bắt đầu từ v = u bằng cách thăm v

và đánh dấu v được xét (vs[v] = 1);

- Bước 2: Chọn một đỉnh t kề với v và chưa được xét;

- Bước 3: Nếu chọn được t thì quay lại bước 1 với t đóng vai trò u;

- Bước 4: Nếu không chọn được t thì quay lại bước 2 và đỉnh đóng

vai trò v là đỉnh i có thứ tự duyệt ngay trước v;

- Bước 5: Nếu tất cả các đỉnh kề của u đều đã được xét thì dừng;

2

2.1.2 Mô tả thuꢄt toán

Thuꢄt toán: DfsDequy(u){

Thăm(u);

vs[u] = 1;

for v  ke(u) do

if (vs[v] = 0) DfsDequy(v);

}

3

2.1.3 Cài đặt và kiểm nghiệm thuꢄt toán

Cài đặt 1: (Đệ qui)

// G cho bởi ma trận kề a[i][j]

int a[100][100], vs[100], n, u;

void DfsDequy(int u)

{ int v;

cout << u << ” ”;

vs[u]= 1;

for (v= 1; v<=n; v++)

if (vs[v]==0 && a[u][v]==1) DfsDequy(v);

}

4

Cài đặt 2: (Sử dụng ngăn xếp)

// G cho bởi ma trận kề a[i][j]

int vs[100], n, u, s[100];

void DfsNx(int u)

{ int top = 1; s[top] = u; vs[u] = 1;

while (top > 0){

int v = s[top];

for (int i= 1; i<=n; i++) { int ok = 1;

if (vs[i]==0 && a[v][i]==1) {

top++; s[top] = i; vs[i] = 1; int ok = 0;

break; }

if (ok) top--;

}

5

2.2 Thuꢄt toán tìm kiếm theo chiều rộng (Breadth - first Search)

2.2.1 Giới thiệu thuꢄt toán

- Bước khởi tạo: Tất cả các đỉnh v  G chưa được xét (vs[v]= 0);

- Bước 1 : Xây dựng hàng đợi q bắt đầu từ u và đánh dấu u đã xét

(vs[u] = 1);

- Bước 2 (lặp): Nếu q rỗng thì kết thúc. Ngược lại, lấy v ra khỏi hàng

đợi và thăm v;

- Bước 3: Đưa vào hàng đợi tẩt các đỉnh i kề với v và chưa được xét,

đánh dấu i đã xét (vs[i]= 1);

- Bước 4: Quay lại bước 2.

6

2.2.2 Mô tả thuꢄt toán

Thuꢄt toán: Bfs(u){

q = ;

<Đưa u vào q>;

vs[u] = 1;

while q ≠  { <Lấy v ra khỏi q>; Thăm(v);

for i  ke(v) do

if (vs[i] = 0)

{<Đưa i vào q>; vs[i] = 1;

}

7

2.2.3 Cài đặt và kiểm nghiệm thuꢄt toán

// G cho bởi ma trận kề a[i][j]

int vs[100], n, u, q[100];

void bfs(int u)

{ int v, dq = cq = 1; q[cq] = u; vs[u] = 1;

while (dq <= cq){

v = q[dq]; dq++; cout << v << ” ”;

for (int i= 1; i<=n; i++)

if (vs[i]==0 && a[v][i]==1) {

cq++; q[cq] = i; vs[i] = 1; }

}

8

2.3 ꢅng dụng cꢆa các thuꢄt toán tìm kiếm trên đꢇ thꢈ

2.3.1 Duyệt tất cả các đꢉnh cꢆa đꢇ thꢈ

Input: Đồ thị G = (V, E) gồm n đỉnh, m cạnh;

Output: Thứ tự thăm tất cả các đỉnh v  G bắt đầu từ đỉnh 1;

9

Giải thuꢄt 1: Duyệt tất cả các đỉnh của đồ thị;

- Bước khởi tạo: Tất cả các đỉnh v  G chưa được thăm (vs[v]= 0);

- Bước 1: Nếu tất cả các đỉnh đều được thăm thì kết thúc;

- Bước 2: Chọn v  G chưa được thăm (bắt đầu từ v = 1);

- Bước 3: Duyệt theo chiều sâu/chiều rộng (DFS/BFS) bắt đầu từ v;

- Bước 4: Quay lại bước 1;

10

Cài đặt 1 (Sử dụng DFS):

void Duyet1(){int v;

for (v = 1; v <= n; v++) vs[v] = 0;

for (v = 1; v <= n; v++)

if (vs[v] == 0) dfsDequy(v);

}

11

Cài đặt 2 (Sử dụng BFS):

void Duyet2(){int v;

for (v = 1; v <= n; v++) vs[v] = 0;

for (v = 1; v <= n; v++)

if (vs[v] == 0) Bfs(v);

}

12

2.3.2 Tính liên thông cꢆa đꢇ thꢈ

1) Đꢊờng đi trên đꢇ thꢈ

Khái niệm

- Đừng đi độ dài k từ u tới v  G là dãy các đỉnh x₀, x₁, ... , x_k,

trong đó x₀= u, x_n= v và (x_i-1, x_i)  E, 1 ≤ i ≤ k.

- Đừng đi là chu trình nếu bắt đầu và kết thúc tại c̀ng một đỉnh, tức

là u = v.

- Đừng đi hoặc chu trình là đơn nếu không chứa một cạnh quá một

lần.

- Đừng đi là đừng đi sơ cấp nếu đi qua các đỉnh không quá một

lần, trừ đỉnh đầu và đỉnh cúi.

- Đừng đi sơ cấp có đỉnh đầu và đỉnh cúi tr̀ng nhau được là chu

trình sơ ćp.

13

Đếm đꢊờng đi gĩa các đꢉnh

Đꢈnh ĺ. Cho G là đồ thị với ma trận kề A gồm n đỉnh đánh ś 1, 2, …, n. Ś các

đừng đi khác nhau độ dài r từ i đến j, r nguyên dương, bằng giá trị của phần tử

(i, j) của ma trận A^r.

Ch́ng minh.

Theo định ngh̃a, a_ijtại vị tŕ (i, j) của ma trận A ch́nh là ś đừng đi độ dài 1

từ đỉnh i đến đỉnh j  với r = 1 định ĺ đúng.

Giả sử định ĺ đúng với r = k  A^k(i, j) là ś đừng đi khác nhau có độ dài k

từ i đến j.

Chứng minh định ĺ đúng với r = k+1. Vì A^k+1= A^kA  A^k(i, j)= b_i1a_1j+ b_i2a_2j

+ ... + b_ina_nj, trong đó b_ih= A^k(i, h) . Theo giả thiết quy nạp, b_ihlà ś đừng đi

độ dài k từ i đến h.

Đừng đi độ dài k+1 từ i đến j s̃ được tạo bởi đừng đi độ dài k từ i đến

đỉnh trung gian h và một cạnh từ h đến j.

Theo quy tắc nhân, ś các đừng đi như thế là t́ch của ś đừng đi độ dài k từ i

đến h tức là b_ihvà ś các cạnh từ h tới j, tức là a_hj. Khi cộng các t́ch này lại

theo tất cả các đỉnh trung gian ta được kết quả mong mún.

14

V́ dụ . Có bao nhiêu đừng đi độ dài 4 từ đỉnh 1 tới đỉnh 4 trong

đồ thị G dưới đây:

Giải:

Có ma trận kề của G:

0 1 1 0

1 0 0 1

0 1 1 0

8 0 0 8

0 8 8 0

8 0 0 8

















4

A =

 A =

 có 8 đừng đi từ đỉnh 1 đến 4.

















15

2) Tìm đꢊờng đi trên đꢇ thꢈ bắt đầu từ đꢉnh u

Input: Đồ thị G = (V, E) gồm n đỉnh, m cạnh;

Một đỉnh u  G;

Output: Đừng đi từ đỉnh u đến các đỉnh v  G;

16

Giải thuꢄt 2: Tìm đừng đi từ u đến các đỉnh của đồ thị;

//pr[v] là đỉnh trước của v trên đừng đi từ u đến v

- Bước khởi tạo: Tất cả v  G chưa được thăm (vs[v]= 0), pr[v] = 0;

- Bước 1: Duyệt theo chiều sâu/chiều rộng (DFS/BFS) bắt đầu từ u;

- Bước 2: Tại mỗi đỉnh v  G (trừ u) được duyệt đến cập nhật pr[v];

- Bước 3: (Trả lại kết quả) Xét v  G (trừ u):

Nếu vs[v] = 0  không có đừng đi từ u đến v;

Nếu vs[v] = 1  xuất đừng đi từ u đến v;

17

Cài đặt 1 (Sử dụng DFS):

// G cho bởi ma trận kề a[i][j]

int vs[100], n, u, pr[100];

void DfsDequy(int u) { int v;

vs[u]= 1;

for (v= 1; v<=n; v++)

if (vs[v]==0 && a[u][v]==1){ pr[v] = u; DfsDequy(v); }

}

18

Cài đặt 2 (Sử dụng BFS):

int vs[100], n, u, q[100], pr[100];

void bfs(int u) {

int v, dq = cq = 1;

q[cq] = u; vs[u] = 1; pr[u] = 0;

while (dq <= cq){

v = q[dq]; dq++;

for (int i= 1; i<=n; i++)

if (vs[i]==0 && a[v][i]==1) {

cq++; q[cq] = i; vs[i] = 1; pr[i] = v;

}

19

2)T́nh liên thông trong đꢇ thꢈ vô hꢊớng

Đꢈnh ngh̃a . Một đồ thị vô hướng liên thông  có đừng đi gĩa hai

đỉnh bất k̀.

 Đồ thị G không liên thông là hợp các đồ thị con liên thông, không

có đỉnh chung gọi là các th̀nh ph̀n liên thông của G.

 Đ̉nh v G l̀ đ̉nh ćt hay đ̉nh kh́p, đ̉nh trụ  xóa v và các

cạnh liên thuộc s̃ tạo ra một đồ thị con có nhiều thành phần liên

thông hơn G.

 Cạnh e  G l̀ cạnh ćt hay c̀u  khi xóa e s̃ được đồ thị con có

nhiều thành phần liên thông hơn G.

20