Directed Graph - BFS | Breadth First Search Graph Traversal Algorithm Demo

In BFS traversal, we traverse breadth-first instead of going in-depth further.
In BFS, we explore the source node and then it's all adjacent child nodes before moving further. This requires us to maintain Queue for keeping the next node to traverse because it is iterative implementation instead of recursive like in DFS.
In Data structures and algorithms and graph theory, a directed graph is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

A directed graph is an ordered pair G = (V, A) where[1]

V is a set whose elements are called vertices, nodes, or points.
A is a set of ordered pairs of vertices, called arrows, directed edges, directed arcs, or directed lines.
It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges, arcs, or lines.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures and algorithms. It starts at the tree root and explores the neighbour nodes first, before moving to the next level neighbours.

Breadth-first search can be used to solve many problems in graph theory, for example:

Copying garbage collection, Cheney's algorithm
Finding the shortest path between two nodes u and v, with path length measured by the number of edges (an advantage over depth-first search)[10]
(Reverse) Cuthill–McKee mesh numbering
Ford–Fulkerson method for computing the maximum flow in a flow network
Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
Construction of the failure function of the Aho-Corasick pattern matcher.
Testing bipartiteness of a graph.

#BFS #Graph #DFS #Algorithm #Programming #DataStructure #Java