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
Duyệt cây theo chiều sâu DFS (Depth First Search)
Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong mảng chuaxet[] có giá trị FALSE. Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng có giá trị TRUE. Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE.
shellscript
1void DFS( int v){
2
3 Thăm_Đỉnh(v);
4
5 chuaxet[v]:= FALSE;
6
7 for ( u ∈ke(v) ) {
8
9 if (chuaxet[u] ) DFS(u);
10
11 }
12
13}
Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông vớimỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông vớimỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông vớimỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:
Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông vớimỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:
shellscript
1for (i=1; i≤n ; i++)
2
3 chuaxet[i]:= TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/
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.