Chương 1-Bài 13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++
legacy-admin-baitap-1
2 thg 2, 2025
1.471 lượt xem
1 giờ 9 phút
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
Lưu tiến độ học tập
Đăng nhập và ghi danh để lưu tiến độ, bình luận và nhận chứng chỉ. Mở trang khóa học