Graph :
Representations of graph :
There are two ways graphs can be represented. They are
i) Adjacency matrix representation
ii) Adjacency list representation
The adjacency matrix is a n x n Boolean matrix consisting of 0’s and 1’s. The
entry 1 indicates the presence of an edge between corresponding pair of
vertices and the entry 0 indicates no edge.
For example :
Adjacency list representation:
In adjacency list representation of a graph, every vertex is represented
as a node object. The node may either contain data or a reference to a
linked list. This linked list provides a list of all nodes that are adjacent to
the current node.
For example :
Graph Traversal Techniques
What is traversal of a graph?
Traversal means visiting the nodes of a graph systematically one after the
other.
There are two methods of traversal. They are:
i) Depth First Search (DFS) ii) Breadth First Search (BFS)
Depth First search algorithm:
The DFS and BFS algorithms have proved to be very useful in investigating
several important properties of a graph.
Working of DFS Algorithm:
DFS uses stack data structure to keep track of the operations.
Select the start vertex, by marking it as having been visited.
On each iteration, the algorithm proceeds to an unvisited vertex that is
adjacent to the one it is currently in.
This process continues until a dead end is encountered. Dead end is a vertex
with no adjacent unvisited vertices.
Push vertex on to the stack when the vertex is reached for the first time.
Pop a vertex off the stack when it becomes dead end.
It is also very useful to accompany a DFS traversal by constructing the so-
called depth first search forest.
There are two types of edges, we encounter here. They are: i) Tree edge ii)
Back edge
Tree edge: Whenever a new unvisited vertex is reached for the first time, it is
attached as a child to the vertex from which it is being reached. Such an edge
is called tree edge.
Back edge: The DFS algorithm may also encounter an edge leading to
previously visited vertex. Such an edge is called back edge. ( Presence of
Back edge indicates the loop)
Examples : Apply DFS algorithm to for the following graphs
1)
2)
3)
4)
5)
Applications of DFS are :
• To find the spanning tree of a graph
• To check connectivity
• To check acyclicity of a graph
• To find Topological sorted order
Breadth First Search :
BFS proceeds by visiting first all the vertices that are adjacent to a starting
vertex, then all unvisited vertices two edges apart from it, and so on, until all
the vertices in the same connected component from the starting vertex are
visited.
Queue data structure is used to keep track of BFS operation.
Similar to a DFS traversal, it is useful to accompany a BFS traversal by
constructing the so called BFS Forest.
Here we encounter two edges: i) Tree edge ii) Cross edge
Working:
Queue is initialized with the starting vertex, which is marked as visited.
On each iteration, the algorithm identifies all unvisited vertices that are
adjacent to the front vertex, and marks them as visited.
Adds them to the queue, after that the front vertex is removed from the queue.
Applications of BFS
To check connectivity of the graph.
To check whether the graph is acyclic or not.
To find the spanning tree of a graph
To find the path with fewest number of edges.
Examples :