Nội dung bài học không khai báo từ viết tắt bằng thẻ abbr.
Nội dung bài học
Bài toán: Cho đồ thị G=(V, E). Trong đó V là tập đỉnh, E là tập cạnh của đồ thị. Hãy tìm đường đi từ đỉnh s ∈ Vtới đỉnh t ∈ V.
Thủ tục BFS(s) hoặc DFS(s) cho phép ta duyệt các đỉnh cùng một thành phần liên thông với s. Như vậy, nếu trong số các đỉnh liên thông với s chứa t thì chắc chắn có đường đi từ s đến t. Nếu trong số các đỉnh liên thông với s không chứa t thì không tồn tại đường đi từ s đến t. Do vậy, chúng ta chỉ cần gọi tới thủ tục DFS(s) hoặc BFS(s) và kiểm tra xem đỉnh t có thuộc thành phần liên thông với s hay không. Điều này được thực hiện đơn giản thông qua mảng trạng thái chuaxet[]. Nếu chuaxet[t] =False thì có nghĩa t cùng thành phần liên thông với s. Ngược lại chuaxet[t] = True thì t không cùng thành phần liên thông với s.
Để ghi nhận đường đi từ s đến t, ta sử dụng một mảng truoc[] thiết lập giá trị ban đầu là 0.Trong quá trình duyệt, ta thay thế giá trị của truoc[v] để ghi nhận đỉnh đi trước đỉnh v trong đường đi tìm kiếm từ s đến v. Khi đó, trong thủ tục DFS(v) ta chỉ cần thay đổi lại như sau:
shellscript
1void DFS( int v){
2
3 chuaxet[v]:= FALSE;
4
5 for ( u ∈ke(v) ) {
6
7 if (chuaxet[u] ) {
8
9 truoc[u]=v;
10
11 DFS(u);
12
13 }
14
15 }
16
17}
Đối với thủ tục BFS(v) được thay đổi lại như sau:
shellscript
1void BFS(int u){
2
3 queue = φ;
4
5 u <= queue; /*nạp u vào hàng đợi*/
6
7 chuaxet[u] = false;/* đổi trạng thái của u*/
8
9 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
10
11 queue<=p; /*lấy p ra từkhỏi hàng đợi*/
12
13 for (v ∈ke(p) ) {/* đưa các đỉnh v kềvới p nhưng chưa được xét vào hàng đợi*/
14
15 if (chuaxet[v] ) {
16
17 v<= queue; /*đưa v vào hàng đợi*/
18
19 chuaxet[v] = false;/* đổi trạng thái của v*/
20
21 truoc[v]=p;
22
23 }
24
25 }
26
27 } /* end while*/
28
29}/* end BFS*/
Kết quả đường đi được đọc ngược lại thông qua thủ tục Result() như sau:
shellscript
1void Result(void){
2
3 if(truoc[t]==0){
4
5 <Không có đường đi từs đến t>;
6
7 return;
8
9 }
10
11 j = t;
12
13 while(truoc[j]!=s){
14
15 <thăm đỉnh j>;
16
17 j=truoc[j];
18
19 }
20
21 <thăm đỉnh s>;
22
23}
Ví dụ. Tìm đường đi từ đỉnh 1 đến đỉnh 7bằng thuật toán tìm kiếm theo chiều rộng với đồ thị dưới đây:
Tìm đường đi giữa đỉnh 1 đến đỉnh 7 của đồ thị
Tìm đường đi giữa đỉnh 1 đến đỉnh 7 của đồ thị
Ta có, BFS(1) = 1,2,3,11,4,6,12,13,7,8,9,10,5. Rõ ràng chuaxet[7] = True nên có đường đi từ đỉnh 1 đến đỉnh 7. Bây giờ ta xác định giá trị trong mảng truoc[] để có kết quả đường đi đọc theo chiều ngược lại. Truoc[7] = 6; truoc[6] = 2; truoc[2] =1=> đường đi từ đỉnh 1 đến đỉnh 7 là 1 =>2=>6=>7.
Chương trình cài đặt
shellscript
1#include<iostream>
2
3#include<conio.h>
4
5using namespace std;
6
7#define MAX 100
8
9#define TRUE 1
10
11#define FALSE 0
12
13int n;//số đỉnh của đồ thị.
14
15int truoc[MAX], chuaxet[MAX], queue[MAX];//mảng đánh dấu.
16
17int A[MAX][MAX];// ma trận kề của đồ thị.
18
19int s;//đỉnh đầu.
20
21int t;//đỉnh cuối.
22
23
24void Init(void){
25
26 freopen("lienth.IN", "r",stdin);
27
28 cin>>n;
29
30 cout<<"So dinh do thi: "<<n<<endl;
31
32 cin>>s>>t;
33
34 cout<<"Dinh dau:"<<s<<endl;
35
36 cout<<"Dinh cuoi:"<<t<<endl;
37
38 for(int i=1; i<=n;i++){
39
40 for(int j=1; j<=n;j++){
41
42 cin>>A[i][j];
43
44 }
45
46 }
47
48 for(int i=1; i<=n;i++){
49
50 chuaxet[i]=TRUE;
51
52 truoc[i]=0;
53
54 }
55
56 fclose(stdin);
57
58}
59
60void Result(void){
61
62 if(truoc[t]==0){
63
64 cout<<"Khong co duong di tu "<<s<< " den "<<t;
65
66 return;
67
68 }
69
70 cout<<"Duong di tu "<<s<<" den "<<t<<" la: ";
71
72 int j = t;
73
74 cout<<t<<"<=";
75
76 while(truoc[j]!=s){
77
78 cout<<truoc[j]<<"<=";
79
80 j=truoc[j];
81
82 }
83
84 cout<<s;
85
86}
87
88/* Breadth First Search */
89
90void BFS(int s) {
91
92 int dauQ, cuoiQ, u;
93
94 dauQ=1;cuoiQ=1;//khởi tạo queue.
95
96 queue[dauQ]=s;chuaxet[s]=FALSE; //thêm đỉnh đầu vào queue.
97
98 while (dauQ<=cuoiQ){//queue chưa rỗng.
99
100 u=queue[dauQ];//lấy đỉnh u trong queue.
101
102 dauQ=dauQ+1;
103
104 for (int p=1; p<=n;p++){
105
106 if(A[u][p] && chuaxet[p]){
107
108 cuoiQ=cuoiQ+1;
109
110 queue[cuoiQ]=p;
111
112 chuaxet[p]=FALSE;
113
114 truoc[p]=u;
115
116 }
117
118 }
119
120 }
121
122}
123
124
125void main(void){
126
127 Init();
128
129 BFS(s);
130
131 Result();
132
133 getch();
134
135}
Ma trận liền kề lienth.IN
shellscript
113
21 7
30 1 1 0 0 0 0 0 0 0 1 0 0
41 0 0 1 0 1 0 0 0 0 0 0 0
51 0 0 1 0 0 0 0 0 0 0 0 0
60 1 1 0 0 1 0 0 0 0 0 0 0
70 0 0 0 0 0 0 0 1 1 0 0 0
80 1 0 1 0 0 1 1 0 0 0 0 0
90 0 0 0 0 1 0 0 0 0 0 0 0
100 0 0 0 0 1 0 0 0 1 0 0 0
110 0 0 0 1 0 0 0 0 0 0 0 1
120 0 0 0 1 0 0 1 0 0 0 0 0
131 0 0 0 0 0 0 0 0 0 0 1 1
140 0 0 0 0 0 0 0 0 0 1 0 1
150 0 0 0 0 0 0 0 1 0 1 1 0
Output của chương trình.
So dinh cua do thi: 13
Dinh dau: 1
Dinh Cuoi: 7
Duong di tu 1 den 7 la: 7<=6<=2<=1
NenTang.vn
Học lập trình - Làm chủ công nghệ
NenTang.vn là nền tảng học lập trình trực tuyến dành cho người Việt. Toàn bộ nội dung được biên soạn bởi chuyên gia, cập nhật liên tục và miễn phí cho cộng đồng.