This is the Basics of Graph Theory
Breadth First Search A searching algorithm
The searching of a tree data structure, which identifies a node (vertex) with a given property.
What you need to know Basic Definitions
Graph Traversal
Graph traversal means visiting every vertex and edge exactly once in a well-defined order. While using certain graph algorithms, you must ensure that each vertex of the graph is visited exactly once.
Breadth First Search
BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layer wise thus exploring the neighbour nodes. You must then move towards the next-level neighbour nodes.
Simple Explanation How Does It Work?
As the name BFS suggests, you are required to traverse the graph breadthwise as follows:
First move horizontally and visit all the nodes of the current layer.
Then move to the next layer.
The distance between the nodes in layer 1 is comparitively lesser than the distance between the nodes in layer 2. Therefore, in BFS, you must traverse all the nodes in layer 1 before you move to the nodes in layer 2.
Why Do I Need This? It's used in applications
Solving Rubik's Cube
Breadth-first search can be used to solve games where a series of choices result in either a winning or losing state. For example, BFS can help a player determine a winning sequence of moves for solving a Rubik’s cube.
Finding Shortest Routes
BFS runs on maps and determines what the shortest routes between the cities are and produces the another map, which shows the best paths from city to city.
Computation
BFS is also used in the famous Dijkstra’s algorithm for computing the shortest path in a graph and the Ford-Fulkerson algorithm for computing the maximum flow in a flow network.
Shown Step By Step Seeing it in Action
