CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG
Tìm kiếm theo chiều sâu DFS(Depth First Search)
Ý tưởng: Bắt đầu từ một đỉnh v0 nào đó của đồ thị.
Sau đó chọn đỉnh v là đỉnh nào đó kề với đỉnh v0 rồi lập lại quá trình sau đối với đỉnh v: Ở bước tổng quát giả sử đang xét v nếu như trong số các đỉnh kề với v tìm được đỉnh u là chưa xét thì ta sẽ xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ nó ta sẽ tiếp tục quá trình tìm kiếm . Còn như nếu không còn đỉnh nào kề với v là chưa xét thì ta nói rằng ta đã duyệt xong đỉnh v và quay trở lại tìm kiếm từ đỉnh mà trước đó đến đỉnh v ( nếu v=v0 thì kết thúc tìm kiếm). Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm từ tất cả các đỉnh chưa xét kề với v.
Code:
PROCEDURE DFS(v)
{ Giả sử đồ thị cho bởi danh sách kề. Tìm kiếm theo chiều sâu bắt nguồn từ v.
Các biến chuaxet,ke là các biến toàn cục }
BEGIN
thamdinh(v);
chuaxet[v]:=false;
FOR u in ke(v) DO
IF chuaxet[u] THEN DFS(u);
END;
BEGIN
FOR v in V DO chuaxet[v]:=true;
FOR v in V DO
IF chuaxet[v] THEN DFS(v);
END.