TAILIEUCHUNG - Các phương pháp duyệt đồ thị

DFS trên một đồ thị vô hướng cùng giống 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. Ta bắt đầu từ đỉnh S, buộc đầu cuộn chỉ vào S và đánh dấu đỉnh này là " đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u. | 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 Cau trúc Dữ liệu va 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 lap 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 CuOi 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 mot đỉnh kế vời mot 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

• Toán học
• thuật toán Depth First Search
• xác định đỉnh kề trong DFS
• độ phức tạp của thuật toán
• tài liệu học đại học
• các tính chất của BFS