tailieunhanh - Depth-First Search (DFS)

DFS trên một đồ thị vô hướng cũng giống như khá phá một mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. | Các phương pháp duyệt đồ thị Các phương pháp duyệt đồ thị Duyệt theo chiều sâu Depth-First Search Duyệt theo chiều rOng Breadth-First Search Dương Anh Đức - Nhập môn Cấu trúc Dữ liệu và Giải thuật 1 Depth-First Search DFS Khai niêm DFS trên một đồ thị vô hướng cung giong như khám phá một mê cung với một cuộn chỉ và một thùng sớn độ đê đánh dấu tránh bị lác. Tá bát đáu tư đỉnh s buộc đáu cuộn chỉ váộ s vá đánh dấu đỉnh náy lá đã tham . Sáu độ tá đánh dấu s lá đỉnh hiên hánh u. Dương Anh Đức - Nhập môn Cấu trúc Dữ liêu và Giải thuật 4 2 Khai niệm Bây giờ ta đi theo cạnh u v bất kỳ. Nếu cạnh u v dân chúng ta đến đỉnh đã tham v ta quay trờ vế u. Nếu đỉnh v la đỉnh mời ta di chuyến đến v va khOng quến lam cuộn chỉ cua mình thếo. Đánh dấu đỉnh v la đã thãm . Đặt v thanh đỉnh hiến hanh va lăp lai cac bườc trườc. Dương Anh Đức - Nhập môn Cấu trúc Dữ liệu và Giải thuật 5 Khải niệm CuOì cung ta cO thế đi đến một điếm ma tai đo tất ca cac canh kế vời nO đếu dan chung ta đến cac đỉnh đã thãm . Khi đo ta sế quay lui bang cách cuọn ngườc cuọn chỉ va quay lai cho đến khi trờ lai mọt đỉnh kế vời mọt canh con chưa đườc kham pha. Lai tiếp tuc qui trình kham pha như trên. Khi chung ta trờ vế s va khong con canh nao kế vời no chưa bị kham pha la luc DFS dừng. Dương Anh Đức - Nhập môn Cảu trúc Dữ liệu vả Giải thuật 6