TAILIEUCHUNG - Phần tích thiết kế giải thuật (phần 10)

Trong tài liệu này các bạn sẽ gặp lại cách thể hiện dữ liệu qua đồ thị và thêm một phần quan trọng nữa là các bạn sẽ được tham khảo một số phương pháp duyệt đồ thị rất hiệu quả và cũng rất quan trọng trong ứng dụng | 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

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.