Sự Khác Biệt Giữa BFS Và DFS

• 2019

Sự khác biệt chính giữa BFS và DFS là BFS tiến hành theo cấp độ trong khi DFS theo sau một đường dẫn từ nút bắt đầu đến nút kết thúc (đỉnh), sau đó là một đường dẫn khác từ đầu đến cuối, và cho đến khi tất cả các nút được truy cập. Hơn nữa, BFS sử dụng hàng đợi để lưu trữ các nút trong khi DFS sử dụng ngăn xếp để duyệt qua các nút.

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.

Các ứng dụng-

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.

Ứng dụng-

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

1. 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.
2. 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.
3. 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ả.
4. BFS là thuật toán tối ưu trong khi DFS không tối ưu.
5. 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.