Breadth First Search
Now we shall put our glance at the steps involved in the BFS strategy.
Step 1: We take an empty queue.
Step 2: Then, we select a starting point or root node to start with and insert the data from the node
into the queue.
Step 3: If the queue is not empty, then we extract the node from the neighbouring nodes in breadth
wise fashion and insert its child nodes into the queue.
Step 4: Then, we can print the extracted nodes
We will now see the steps of the above BFS strategy into this example. We take a look at the graph
below. We will use the BFS strategy to traverse the graph.
We can allocate ‘a’ as the root node. Then we start searching for the goal node in the downward
direction following the steps mentioned above.
The figure illustrates the steps involved in BFS, which binds in the end to end process. The steps are
executed in the following manner.
1. We allocate node ‘a’ as a starting root node and insert it into the queue.
2. Then ‘a’ node is extracted and the child nodes of ‘a’ which are ‘b’ and ‘c’ put into the queue.
3. Then we Print ‘a’.
4. Then the first node in the queue is extracted again similarly.
5. Next, the child of ‘b’ which are ‘d’ and ‘e’ are inserted into the queue and extracted for
printing.
6. Then we recursively repeat the steps until the queue is empty.
7. We cannot repeat the steps for already visited nodes.
Introduction to Graph in Data Structure
Graphs are non-linear data structures comprising a finite set of nodes and edges. The nodes are the
elements, and edges are ordered pairs of connections between the nodes.
Real-World Example
The best example of graphs in the real world is Facebook. Each person on Facebook is a node and is
connected through edges. Thus, a is a friend of B. B is a friend of C, and so on.
Terminologies
Here are the Terminologies of Graph in Data Structure mentioned below
1. Graph Representation: Generally, a graph is represented as a pair of sets (V, E). V is the set of
vertices or nodes. E is the set of Edges. In the above example,
V = { A, B, C, D, E }
E = { AB, AC, AD, BE, CD, DE }
2. Node or Vertex: The elements of a graph are connected through edges.
3. Edges: A path or a line between two vertices in a graph.
4. Adjacent Nodes: Two nodes are called adjacent if they are connected through an edge. Node A is
adjacent to nodes B, C, and D in the above example, but not to node E.
5. Path: Path is a sequence of edges between two nodes. It is essentially a traversal starting at one
node and ending at another. Thus, in the example above, there are multiple paths from node A to node
E.
Path(A, E) = { AB, BE }
OR
Path(A, E) = { AC, CD, DE }
OR
Path(A, E) = { AD, DE }
6. Undirected Graph: An undirected graph is one where the edges do not specify a particular
direction. The edges are bi-directional.
Example
Thus, the edge AC can be traversed from both A to C and C to A in this example. Similar to all the
edges. A path from node B to node C would be either { BA, AC } or { BD, DC }.
7. Directed Graph: A directed graph is one where the edges can be traversed in a specified direction
only.
Example
Thus, in the same example, now the edges are directional. You can only traverse the edge along its
direction. There is no path from node B to node C now.
8. Weighted Graph: A weighted graph is one where the edges are associated with a weight. This is
generally the cost to traverse the edge.
Example
Thus, in the same example, now the edges have a certain weight associated with them. There are two
possible paths between node A to node E.
Path1 = { AB, BD, DE }, Weight1 = 3+2+5 = 10
Path2 = { AC, CD, DE }, Weight2 = 1+3+5 = 9
Clearly, one would prefer Path2 if the goal is to reach node E from node A with minimum cost.
3. Breadth-First Search (BFS)
This is a traversal operation in the graph. BFS horizontally traverses the graph. This means that it
traverses all the nodes at a single level before proceeding to the next level.
The BFS algorithm starts at the top of the first node in the graph and then traverses all the adjacent
nodes to it. Once all the adjacent nodes are traversed, the algorithm repeats the same procedure for
child nodes.
Example
Traversing the above graph in BFS fashion would result from A -> B -> C -> D -> E -> F -> G. The
algorithm starts from node A and traverses all its adjacent nodes B, C and D. It marks all the four
nodes as visited. Once all the adjacent nodes of A are traversed, the algorithm moves to the first
adjacent node of A and repeats the same procedure. In this case, the node is B, and the adjacent nodes
to B are E and F. Next, the adjacent nodes to C are traversed. Once all the nodes are visited, the
operation ends.
4. Depth First Search (DFS)
Depth First Search or DFS traverses the graph vertically. It starts with the root node or the first node
of the graph and traverses all the child nodes before moving to the adjacent nodes.
Example
Traversing the above graph in BFS fashion would result from A -> B -> E -> F -> C -> G -> D. The
algorithm starts from node A and traverses all its child nodes. As soon as it encounters B, it seems
that it has further child nodes. So, the child nodes of B are traversed before proceeding to the next
child node of A.
Real-World Implementations of Graphs
Design of electrical circuits for power transmission.
Design of network of interconnected computers.
Study of the molecular, chemical and cellular structure of any substance, e.g. Human DNA.
Design of transport routes between cities and places within a city.
Graph Traverse in DFS
In DFS, the below steps are followed to traverse the graph. For example, a given graph, let us start
traversal from 1:
Stack Traversal Spanning
Sequence Tree
1,4
1,4,3
1,4,3,10
1,4,3,10,9
1,4,3,10,9,2
1,4,3,10,9,2,8
1,4,3,10,9,2,8,7
1,4,3,10,9,2,8,7,5
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
1,4,3,10,9,2,8,7,5,6
Explanation to DFS Algorithm
Below are the steps to DFS Algorithm with advantages and disadvantages:
Step1: Node 1 is visited and added to the sequence as well as the spanning tree.
Step2: Adjacent nodes of 1 are explored that is 4 thus 1 is pushed to stack and 4 is pushed into the
sequence as well as spanning tree.
Step3: One of the adjacent nodes of 4 is explored and thus 4 is pushed to the stack, and 3 enters the
sequence and spanning tree.
Step4: Adjacent nodes of 3 are explored by pushing it onto the stack and 10 enters the sequence. As
there is no adjacent node to 10, thus 3 is popped out of the stack.
Step5: Another adjacent node of 3 is explored and 3 is pushed onto the stack and 9 is visited. No
adjacent node of 9 thus 3 is popped out and the last adjacent node of 3 i.e 2 is visited.
A similar process is followed for all the nodes till the stack becomes empty which indicates the stop
condition for the traversal algorithm. — -> dotted lines in the spanning tree refers to the back edges
present in the graph.
In this way, all the nodes in the graph are traverse without repeating any of the nodes.
Advantages and Disadvantages
Advantages: The memory requirements for this algorithm is very less. Lesser space and time
complexity than BFS.
Disadvantages: Solution is not guaranteed Applications. Topological Sorting. Finding
Bridges of the graph.
Graph Representation
One can represent a graph in several ways. We have to traverse the graph in computer science using
mathematical notations to represent data in the network or other applications. There are two most
generic ways of representing a graph in computer science, and we will discuss them as:
1. Adjacency Matrix
We can define an adjacency matrix as a binary matrix A of V*V elements. The element A x,y is 1 if
there exists an edge among vertex i and j or else it is 0. We know that a binary matrix is the one that is
either 0 or 1 as its values. In case of an undirected graph we if Ax,y = 1, then Ay,x = 1. In a directed
graph, if Ax,y = 1, then Ay,x may or may not be 1. Adjacency matrix gives us constant time and all-
time access to running time (O(1) ) that helps to find out if any edge exists between two given nodes.
The space complexity is given by O(V2).
Example: The adjacency matrix of the following undirected graph is:
Ax,y=
The adjacency matrix of the following directed graph is given by:
Ax,y=
2. Adjacency List
We can define an adjacency list as an array A composed of separate lists. The array elements
represented as Axis a list containing all vertices adjacent to vertex x. In a weighted graph, the edge’s
cost is also stored along with the information related to the vertex in the list using the pairs of edges
and vertices. In an undirected graph, if vertex y is in list Ax, then vertex x will be in list Ay, and the
space complexity is O(V + E).
E.g. of an undirected graph and the adjacency list of the graph is expressed as follows:
E.g. of a directed graph and the adjacency list of the graph is expressed as follows:
