Breadth-First Search: Difference between revisions

Jump to navigation Jump to search

Breadth-First Search (edit)

Revision as of 03:57, 6 May 2023

313 bytes removed ,  6 May 2023
no edit summary
No edit summary
Line 1: Line 1:
= Breadth-First Search (BFS) =
== Breadth-First Search ==


Breadth-First Search (BFS) is an algorithm for searching a tree or graph data structure for a node that meets a set of criteria. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. <ref name=“geeksforgeeks”>https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/</ref>
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward (layer-by-layer) motion. BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph.


== How it works ==
== Algorithm ==


BFS uses a queue data structure to keep track of the nodes to be visited. It also uses an array or a set to mark the nodes that have been visited, to avoid revisiting them.
    Start at the source node and mark it as visited.
    Enqueue the source node into a queue.
    While the queue is not empty:
    a. Dequeue the front node from the queue.
    b. Process the dequeued node (e.g., print its value).
    c. For each adjacent node of the dequeued node, if it is not visited, mark it as visited and enqueue it.


The algorithm works as follows:
Choose a starting node, mark it as visited, and add it to the queue.
While the queue is not empty:
Dequeue a node from the queue and process it (e.g., print its value).
Enqueue all its adjacent nodes that have not been visited and mark them as visited.
Repeat step 2 until the queue is empty.
== Complexity ==
== Complexity ==


Retrieved from "https://wiki.usaco.fun/index.php/Special:MobileDiff/471"

Navigation menu