THUẬT TOÁN TÌM KIẾM THEO CHIỀU SÂU (DFS)

Để 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.
void DFS( int v){
Thăm_Đỉnh(v); chuaxet[v]:= FALSE;
for ( u ∈ke(v) ) {
if (chuaxet[u] ) DFS(u);
}
}
Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với v mỗ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:
{
for (i=1; i≤ n ; i++)
chuaxet[i]:= TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/
for (i=1; i≤ n ; i++)
if (chuaxet[i] )
DFS( i);
}

Ví dụ. áp dụng thuật toán tìm kiếm theo chiều sâu với đồ thị trong hình sau: