Graphs

INTRODUCTION

Graph is another important non-linear data structure. In tree structure, there

is a hierarchical relationship between parent and children, that is, one
parent and many children. On the other hand, in graph, relationship is less
restricted. Here relationship is from many parents to many children. E.g.,
traffic flow can be modeled by a graph: 1. Each street intersection
represents a vertex, and each street is an edge. 2. The edge costs could
represent, among other things, a speed limit or a capacity (number of
lanes). 3. We can then ask for the shortest route or use this information to
find the most likely locations for bottleneck.

FIGURE 1 Two non-linear data structures: tree and graph

TERMINOLOGIES

Graph
A graph G consists of a nonempty set V called the set of nodes (points,
vertices) of the graph, a set E which is the set of edges of the graph and a
mapping from the set E to a set V. or A graph is a collection of edges and
vertices.

1
 Diagraph
A graph in which every edge is directed that is called directed or diagraph.

Undirected Graph
A graph in which every edge is undirected that is called undirected graph.

Mixed Graph
In graph ‘G’ if some edges are directed and some edges are undirected than
graph ‘G’ is known as mixed graph.

Weighted Graph
If all the edges in the graph are labeled with some weight than this graph is
known as weighted graph.

Incident
2
 An edge connects two vertices, these two vertices are said to be incident to
that edge.

Adjacent Vertices
A vertex Vi is adjacent to Vj if there is an edge from Vi to Vj.

Cycle
A path which starting and ending at the same node is called cycle.

Self loop/sling
If there is an edge whose starting and ending vertices are same, it is called
self loop.

Parallel Edges
If there are more than one edges between the same pair of vertices then
they are known as parallel edges.

Simple Graph
A directed graph which does not have any self loop or parallel edges, it is
called simple graph.

3
 Complete Graph
Graph ‘G’ is said to be complete if each vertex Vi is adjacent to every
other vertex Vj in G is called complete graph. (In short every node is
connected to every node).

Acyclic Graph
If a directed graph do not have any cycle than it is called acyclic graph.

Isolated Graph
A vertex is isolated if there is no edge connected from any other vertex to
that vertex.

Path
A route that does not pass any edge more than one’s is called path of the
graph.

4
 Length of the path
Total edges between starting and ending nodes of the path is called length
of the path. (Distance).

Degree of Vertex
The number of edges connected with vertex Vi is called the degree of
vertex Vi. (How many nodes are connected to one node…).

Indegree
Number of edges comes into Vi, is called indegree of Vi.

Out Degree
Number of edges going from Vi, is called outdegree of Vi.

5
 Pendent Degree
A vertex Vi is called pendent if, its indegree is one and outdegree is zero.

REPRESENTATION OF GRAPH

A graph can be represented in many ways. Some of these representations

are as under:

1. Set representation
2. Linked representation
3. Sequential (matrix) representation.

6
 Read Graph_Representation.pdf

Brief summary from here

Set Representation
This is one of the straight forward methods of representing a graph. With
this method, two sets are maintained: (i) V, the set of vertices, (ii) E, the
set of edges.

Graph G1
V(G1) = { A, B, C, D}
e(G1) = {e1, e2, e3, e4}
E(G1) ={(A-B),(A-C),(B-D),(C-D)}

Linked Representation
Linked representation is another space-saving way of graph representation.
In it, the number of lists depends on the number of vertices in the graph.

Matrix Representation
Matrix representation is the most useful way of representing any graph.
This representation uses a square matrix of order n x n, n being the number
of vertices in the graph. The matrix is alternatively termed as bit matrix or
Boolean matrix as the entries are either 0 or 1.

7
 A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0

Example 1: Represent this graph in Set, List and Matrix.

Set
G1(V)={v1, v2, v3, v4, v5, v6, v7}
G1(e)={e1, e2, e3, e4, e5, e6, e7, e8, e9}
G1(E)={(v1-v2),(v1-v3),(v2-v4),(v2-v1),(v2-v5),(v3-v1),(v3-v7),(v3-
v4),(v4-v2),(v4-v3),(v4-v6),(v5-v2),(v5-v6),(v6-v4),(v6-v5),(v6-v7),(v7-
v6),(v7-v3)}
List

8
 Matrix

V1 V2 V3 V4 V5 V6 V7
V1 0 1 1 0 0 0 0
V2 1 0 0 1 0 0 0
V3 1 0 0 1 0 0 1
V4 0 1 1 0 0 1 0
V5 0 1 0 0 0 1 0
V6 0 0 0 1 1 0 1
V7 0 0 1 0 0 1 0

Example 2: Represent this graph in Set, List and Matrix.

Set
G1(V)={v1, v2, v3, v4, v5, v6, v7}
G1(e)={e1, e2, e3, e4, e5, e6, e7, e8, e9}
G1(E)={(v1-v2),(v3-v1),(v2-v4),(v3-v4),(v5-v2),(v4-v6),(v3-v7),(v5-
v6),(v6-v7)}

List

9
 Matrix

V1 V2 V3 V4 V5 V6 V7
V1 0 1 0 0 0 0 0
V2 0 0 0 1 0 0 0
V3 1 0 0 1 0 0 1
V4 0 0 0 0 0 1 0
V5 0 1 0 0 0 1 0
V6 0 0 0 0 0 0 1
V7 0 0 0 0 0 0 0

GRAPH TRAVERSALS

To traverse a graph means that to visit each node at least once in

systematic manner And by that way to find the shortest path from the
source to the destination node.

In binary tree we traverse inorder, preorder or postorder manner.

Graph is represented by it’s nodes and edges so traversal of each node is

the traversing in graph.

There are several methods available for the graph traversal.

We store the graph in adjacency list.

Traversing a graph is different that traversing a tree, because there is no

first node or root node in a graph. So traversal can start from any node.
Also in tree all nodes are reachable from the root node, so traversing of all
nodes is easier. While in graph it is possible that some nodes are not
reachable from the start node, so we have to recursively check that all
nodes are visited or not.

10
 There are two methods of traversing a graph.

1. Breadth First Search

2. Depth First Search

First method is traversing the graph breadth wise, while second method is
traversing a graph in depth.

Breadth First Search

This method is used to traverse a graph for finding a shortest path from the
starting node to the ending node.
Using BFS algorithm, shortest distance is the minimum number of edges
from the start node to the other remaining nodes. BFS traversal method
will traverse node according to the level that is first level, second level etc.

In BFS we can start from any node of the graph which will be the starting
node of traversal. First we, visit all the adjacent nodes of the start node.
Then we take the next start node, whichever is the nearest of the main start
node. Again we follow the same process that is visit all adjacent nodes.
Here we maintain the flag which will monitor that one node should not
visited more than once.

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

11
 Let’s take an example to understand above process.

View of Breadth First Search

In the following graph if we start from 1 then we traverse all adjacent

nodes of 1 that is 2 and 3. So path will be 1-2-3. Then we visit all adjacent
unvisited nodes of 2 that is 4 and 5, and path will be 1-2-3-4-5. Now
adjacent nodes of 4 are 2, 3 and 5, but all are visited. So we visit all
adjacent unvisited nodes of 5 and final traversal order will be 1-2-3-4-5-6-
7.

Example 3: Convert the given graph into BFS.

Ans:
V1 – v2 – v8 – v3 – v5 – v4 – v7 – v6

12
 Example 4: Convert the given graph into BFS.

Ans:
V1 - v3 – v4 – v2 – v6 – v7 – v5

Example 5: Convert the given graph into BFS.

Ans:
V1 – v2 – v3 – v5 – v4 – v7 – v6 – v8

13
 Depth First Search

DFS traversal of a graph produces a spanning tree as final result. Spanning

Tree is a graph without loops. We use Stack data structure with maximum
size of total number of vertices in the graph to implement DFS traversal.

We use the following steps to implement DFS traversal...

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

 Step 2 - Select any vertex as starting point for traversal. Visit that
vertex and push it on to the Stack.
 Step 3 - Visit any one of the non-visited adjacent vertices of a vertex
which is at the top of stack and push it on to the stack.
 Step 4 - Repeat step 3 until there is no new vertex to be visited from
the vertex which is at the top of the stack.
 Step 5 - When there is no new vertex to visit then use back
tracking and pop one vertex from the stack.
 Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.
 Step 7 - When stack becomes Empty, then produce final spanning tree
by removing unused edges from the graph

Depth First Search

Example 6: Convert the given graph into DFS.

14
 Ans:
V1 – V2 – V4 – V3

Example 7: Convert the given graph into DFS.

Ans:
v1 – v2 – v5 – v6 – v4 – v8 – v3 – v7

Back track

Ans:
v1 – v2 – v5 – v6 – v4 – v8 – v7 – v3

Example 7: Convert the given graph into DFS.

15
 Ans:
V1 – V2 – V5 – V6 – V4 – V8 – V3 – V7

Application of Graph

 In Computer science graphs are used to represent the flow of

computation.
 Google maps uses graphs for building transportation systems, where
intersection of two(or more) roads are considered to be a vertex and the
road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest
path between two vertices.
 In Facebook, users are considered to be the vertices and if they are
friends then there is an edge running between them. Facebook’s Friend
suggestion algorithm uses graph theory. Facebook is an example
of undirected graph.
 In World Wide Web, web pages are considered to be the vertices.
There is an edge from a page u to other page v if there is a link of page v
on page u. This is an example of Directed graph. It was the basic idea
behind Google Page Ranking Algorithm.
 In Operating System, we come across the Resource Allocation
Graph where each process and resources are considered to be vertices.
Edges are drawn from resources to the allocated process, or from
requesting process to the requested resource. If this leads to any
formation of a cycle then a deadlock will occur.
 In mapping system we use graph. It is useful to find out which is an
excellent place from the location as well as your nearby location. In
GPS we also use graphs.
 Facebook uses graphs. Using graphs suggests mutual friends. it
shows a list of the f following pages, friends, and contact list.
 Microsoft Excel uses DAG means Directed Acyclic Graphs.
 In the Dijkstra algorithm, we use a graph. we find the smallest path
between two or many nodes.
 On social media sites, we use graphs to track the data of the users.
liked showing preferred post suggestions, recommendations, etc.
 Graphs are used in biochemical applications such as structuring of
protein, DNA etc.
Thus the development of algorithms t

16