Graph Step 5 - Delete node C from queue1 and add it into queue2.

Insert
A graph can be defined as group of vertices and edges that all neighbors of node C to queue1.
are used to connect these vertices. A graph can be seen as a QUEUE1 = {F, E, G}
cyclic tree, where the vertices (Nodes) maintain any complex QUEUE2 = {A, B, D, C}
relationship among them instead of having parent child Step 5 - Delete node F from queue1 and add it into queue2. Insert
relationship. all neighbors of node F to queue1. Since all the neighbors of
A graph G can be defined as an ordered set G(V, E) where V(G) node F are already present, we will not insert them again.
represents the set of vertices and E(G) represents the set of QUEUE1 = {E, G}
edges which are used to connect these vertices. QUEUE2 = {A, B, D, C, F}
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges Step 6 - Delete node E from queue1. Since all of its neighbors
((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the following have already been added, so we will not insert them again.
figure. Now, all the nodes are visited, and the target node E is
encountered into queue2.
QUEUE1 = {G}
QUEUE2 = {A, B, D, C, F, E}
DFS (Depth First Search) algorithm
In this article, we will discuss the DFS algorithm in the data
structure. It is a recursive algorithm to search all the vertices
of a tree data structure or a graph. The depth-first search
Directed and Undirected Graph (DFS) algorithm starts with the initial node of graph G and
A graph can be directed or undirected. However, in an goes deeper until we find the goal node or the node with no
undirected graph, edges are not associated with the children.
directions with them. An undirected graph is shown in the Because of the recursive nature, stack data structure can be used to
above figure since its edges are not attached with any of the implement the DFS algorithm. The process of implementing
directions. If an edge exists between vertex A and B then the the DFS is similar to the BFS algorithm.
vertices can be traversed from B to A as well as A to B. The step by step process to implement the DFS traversal is
In a directed graph, edges form an ordered pair. Edges given as follows -
represent a specific path from some vertex A to another 1) First, create a stack with the total number of vertices in the
vertex B. Node A is called initial node while node B is called graph.
terminal node. 2) Now, choose any vertex as the starting point of traversal, and
Graph Terminology push that vertex into the stack.
Path 3) After that, push a non-visited vertex (adjacent to the vertex on
A path can be defined as the sequence of nodes that are the top of the stack) to the top of the stack.
followed in order to reach some terminal node V from the 4) Now, repeat steps 3 and 4 until no vertices are left to visit
initial node U. from the vertex on the stack's top.
Closed Path 5) If no vertex is left, go back and pop a vertex from the stack.
A path will be called as closed path if the initial node is same 6) Repeat steps 2, 3, and 4 until the stack is empty.
as terminal node. A path will be closed path if V0=VN. Applications of DFS algorithm
Simple Path 1) The applications of using the DFS algorithm are given as
If all the nodes of the graph are distinct with an exception follows -
V0=VN, then such path P is called as closed simple path. 2) DFS algorithm can be used to implement the topological
Cycle sorting.
A cycle can be defined as the path which has no repeated 3) It can be used to find the paths between two vertices.
edges or vertices except the first and last vertices. 4) It can also be used to detect cycles in the graph.
Connected Graph 5) DFS algorithm is also used for one solution puzzles.
A connected graph is the one in which some path exists 6) DFS is used to determine if a graph is bipartite or not.
between every two vertices (u, v) in V. There are no isolated Algorithm
nodes in connected graph. Step 1: SET STATUS = 1 (ready state) for each node in G
Complete Graph Step 2: Push the starting node A on the stack and set its STATUS
A complete graph is the one in which every node is connected = 2 (waiting state)
with all other nodes. A complete graph contain n(n-1)/2 edges Step 3: Repeat Steps 4 and 5 until STACK is empty
where n is the number of nodes in the graph. Step 4: Pop the top node N. Process it and set its STATUS = 3
Weighted Graph (processed state)
In a weighted graph, each edge is assigned with some data Step 5: Push on the stack all the neighbors of N that are in the
such as length or weight. The weight of an edge e can be ready state (whose STATUS = 1) and set their STATUS = 2
given as w(e) which must be a positive (+) value indicating the (waiting state)
cost of traversing the edge. [END OF LOOP]
Digraph Step 6: EXIT
A digraph is a directed graph in which each edge of the graph Example of DFS algorithm
is associated with some direction and the traversing can be Now, let's understand the working of the DFS algorithm by using
done only in the specified direction. an example. In the example given below, there is a directed
Loop graph having 7 vertices.
An edge that is associated with the similar end points can be
called as Loop.
BFS algorithm
In this article, we will discuss the BFS algorithm in the data
structure. Breadth-first search is a graph traversal algorithm
that starts traversing the graph from the root node and
explores all the neighboring nodes. Then, it selects the
nearest node and explores all the unexplored nodes. While
using BFS for traversal, any node in the graph can be Now, let's start examining the graph starting from Node H.
considered as the root node. Step 1 - First, push H onto the stack.
Algorithm STACK: H
Step 1: SET STATUS = 1 (ready state) for each node in G Step 2 - POP the top element from the stack, i.e., H, and print
Step 2: Enqueue the starting node A and set its STATUS = 2 it. Now, PUSH all the neighbors of H onto the stack that are in
(waiting state) ready state.
Step 3: Repeat Steps 4 and 5 until QUEUE is empty Print: H]
Step 4: Dequeue a node N. Process it and set its STATUS = 3 STACK: A
(processed state). Step 3 - POP the top element from the stack, i.e., A, and print
Step 5: Enqueue all the neighbours of N that are in the ready it. Now, PUSH all the neighbors of A onto the stack that are in
state (whose STATUS = 1) and set their STATUS = 2 [END OF ready state.
LOOP] Print: A
Step 6: EXIT STACK: B, D
Example of BFS algorithm Step 4 - POP the top element from the stack, i.e., D, and print
Now, let's understand the working of BFS algorithm by using it. Now, PUSH all the neighbors of D onto the stack that are in
an example. In the example given below, there is a directed ready state.
graph having 7 vertices. Print: D
STACK: B, F
Step 5 - POP the top element from the stack, i.e., F, and print
it. Now, PUSH all the neighbors of F onto the stack that are in
ready state.
Print: F
Now, let's start examining the graph starting from Node A. STACK: B
Step 1 - First, add A to queue1 and NULL to queue2. Step 6 - POP the top element from the stack, i.e., B, and print
QUEUE1 = {A} it. Now, PUSH all the neighbors of B onto the stack that are in
QUEUE2 = {NULL} ready state.
Step 2 - Now, delete node A from queue1 and add it into queue2. Print: B
Insert all neighbors of node A to queue1. STACK: C
QUEUE1 = {B, D} Step 7 - POP the top element from the stack, i.e., C, and print
QUEUE2 = {A} it. Now, PUSH all the neighbors of C onto the stack that are in
Step 3 - Now, delete node B from queue1 and add it into queue2. ready state.
Insert all neighbors of node B to queue1. Print: C
QUEUE1 = {D, C, F} STACK: E, G
QUEUE2 = {A, B} Step 8 - POP the top element from the stack, i.e., G and PUSH
Step 4 - Now, delete node D from queue1 and add it into queue2. all the neighbors of G onto the stack that are in ready state.
Insert all neighbors of node D to queue1. The only neighbor of Print: G
Node D is F since it is already inserted, so it will not be STACK: E
inserted again. Step 9 - POP the top element from the stack, i.e., E and PUSH
QUEUE1 = {C, F} all the neighbors of E onto the stack that are in ready state.
QUEUE2 = {A, B, D} Print: E
STACK:
Now, all the graph nodes have been traversed, and the stack is
empty.