Breadth First Search Archives

Shortest Path in an Unweighted Graph Using BFS

by admin

Shortest path algorithms are designed to find the minimum cost path between two nodes in a graph.
For example, a shortest path algorithm can be used to find the fastest route between two places or the minimum number of connections required to reach one point from another.
An unweighted graph is a graph in which all the edges are of same cost. Therefore, the shortest path is simply the path with the minimum number of edges.
The easiest way to find the shortest path in an unweighted graph is by using BFS (Breadth First Search).
Before going ahead, you can have a look at Graph Basics if you are not familiar with graph representation..

(more…)

Binary Tree Level Order Traversal Explained With Simple Example

by admin

A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics and Binary Tree implementation.

(more…)

Breadth first search for a Graph

by admin

Traversal of a Graph means visiting each and every nodes present in the Graph. Traversal can be done using various approaches and here we are going to talk about one of most famous and useful traversal algorithm known as Breadth first search (BFS). In this algorithm, backtracking and recursion is being used along with a Queue to visit all the nodes. Before going ahead have a look into Graph Basics.

(more…)