Graph

A graph can be defined as group of vertices and edges that are used to connect these vertices.
A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any complex
relationship among them instead of having parent child relationship.
Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices
and E(G) represents the set of edges which are used to connect these vertices.
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E), (E,D),
(D,B), (D,A)) is shown in the following figure.

Directed and Undirected Graph

A graph can be directed or undirected. However, in an undirected graph, edges are not
associated with the directions with them. An undirected graph is shown in the above figure
since its edges are not attached with any of the directions. If an edge exists between vertex A
and B then the vertices can be traversed from B to A as well as A to B.
 In a directed graph, edges form an ordered pair. Edges represent a specific path from some
vertex A to another vertex B. Node A is called initial node while node B is called terminal
node.
A directed graph is shown in the following figure.

Graph Traversal
Graph traversal is a technique used for searching a vertex in a graph. The graph traversal is
also used to decide the order of vertices is visited in the search process. A graph traversal
finds the edges to be used in the search process without creating loops. That means using
graph traversal we visit all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...

1. DFS (Depth First Search)

2. BFS (Breadth First Search)

BFS (Breadth First Search)

This is a very different approach for traversing the graph nodes. The aim of BFS algorithm is
to traverse the graph as close as possible to the root node. Queue is used in the
implementation of the breadth first search.
We use the following steps to implement BFS traversal...

 Step 1 - Define a Queue of size total number of vertices in the graph.

 Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.
 Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue
and insert them into the Queue.
 Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.
 Step 5 - Repeat steps 3 and 4 until queue becomes empty.
 Step 6 - When queue becomes empty, then produce final spanning tree by removing unused
edges from the graph
Example

Step Traversal Description

1 Initialize the queue.

We start from visiting S (starting node),

2
and mark it as visited.

We then see an unvisited adjacent node

from S. In this example, we have three
3
nodes but alphabetically we choose A,
mark it as visited and enqueue it.

Next, the unvisited adjacent node

4 from S is B. We mark it as visited and
enqueue it.
 Next, the unvisited adjacent node
5 from S is C. We mark it as visited and
enqueue it.

Now, S is left with no unvisited adjacent

6
nodes. So, we dequeue and find A.

From A we have D as unvisited adjacent

7 node. We mark it as visited and enqueue
it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the
program is over.
Depth First Search Algorithm
A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the
top of the stack.
4. Keep repeating steps 2 and 3 until the stack is
empty. Depth First Search Example
Let's see how the Depth First Search algorithm works with an example. We use an undirected
graph with 5 vertices.

Undirected graph with 5 vertices

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting
all its adjacent vertices in the stack.

Visit the element and put it in the visited list

Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has
already been visited, we visit 2 instead.

Visit the element at the top of stack

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit
it.
Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit
it.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit
it.
After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have
completed the Depth First Traversal of the graph.

What is a Minimum Spanning Tree?

 The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can
be many spanning trees. Minimum spanning tree is the spanning tree where the cost is
minimum among all the spanning trees. There also can be many minimum spanning trees.
Minimum spanning tree has direct application in the design of networks. It is used in
algorithms approximating the travelling salesman problem, multi-terminal minimum cut
problem and minimum-cost weighted perfect matching. Other practical applications are:

1. Cluster Analysis
2. Handwriting recognition
3. Image segmentation

There are two famous algorithms for finding the Minimum Spanning
Tree: Kruskal’s Algorithm
Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing
spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an
edge which has least weight and add it to the growing spanning tree.
Algorithm Steps:

 Sort the graph edges with respect to their weights.

 Start adding edges to the MST from the edge with the smallest weight until the edge of the
largest weight.
 Only add edges which doesn't form a cycle , edges which connect only disconnected
components.

Consider following example:

In Kruskal’s algorithm, at each iteration we will select the edge with the lowest weight. So,
we will start with the lowest weighted edge first i.e., the edges with weight 1. After that we
will select the second lowest weighted edge i.e., edge with weight 2. Notice these two edges
are totally disjoint. Now, the next edge will be the third lowest weighted edge i.e., edge with
weight 3, which connects the two disjoint pieces of the graph. Now, we are not allowed to
pick the edge with weight 4, that will create a cycle and we can’t have any cycles. So we will
select the fifth lowest weighted edge i.e., edge with weight 5. Now the other two edges will
create cycles so we will ignore them. In the end, we end up with a minimum spanning tree
with total cost 11 ( = 1 + 2 + 3 + 5).
Prim’s Algorithm
 Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s
Algorithm we grow the spanning tree from a starting position. Unlike an edge in Kruskal's,
we add vertex to the growing spanning tree in Prim's.
Algorithm Steps:

 Maintain two disjoint sets of vertices. One containing vertices that are in the growing
spanning tree and other that are not in the growing spanning tree.
 Select the cheapest vertex that is connected to the growing spanning tree and is not in the
growing spanning tree and add it into the growing spanning tree. This can be done using
Priority Queues. Insert the vertices, that are connected to growing spanning tree, into the
Priority Queue.
 Check for cycles. To do that, mark the nodes which have been already selected and insert
only those nodes in the Priority Queue that are not marked.

Consider the example below:

In Prim’s Algorithm, we will start with an arbitrary node (it doesn’t matter which one) and
mark it. In each iteration we will mark a new vertex that is adjacent to the one that we have
already marked. As a greedy algorithm, Prim’s algorithm will select the cheapest edge and
mark the vertex. So we will simply choose the edge with weight 1. In the next iteration we
have three options, edges with weight 2, 3 and 4. So, we will select the edge with weight 2
and mark the vertex. Now again we have three options, edges with weight 3, 4 and 5. But we
can’t choose edge with weight 3 as it is creating a cycle. So we will select the edge with
weight 4 and we end up with the minimum spanning tree of total cost 7 ( = 1 + 2 +4).
Floyd-Warshall Algorithm
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs
of vertices in a weighted graph. This algorithm works for both the directed and undirected
weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of
the edges in a cycle is negative).
A weighted graph is a graph in which each edge has a numerical value associated with it.
 Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd algorithm, Roy-
Warshall algorithm, or WFI algorithm.
This algorithm follows the dynamic programming approach to find the shortest paths.
Let the given graph be:

Initial graph
Follow the steps below to find the shortest path between all the pairs of vertices.

1. Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the
column are indexed as i and j respectively. i and j are the vertices of the graph. Each
cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path
from ith vertex to jth vertex, the cell is left as infinity.
Fill each cell with the distance between ith and jth vertex
2. Now, create a matrix A1 using matrix A0. The elements in the first column and the first
row are left as they are. The remaining cells are filled in the following way. Let k be the
intermediate vertex in the shortest path from source to destination. In this step, k is the first
vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).
That is, if the direct distance from the source to the destination is greater than the path
through the vertex k, then the cell is filled with A[i][k] + A[k][j]. In this step, k is vertex 1.
We calculate the distance from source vertex to destination vertex through this vertex k.
Calculate the distance from the source vertex to destination vertex through this vertex k
For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the
distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7.
Since 4 < 7, A0[2, 4] is filled with 4.
3. Similarly, A2 is created using A1. The elements in the second column and the second row
are left as they are. In this step, k is the second vertex (i.e. vertex 2). The remaining steps are
the same as in step 2.

Calculate the distance from the source vertex to destination vertex through this vertex 2
4. Similarly, A3 and A4 is also created.
Calculate the distance from the source vertex to destination
vertex through this vertex 3 Calculate the distance from the
source vertex to destination vertex through this vertex 4
5. A4 gives the shortest path between each pair of vertices.

Dijkstra Algorithm
Dijkstra’s algorithm is also known as the shortest path algorithm.
It is an algorithm used to find the shortest path between nodes of
the graph. The algorithm creates the tree of the shortest paths
from the starting source vertex from all other points in the graph.
It differs from the minimum spanning tree as the shortest
distance between two vertices may not be included in all the
vertices of the graph. The algorithm works by building a set of
nodes that have a minimum distance from the source. Here,
Dijkstra's algorithm uses a greedy approach to solve the problem
and find the best solution.
Example
Let us consider the below example to understand the algorithm.
Here we are given a weighted graph, and we will choose vertex
'A' as the source vertex of the graph.
As the algorithm generates the shortest path from the source
vertex to every other vertex, we will set the distance of the source
vertex to itself as '0'. The distance from the source vertex to all
other vertex is not determined yet, and therefore, we will
represent it using infinity.
For now, the list of unvisited nodes will be: {B, C, D, E}

13