Breadth First Traversal and Depth First Traversal in Data Structure

What is Breadth First Traversal in Data Structures?

Breadth-first Search (BFS) is a graph traversal technique that traverses all vertices of a graph in breadthwise order. It indicates that it begins at a specific vertex or node and visits all vertices at the same level before progressing to the next level. It is a recursive method that searches all of the vertices in a graph or tree data structure.

BFS Algorithm

• Choose a beginning vertex or node.
• Move the beginning vertex to the end of the queue.
• Mark the beginning vertex as visited and include it in the visited array/list.
• While the queue is not empty, remove the front vertex.
• Visit and process the removed vertex.
• Enqueue all nearby vertices to the removed vertex that has not yet been visited.
• Each visited adjacent vertex should be marked as visited and added to the visited array/list.
• Repeat steps 4 until the queue is empty.

Rules for Breadth-First Traversal Algorithm

• BFS use a FIFO queue for traversal.
• BFS can start at any vertex in the graph.
• It visits every node in the graph.
• Each visited node's unvisited neighbours are added to the queue.
• BFS continues until every vertex has been visited.
• Mark visited nodes to prevent looping.

Applications of Breadth First Search Algorithm

• Minimum spanning tree: BFS determines the shortest path that connects all vertices.
• Peer-to-peer networking: BFS finds neighboring peers quickly.
• Search engine crawlers: BFS navigates online pages by following links.
• GPS navigation: BFS locates nearby locations within a specified radius.
• Broadcasting: BFS broadcasts information to neighboring peers.
• Pathfinding: BFS determines whether there is a path between two vertices.
• Finding reachable nodes: BFS locates all reachable vertices in a graph.

What is Depth First Traversal in Data Structures?

Depth-first search begins with a starting node, travels as far as feasible along each branch before returning, then repeats the procedure for unvisited nodes. This recursive algorithm iteratively traverses all vertices in a graph or tree.

DFS Algorithm

• Begin by picking a beginning vertex or node.
• Place the beginning vertex on top of a stack.
• Take the top item from the stack and add it to the visited list or array.
• Make a list of the vertex's nearby nodes.
• Add those that aren't on the visited list to the top of the stack.
• Repeat steps 3 and 4 until the stack is empty.

Applications of Depth First Search Algorithm

• Finding Paths: Look for any path in the network that connects two vertices, u and v.
• Connected Components: Find the number of connected components in an undirected graph.
• Topological Sorting: Sort a directed graph by topology.
• Strongly Connected Components: Locate strongly connected components in a directed graph.
• Cycle Detection: Identify cycles in the given graph.
• Bipartite Graphs: Determine whether the provided graph is bipartite.

Complexity Analysis of BFS and DFS Algorithms