Mục đích của BFS và DFS là gì?

Question

Tôi đã học được cách các thuật toán này hoạt động, nhưng chúng được sử dụng để làm gì?

Chúng ta sử dụng chúng để:

• tìm một nút nào đó trong một biểu đồ hoặc
• để tìm một con đường ngắn nhất hoặc
• để tìm một chu kỳ trong một đồ thị

?

Cả hai người trong số họ chỉ truy cập tất cả các nút và đánh dấu họ đã truy cập và tôi không thấy điểm làm việc đó.

Tôi sắp bị mất ở đây những gì tôi đang học.

Answer 1

BFS và DFS là các thuật toán tìm kiếm đồ thị có thể được sử dụng cho nhiều mục đích khác nhau.

Một ứng dụng phổ biến của hai kỹ thuật tìm kiếm là xác định tất cả các nút có thể truy cập từ một nút bắt đầu đã cho. Ví dụ, giả sử bạn có một bộ sưu tập các máy tính mà mỗi máy tính được nối mạng với một số máy tính khác. Bằng cách chạy BFS hoặc DFS từ một nút cụ thể, bạn sẽ khám phá tất cả các máy tính khác trong mạng mà máy tính ban đầu có khả năng nói trực tiếp hoặc gián tiếp. Đây là những máy tính được đánh dấu trở lại.

BFS cụ thể có thể được sử dụng để tìm đường đi ngắn nhất giữa hai nút trong biểu đồ không có trọng số. Giả sử, ví dụ, bạn muốn gửi một gói dữ liệu từ một máy tính trong một mạng khác, và các máy tính không được kết nối trực tiếp với nhau. Dọc theo lộ trình nào bạn nên gửi gói để đưa nó đến điểm đến càng nhanh càng tốt? Nếu bạn chạy một BFS và tại mỗi lần lặp có mỗi nút lưu một con trỏ đến nút "cha mẹ" của nó, bạn sẽ kết thúc tìm tuyến từ nút bắt đầu đến mỗi nút khác trong biểu đồ để giảm thiểu số lượng liên kết phải được duyệt qua để tiếp cận máy tính đích.

DFS thường được sử dụng làm chương trình con trong các thuật toán phức tạp hơn. Ví dụ, thuật toán của Tarjan để tính toán các thành phần được kết nối chặt chẽ dựa trên tìm kiếm theo chiều sâu. Nhiều kỹ thuật biên dịch tối ưu hóa chạy một DFS trên một biểu đồ được xây dựng thích hợp để xác định thứ tự áp dụng một loạt các hoạt động cụ thể. Tìm kiếm chiều sâu đầu tiên cũng có thể được sử dụng trong tạo mê cung: bằng cách lấy một mạng lưới các nút và liên kết mỗi nút với các láng giềng của nó, bạn có thể xây dựng một biểu đồ biểu diễn một lưới. Chạy tìm kiếm chiều sâu đầu tiên ngẫu nhiên trên biểu đồ này sau đó tạo ra một mê cung có chính xác một giải pháp.

Đây không phải là danh sách đầy đủ. Các thuật toán này có tất cả các loại ứng dụng và khi bạn bắt đầu khám phá các thuật toán nâng cao hơn, bạn thường sẽ thấy mình dựa vào DFS và BFS làm khối xây dựng. Nó tương tự như phân loại - phân loại bởi chính nó không phải là tất cả những gì thú vị, nhưng có thể sắp xếp một danh sách các giá trị là vô cùng hữu ích như là một chương trình con trong các thuật toán phức tạp hơn.

Hy vọng điều này sẽ hữu ích!