Graph Data Structure: Breadth First Search (BFS)

A graph is a pictorial representation of a set of objects where some pairs of objects are
connected by links. The interconnected objects are represented by points termed

as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set
of edges, connecting the pairs of vertices. Take a look at the following graph −
Graph Data Structure

Mathematical graphs can be represented in data structure. We can represent a graph
using an array of vertices and a two-dimensional array of edges. Before we proceed
further, let's familiarize ourselves with some important terms −
 Vertex − Each node of the graph is represented as a vertex. In the following
example, the labeled circle represents vertices. Thus, A to G are vertices. We
can represent them using an array as shown in the following image. Here A can
be identified by index 0. B can be identified using index 1 and so on.
 Edge − Edge represents a path between two vertices or a line between two
vertices. In the following example, the lines from A to B, B to C, and so on
represents edges. We can use a two-dimensional array to represent an array as
shown in the following image. Here AB can be represented as 1 at row 0,
column 1, BC as 1 at row 1, column 2 and so on, keeping other combinations as
0.
 Adjacency − Two node or vertices are adjacent if they are connected to each
other through an edge. In the following example, B is adjacent to A, C is
adjacent to B, and so on.
 Path − Path represents a sequence of edges between the two vertices. In the
following example, ABCD represents a path from A to D.
Types of Graph
Breadth First Search (BFS)
There are many ways to traverse graphs. BFS is the most commonly used approach.
BFS is a traversing algorithm where you should start traversing from a selected node (source or
starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which
are directly connected to source node). You must then move towards the next-level neighbour
nodes.
As the name BFS suggests, you are required to traverse the graph breadthwise as follows:
1. First move horizontally and visit all the nodes of the current layer
2. Move to the next layer
Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as

deep as possible down one path before backing up and trying a different one.
Depth-first search is like walking through a corn maze. You explore one path, hit a dead
end, and go back and try a different one.
Advantages:
 Depth-first search on a binary tree generally requires less memory than breadth-

first.
 Depth-first search can be easily implemented with recursion.
Disadvantages
 A DFS doesn't necessarily find the shortest path to a node, while breadth-first search
does.
Breadth First Search (BFS) Algorithm
o Step 1: SET STATUS = 1 (ready state)
for each node in G
o Step 2: Enqueue the starting node A
and set its STATUS = 2
(waiting state)
o Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
o Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
o Step 5: Enqueue all the neighbours of
N that are in the ready state
(whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
o Step 6: EXIT
Depth First Search (DFS) Algorithm

Algorithm
o Step 1: SET STATUS = 1 (ready state) for each node in G
o Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting
state)
o Step 3: Repeat Steps 4 and 5 until STACK is empty
o Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
o Step 5: Push on the stack all the neighbours of N that are in the ready state
(whose STATUS = 1) and set their
STATUS = 2 (waiting state)
[END OF LOOP]
o Step 6: EXIT
o Spanning Tree
o Spanning tree can be defined as a sub-graph of connected, undirected graph G
that is a tree produced by removing the desired number of edges from a graph.
In other words, Spanning tree is a non-cyclic sub-graph of a connected and
undirected graph G that connects all the vertices together. A graph G can have
multiple spanning trees.
o Minimum Spanning Tree

o There can be weights assigned to every edge in a weighted graph. However, A
minimum spanning tree is a spanning tree which has minimal total weight. In
other words, minimum spanning tree is the one which contains the least weight
among all other spanning tree of some particular graph.
Shortest path algorithms

In this section of the tutorial, we will discuss the algorithms to calculate the shortest
path between two nodes in a graph.
There are two algorithms which are being used for this purpose.
o Prim's Algorithm
o Kruskal's Algorithm
o next →← prev
o Prim's Algorithm
o Prim's Algorithm is used to find the minimum spanning tree from a graph. Prim's
algorithm finds the subset of edges that includes every vertex of the graph such
that the sum of the weights of the edges can be minimized.
o Prim's algorithm starts with the single node and explore all the adjacent nodes
with all the connecting edges at every step. The edges with the minimal weights
causing no cycles in the graph got selected.
Algorithm
o Step 1: Select a starting vertex
o Step 2: Repeat Steps 3 and 4 until there are fringe vertices
o Step 3: Select an edge e connecting the tree vertex and fringe vertex that has
minimum weight
o Step 4: Add the selected edge and the vertex to the minimum spanning tree T
[END OF LOOP]
o Step 5: EXIT
Kruskal's Algorithm
Kruskal's Algorithm is used to find the minimum spanning tree for a connected
weighted graph. The main target of the algorithm is to find the subset of edges
by using which, we can traverse every vertex of the graph. Kruskal's algorithm
follows greedy approach which finds an optimum solution at every stage instead
of focusing on a global optimum.
Algorithm
o Step 1: Create a forest in such a way that each graph is a separate tree.
o Step 2: Create a priority queue Q that contains all the edges of the graph.
o Step 3: Repeat Steps 4 and 5 while Q is NOT EMPTY
o Step 4: Remove an edge from Q
o Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it
to the forest (for combining two trees into one tree).
ELSE
Discard the edge
o Step 6: END
Solve the problem itself
Write the step also..
Greedy Algorithms
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always
choosing the next piece that offers the most obvious and immediate benefit. So the
problems where choosing locally optimal also leads to global solution are best fit for
Greedy.
1. Kruskal’s Minimum Spanning Tree

2. Prim’s Minimum Spanning Tree

Graph Data Structure: Breadth First Search (BFS)

Uploaded by

Copyright:

Available Formats

Graph Data Structure: Breadth First Search (BFS)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Graph Data Structure: Breadth First Search (BFS)

Uploaded by

Copyright:

Available Formats

A graph is a pictorial representation of a set of objects where some pairs of objects are

connected by links. The interconnected objects are represented by points termed

Graph Data Structure

Breadth First Search (BFS)

Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as

 Depth-first search on a binary tree generally requires less memory than breadth-

Depth First Search (DFS) Algorithm

o Step 3: Repeat Steps 4 and 5 until STACK is empty

o Minimum Spanning Tree

Shortest path algorithms

1. Kruskal’s Minimum Spanning Tree

You might also like