DFS - sâu
DFS
Ý tưởng của DFS: bắt đầu tại 1 đỉnh vo nào đó, chọn 1 đỉnh u bất kỳ kề với v0 và lấy nó làm đỉnh duyệt tiếp theo. Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh v0 với đỉnh bắt đầu là u.
Chú ý: sử dụng mảng chuxet[] gồm n phần tử (tương ứng với n đỉnh) để xác định phần tử đã đc duyệt.
Nếu vi đã duyệt, chuaxet[i] = FALSE và ngược lại
Thủ tục đệ quy DFS() được mô tả:
void DFS (int v) {
Thăm_Đỉnh (v); chuaxet[v] := FALSE;
for (u 'thuộc' ke(v) ) {
if (chuaxet[u] ) DFS (u);
}
}
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 1 lần
Để đảm bảo duyệt tất cả các đỉnh của đồ thị, ta cần:
{
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);
}
Bạn đang đọc truyện trên: AzTruyen.Top