58

B.Sc. IV SEMESTER

UNIT – IV

GRAPHS

What is Graph? Explain terminology of Graphs.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Generally, a graph G is represented as G = (V, E), where V is set of vertices and

E is set of edges.
G=(V,E)
V(G)={v0,v1,v2…..vn-1}
E(G)={e1,e2….en)
Example
The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = (V, E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}

Graph Terminology (or ) Graph Components

We use the following terms in graph data Components
Vertex
A individual data element of a graph is called as Vertex. Vertex is also known
as node. In above example graph, A, B, C, D & E are known as vertices.
Edge
An edge is a connecting link between two vertices. Edge is also known as Arc.
An edge is represented as (startingVertex, ending Vertex).
Example: In the above graph, the link between vertices A and B is represented
as (A, B). In above example graph, there are 7 edges (i.e., (A, B), (A, C), (A, D),
(B,D), (B,E), (C,D), (D,E)).
Undirected Graph
A graph with only undirected edges is said to be undirected graph.

Data Structures Prepared by Mahesh MCA

 59
B.Sc. IV SEMESTER

Directed Graph
A graph with only directed edges is said to be directed graph.

Degree
Total number of edges connected to a vertex is said to be degree of that vertex.
In-degree
Total number of incoming edges connected to a vertex is said to be in-degree of
that vertex.
Out-degree
Total number of outgoing edges connected to a vertex is said to be out-degree of
that vertex.
Path
A path is a sequence of alternating vertices and edges that starts at a vertex
and ends at a vertex such that each edge is incident to its predecessor and
successor vertex.
Adjacent
If there is an edge between vertices A and B then both A and B are said to be
adjacent. In other words, Two vertices A and B are said to be adjacent if there
is an edge whose end vertices are A and B.
Mixed Graph
A graph with undirected and directed edges is said to be mixed graph.
Origin
If an edge is directed, its first endpoint is said to be origin of it.
Destination
If an edge is directed, its first endpoint is said to be origin of it and the other
endpoint is said to be the destination of the edge.
Cyclic graph:- A graph that has cycles is called cyclic graph.
Acyclic graph:- a graph that has no cycles is called an acyclic graph.
Isolated graph:- if a node has no edges connected with any other node then it‘s
degree will be o and it will be called isolated graph.
Self-loop
An edge (undirected or directed) is a self-loop if its two endpoints coincide.
Multigraph:- a graph which has loop or multiple edges can be described as
multigraph.

Data Structures Prepared by Mahesh MCA

 60
B.Sc. IV SEMESTER

Explain different types of Graphs.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Generally, a graph G is represented as G = (V, E), where V is set of vertices and

E is set of edges.
G=(V,E)
Types of Graphs:

1. Directed graph

2. Undirected Graph

3. Weighted Graph

Directed Graph:
A directed graph G is defined as an ordered pair (V, E) where, V is a set of
vertices and the ordered pairs in E are called edges on V. A directed graph can
be represented geometrically as a set of marked points (called vertices) V with a
set of arrows (called edges) E between pairs of points (or vertex or nodes) so
that there is at most one arrow from one vertex to another vertex. For example,
in the figure shows a directed graph, where G = {a, b, c, d }, {(a, b), (a, d), (d, b),
(d, d), (c, c)}

An edge (a, b), in said to the incident with the vertices it joints, i.e., a, b. We
can also say that the edge (a, b) is incident from a to b. The vertex a is called
the initial vertex and the vertex b is called the terminal vertex of the edge (a, b).
If an edge that is incident from and into the same vertex, say (d, d) of (c, c) in
the above Fig , is called a loop.

Undirected Graph:
An undirected graph G is defined abstractly as an ordered pair (V, E), where V
is a set of vertices and the E is a set at edges. An undirected graph can be

Data Structures Prepared by Mahesh MCA

 61
B.Sc. IV SEMESTER

represented geometrically as a set of marked points (called vertices) V with a

set at lines (called edges) E between the points. An undirected graph G is
shown in Fig.

Weighted Graph:
A graph G is said to be weighted graph if every edge and/or vertices in the
graph is assigned with some weight or value. A weighted graph can be defined
as G = (V, E, We, Wv) where V is the set of vertices, E is the set at edges and
We is a weights of the edges whose domain is E and Wv is a weight to the
vertices whose domain is V. Consider a graph In Fig, which shows the distance
in km between four metropolitan cities in India. Here V = {N, K, M, C,} E = {(N,
K), (N,M,), (M,K), (M,C), (K,C)} We = {55,47, 39, 27, 113} and Wv = {N, K, M, C}
The weight at the vertices is not necessary to maintain have become the set Wv
and V are same.

Complete Graph:
A graph G is said to complete (or fully connected or strongly connected) if there
is a path from every vertex to every other vertex. Let a and b are two vertices in
the directed graph, then it is a complete graph if there is a path from a to b as
well as a path from b to a. A complete graph with n vertices will have n (n –
1)/2 edges.

Data Structures Prepared by Mahesh MCA

 62
B.Sc. IV SEMESTER

Write a short note on path of a graph.

Path and Circuit:

In a directed graph, a path is a sequence of edges (e1, e2, e3, ...... en) such that
the edges are connected with each other (i.e., terminal vertex en coincides with
the initial vertex e1). A path is said to be elementary if it does not meet the
same vertex twice. A path is said to be simple if it does not meet the same
edges twice. Consider a graph in Fig.

Where (e1, e2, d3, e4, e5) is a path; (e1, e3, e4, e5, e12, e9, e11, e6, e7, e8,
e11) is a path but not a simple one; (e1, e3, e4, e5, e6, e7, e8, e11, e12) is a
simple path but not elementary one; (e1, e3, e4, e5, e6, e7, e8) is an elementary
path.

A circuit is a path (e1, e2, .... en) in which terminal vertex of en coincides with
initial vertex of e1. A circuit is said to be simple if it does not include (or visit)
the same edge twice. A circuit is said to be elementary if it does not visit the
same vertex twice. In Fig. (e1, e3, e4, e5, e12, e9, e10) is a simple circuit but
not a elementary one; (e1, e3, e4, e5, e6, e7, e8, e10) is an elementary circuit.

Data Structures Prepared by Mahesh MCA

 63
B.Sc. IV SEMESTER

Write the Applications of Graphs

Since they are powerful abstractions, graphs can be very important in modeling
data.

Social network graphs: Graphs that represent who knows whom, who
communicates with whom or other relationships in social structures

Transportation networks: Graph networks are used by many map programs

such as Google maps, Bing maps and now Apple IOS 6 maps to find the best
routes between locations.

Utility graphs. The power grid, the Internet, and the water network are all
examples of graphs where vertices represent connection points, and edges the
wires or pipes between them.

Document link graphs. The best known example is the link graph of the web,
where each web page is a vertex, and each hyperlink a directed edge.

Network packet traffic graphs. Vertices are IP (Internet protocol) addresses

and edges are the packets that flow between them.

Robot planning. Vertices represent states the robot can be in and the edges
the possible transitions between the states.

Neural networks. Vertices represent neurons and edges the synapses between
them. Neural networks are used to understand how our brain works and how
connections change when we learn.

Semantic networks. Vertices represent words or concepts and edges represent

the relationships among the words or concepts.

Graphs in compilers. Graphs are used extensively in compilers. They can be

used for type inference, for so called data flow analysis, register allocation and
many other purposes.

Data Structures Prepared by Mahesh MCA

 64
B.Sc. IV SEMESTER

Explain squential representation of a graph with example.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Graph data structure is represented using following representations:

Adjacency Matrix( sequential )
Adjacency List(linked)
Adjacency Matrix(Sequential Representation)

In this representation, graph can be represented using a matrix of size total

number of vertices by total number of vertices. Adjacency matrix is the matrix,
which keeps the information of adjacency nodes. The adjacency matrix A of a
graph G=(V,E) with n nodes is an MXN matrix such that,
A[i][j]= { 1 If there is an edge from node i to node j
0 if there is no edge from node I to node j }

Example:
For a Undirected graph representation the adjacency matrix representation is

For a Directed graph representation the adjacency matrix representation is

That means if a graph with 4 vertices can be represented using a matrix of 4X4
class. In this matrix, rows and columns both represent vertices. This matrix is
filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to
column vertex and 0 represents there is no edge from row vertex to column
vertex.

Data Structures Prepared by Mahesh MCA

 65
B.Sc. IV SEMESTER

Explain Linked representation of a graph with example.

In adjacency list representation of graph, we will maintain two lists. First list
will keep track of an nodes in the graph and second list will maintain a list of
adjacent nodes for each node. It is more efficiency of than adjacency matrix.
Example: Consider the following directed graph representation implemented
using linked list

Explain various graph traversals with examples.

Many application of graph requires a structured system to examine the vertices

and edges of a graph G. That is a graph traversal, which means visiting all the
nodes of the graph. There are two graph traversal methods.

Breadth First Search (BFS)

Depth First Search (DFS)

Breadth First Search (BFS):

In breadth first search we start at a vertex v and mark it as having reached

(visited). The vertex v is at this time said to be unexplored. A vertex is said to
have been explored by an algorithm has visited all vertices adjacent from it. All
unvisited vertices adjacent from v are visited next and so on.

A complete traversal of the graph can be made by repeatedly calling BFS each
time with a new unvisited starting vertex.

Step-1: Initialize all nodes to the ready state (status-1)

Step-2: Put the starting node A in QUEUE and change its status to the waiting
state (status-2)

Step-3: Repeat steps 4 and 5 until queue is empty.

Step-4: Remove the front node N of queue, process N and change the status of
N to the processes state (status-3).

Data Structures Prepared by Mahesh MCA

 66
B.Sc. IV SEMESTER

Step-5; Add to the rear of queue all the neighbors of N that are in the ready
state (status- 1) and change their status to the waiting state (status-2).

Step-6: Exit

Depth First Search: (DFS)

Depth first search (DFS) of undirected graph proceeds as follows. The start
vertex ―V‖ is visited. Next an unvisited vertex ―W‖ adjacent to ―V‖ is selected
and a depth first search from ―w‖initiated. When a vertex ―v‖ reached such that
all its adjacent vertices have been visited, we back up to the last vertex visited
which was an unvisited vertex ‟w‖ adjacent to its and initiate a depth search
vertex can be reached from any of the visited ones.

Algorithm:
Step-1: Initialize all nodes to the ready state (status-1).
Step-2: Push the starting node A onto the Stack and change its status to the
waiting state (status-2). Step-3: Repeat step 4 and 5 until stack is empty.
Step-4: Pop the top node N of stack . process N and change its status to the
processed state (STATUS-3).
Step-5: Push onto stack all the neighbor of N that are still in the ready state
(status-1) and change their status to the waiting state (status-2).
Step-5: Exit.

The depth first search of the above graph is

Data Structures Prepared by Mahesh MCA

 67
B.Sc. IV SEMESTER

Discuss about Spanning Trees.

A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Hence, a spanning tree does not have
cycles and it cannot be disconnected. Every connected and undirected Graph G
has at least one spanning tree. A disconnected graph does not have any
spanning tree, as it cannot be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected
graph can have maximum nn-2 number of spanning trees, where n is the
number of nodes. In the above addressed example, 33−2 = 3 spanning trees are
possible.

General Properties of Spanning Tree

Following are a few properties of the spanning tree connected to graph G –
A connected graph G can have more than one spanning tree.
All possible spanning trees of graph G, have the same number of edges
and vertices.
The spanning tree does not have any cycle (loops).
Removing one edge from the spanning tree will make the graph
disconnected, i.e. the spanning tree is minimally connected.
Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.

Data Structures Prepared by Mahesh MCA

 68
B.Sc. IV SEMESTER

Mathematical Properties of Spanning Tree

Spanning tree has n-1 edges, where n is the number of nodes (vertices).
From a complete graph, by removing maximum e - n + 1 edges, we can
construct a spanning tree.
A complete graph can have maximum nn-2 number of spanning trees.

Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in
a graph. Common applications of spanning trees are –
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
Minimal Spanning tree Algorithms
There are two algorithms for finding Minimum spanning tree
1) Prim‘s algorithm
2) Kruskal‘s algorithm
1) Prim’s algorithm
Prim's algorithm to find minimum cost spanning tree uses the greedy
approach. Prim's algorithm shares a similarity with the shortest path
first algorithms.
Algorithm
1) One node is picked as a root node (u) from the given connected graph.
2) At each stage choose a new vertex v from u, by considering an edge (u, v)
with minimum cost among all the edges from u, where u is already in the tree
and v is not in the tree.
3) The Prim‘s algorithm table is constructed with three parameters. They are:
Known – Vertex is added in the tree or not.
dv –Weight of the shortest arc connecting v to a known vertex.
Pv – last vertex which causes a change in dv
4) After selecting the vertex v, update rule is applied for each unknown w
adjacent to v. The rule is dw=Min (dw, Cw,v) that is if more than one path exist
between v to w, then dw is updated with minimum cost.
Example:
For the following graph construct Minimum spanning tree using Prim‘s
algorithm.

Data Structures Prepared by Mahesh MCA

 69
B.Sc. IV SEMESTER

2) Kruskal’s algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum
spanning tree for a connected weighted graph. This means it finds a subset of
the edges that forms a tree that includes every vertex, where the total weight of
all the edges in the tree is minimized. If the graph is not connected, then it
finds a minimum spanning forest (a minimum spanning tree for each
connected component). Kruskal's algorithm is an example of a greedy
algorithm.

Algorithm:
1) Start by selecting the two nodes with the minimal costing link.
2) Select any two nodes with the minimal costing link. Your selection is not
bound by any requirement to
select nodes connected to previously selected nodes. Any two nodes we can
select, as long as it the minimal cost.
3) Repeat steps 1 and 2 until all nodes have been selected / connected.
Example:

Solution:

Data Structures Prepared by Mahesh MCA

 70
B.Sc. IV SEMESTER

Data Structures Prepared by Mahesh MCA

 71
B.Sc. IV SEMESTER

UNIT – V
Sortings & Searching

Sorting terminology and Sorting techniques:

Sorting is one of the most important and fundamental operations performed in
computer science. It is the task of rearranging data in an order such as
Ascending, Descending or Lexicographic order. Here the data may be of any
type like numerical, alphabetical or alphanumeric.The task sorting is done
more requently in the world of computer science. Sorting is important for the
following reasons.
1. How to rearrange a given set of data?
2. What kind of data structures are suitable to store data prior to their sorting?
3. How fast can the sorting be achieved?
4. How to sort various types of data values?
Basic Terminology
Internal Sorting:When a set of data to be stored in small enough such that the
entire sorting can be performed in a computer‘s internal storage(primary
memory) then the sorting is called ‗Internal Sort‘.
External Sort:Sorting of a large set of data, which is stored in external
memory(such as hard disk) is called ‗External Sorting‘.
Ascending Order:An arrangement of data is in increasing order of elements is
called ascending order . if Ai and Aj are two data items and Ai proceeds Aj then
Ai<= Aj.
Eg: {1, 2, 3, 4, 5, 6, 7, 8}
Descending Order:An arrangement of data is in decreasing order of elements
is called descending order . if Ai and Aj are two data items and Ai proceeds Aj
then Ai>= Aj.
Eg: {8, 7, 6, 5, 4, 3, 2, 1}
Lexicographic Order:Arranging character or string data values into dictionary
order is known lexicographic order. Eg: {Ant, Bat, Cat, Doll, Egg}
Swap:
Swap between two data storages implies the interchange of their contents.
Eg: Before Swap a[1] = 10 a[2] = 20
After Swap a[1] = 20 a[2] = 10.
Sorting Methods:
There are several sorting methods/strategies available to sort data in computer
data
processing. Each method follows a different strategy/algorithm to sort data.
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Data Structures Prepared by Mahesh MCA