BFS và DFS là các phương thức di chuyển ngang được sử dụng trong tìm kiếm đồ thị. Biểu đồ truyền tải là quá trình truy cập tất cả các nút của biểu đồ. Biểu đồ là một nhóm các đỉnh 'V' và Edges 'E' kết nối với các đỉnh.
Biểu đồ so sánh
| Cơ sở để so sánh | BFS | DFS |
|---|---|---|
| Căn bản | Thuật toán dựa trên Vertex | Thuật toán dựa trên cạnh |
| Cấu trúc dữ liệu được sử dụng để lưu trữ các nút | Xếp hàng | Cây rơm |
| Tiêu thụ bộ nhớ | Không hiệu quả | Hiệu quả |
| Cấu trúc của cây được xây dựng | Rộng và ngắn | Hẹp và dài |
| Thời trang đi qua | Các đỉnh không mong muốn cũ nhất được khám phá lúc đầu. | Các đỉnh dọc theo cạnh được khám phá ngay từ đầu. |
| Tối ưu | Tối ưu cho việc tìm khoảng cách ngắn nhất, không phải chi phí. | Không tối ưu |
| Ứng dụng | Kiểm tra biểu đồ lưỡng cực, thành phần được kết nối và đường dẫn ngắn nhất có trong biểu đồ. | Kiểm tra đồ thị được kết nối hai cạnh, đồ thị được kết nối mạnh, đồ thị theo chu kỳ và thứ tự tôpô. |
Định nghĩa của BFS
Breadth First Search (BFS) là phương pháp di chuyển ngang được sử dụng trong biểu đồ. Nó sử dụng một hàng đợi để lưu trữ các đỉnh đã truy cập. Trong phương pháp này, phần nhấn mạnh nằm trên các đỉnh của đồ thị, một đỉnh được chọn lúc đầu sau đó được truy cập và đánh dấu. Các đỉnh liền kề với đỉnh được truy cập sau đó được truy cập và lưu trữ trong hàng đợi một cách tuần tự. Tương tự, các đỉnh được lưu trữ sau đó được xử lý từng cái một và các đỉnh liền kề của chúng được truy cập. Một nút được khám phá đầy đủ trước khi truy cập bất kỳ nút nào khác trong biểu đồ, nói cách khác, nó đi qua các nút chưa được khám phá nông nhất trước tiên.
Thí dụ
Chúng ta có một đồ thị có các đỉnh là A, B, C, D, E, F, G. Coi A là điểm bắt đầu. Các bước liên quan đến quy trình là:
- Vertex A được mở rộng và lưu trữ trong hàng đợi.
- Các kế tiếp B, D và G của A, được mở rộng và lưu trữ trong hàng đợi trong khi Vertex A bị xóa.
- Bây giờ B ở đầu trước của hàng đợi được loại bỏ cùng với việc lưu trữ các đỉnh kế tiếp E và F.
- Vertex D ở đầu trước của hàng đợi được loại bỏ và nút F được kết nối của nó đã được truy cập.
- Vertex G bị xóa khỏi hàng đợi và nó có E kế tiếp đã được truy cập.
- Bây giờ E và F được xóa khỏi hàng đợi và đỉnh C kế tiếp của nó được duyệt và lưu trong hàng đợi.
- Cuối cùng C cũng bị loại bỏ và hàng đợi trống có nghĩa là chúng ta đã hoàn thành.
- Đầu ra được tạo là - A, B, D, G, E, F, C.
BFS có thể hữu ích trong việc tìm kiếm xem biểu đồ có kết nối các thành phần hay không. Và nó cũng có thể được sử dụng trong việc phát hiện đồ thị lưỡng cực .
Một đồ thị là lưỡng cực khi các đỉnh đồ thị được chia thành hai bộ khác nhau; không có hai đỉnh liền kề sẽ nằm trong cùng một tập hợp. Một phương pháp khác để kiểm tra đồ thị lưỡng cực là kiểm tra sự xuất hiện của một chu kỳ lẻ trong biểu đồ. Một đồ thị lưỡng cực không được chứa chu kỳ lẻ.
BFS cũng tốt hơn trong việc tìm ra con đường ngắn nhất trong biểu đồ có thể được xem như một mạng.
Định nghĩa của DFS
Phương pháp di chuyển ngang tìm kiếm sâu (DFS) sử dụng ngăn xếp để lưu trữ các đỉnh đã truy cập. DFS là phương pháp dựa trên cạnh và hoạt động theo kiểu đệ quy trong đó các đỉnh được khám phá dọc theo một đường dẫn (cạnh). Việc thăm dò một nút bị đình chỉ ngay khi tìm thấy một nút chưa được khám phá khác và các nút chưa được khám phá sâu nhất được duyệt qua trước hết. DFS di chuyển / truy cập mỗi đỉnh chính xác một lần và mỗi cạnh được kiểm tra chính xác hai lần.
Thí dụ
Tương tự như BFS, hãy lấy cùng một biểu đồ để thực hiện các hoạt động DFS và các bước liên quan là:
- Coi A là đỉnh bắt đầu được khám phá và lưu trữ trong ngăn xếp.
- B đỉnh kế tiếp của A được lưu trữ trong ngăn xếp.
- Vertex B có hai người kế vị E và F, trong số đó, bảng chữ cái E được khám phá đầu tiên và được lưu trữ trong ngăn xếp.
- Sự kế thừa của đỉnh E, tức là G được lưu trữ trong ngăn xếp.
- Vertex G có hai đỉnh được kết nối và cả hai đều đã được truy cập, do đó G được bật ra khỏi ngăn xếp.
- Tương tự, E s cũng bị loại bỏ.
- Bây giờ, đỉnh B nằm ở đầu ngăn xếp, một nút khác (đỉnh) F được khám phá và lưu trữ trong ngăn xếp.
- Vertex F có hai người kế nhiệm C và D, giữa họ C được duyệt trước và được lưu trữ trong ngăn xếp.
- Vertex C chỉ có một người tiền nhiệm đã được truy cập, do đó, nó bị xóa khỏi ngăn xếp.
- Bây giờ đỉnh D được kết nối với F được truy cập và lưu trữ trong ngăn xếp.
- Vì đỉnh D không có bất kỳ nút không mong muốn nào, do đó D bị loại bỏ.
- Tương tự, F, B và A cũng được bật lên.
- Đầu ra được tạo là - A, B, E, G, F, C, D.
Các ứng dụng của DFS bao gồm kiểm tra hai đồ thị được kết nối cạnh, đồ thị được kết nối mạnh, đồ thị theo chu kỳ và thứ tự tôpô .
Một biểu đồ được gọi là hai cạnh được kết nối khi và chỉ khi nó vẫn được kết nối ngay cả khi một trong các cạnh của nó bị xóa. Ứng dụng này rất hữu ích, trong các mạng máy tính mà sự thất bại của một liên kết trong mạng sẽ không ảnh hưởng đến mạng còn lại và nó vẫn sẽ được kết nối.
Biểu đồ được kết nối mạnh là một biểu đồ trong đó phải tồn tại một đường dẫn giữa các cặp đỉnh được sắp xếp. DFS được sử dụng trong biểu đồ có hướng để tìm kiếm đường dẫn giữa mỗi cặp đỉnh được sắp xếp. DFS có thể dễ dàng giải quyết các vấn đề kết nối.
Sự khác biệt chính giữa BFS và DFS
- BFS là thuật toán dựa trên đỉnh trong khi DFS là thuật toán dựa trên cạnh.
- Cấu trúc dữ liệu hàng đợi được sử dụng trong BFS. Mặt khác, DFS sử dụng stack hoặc đệ quy.
- Không gian bộ nhớ được sử dụng hiệu quả trong DFS trong khi sử dụng không gian trong BFS không hiệu quả.
- BFS là thuật toán tối ưu trong khi DFS không tối ưu.
- DFS xây dựng cây hẹp và dài. Như chống lại, BFS xây dựng cây rộng và ngắn.
Phần kết luận
BFS và DFS, cả hai kỹ thuật tìm kiếm đồ thị có thời gian chạy tương tự nhưng tiêu thụ không gian khác nhau, DFS chiếm không gian tuyến tính vì chúng ta phải nhớ đường dẫn đơn với các nút chưa được khám phá, trong khi BFS giữ mọi nút trong bộ nhớ.
DFS mang lại giải pháp sâu hơn và không tối ưu, nhưng nó hoạt động tốt khi giải pháp dày đặc trong khi BFS là tối ưu để tìm kiếm mục tiêu tối ưu lúc đầu.
