DATA STRUCTURES UNIT-5 KHK

Graphs
What is a Graph?
A graph G consist of
1. Set of vertices V (called nodes), (V = {v1, v2, v3, v4......}) and
2. Set of edges E (i.e., E {e1, e2, e3......cm}
A graph can be represents as G = (V, E), where V is a finite and non-empty set at vertices and E
is a set of pairs of vertices called edges. Each edge „e‟ in E is identified with a unique pair (a, b)
of nodes in V, denoted by e = [a, b].

Consider a graph, G in the above , Then the vertex V and edge E can be represented as:
V = {v1, v2, v3, v4, v5, v6} and E = {e1, e2, e3, e4, e5, e6} E = {(v1, v2) (v2, v3) (v1, v3) (v3,
v4), (v3, v5) (v5, v6)}. There are six edges and vertex in the 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)}

VASAVI DEGREE COLLEGE 1

DATA STRUCTURES UNIT-5 KHK

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 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.

VASAVI DEGREE COLLEGE 2

DATA STRUCTURES UNIT-5 KHK

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.

VASAVI DEGREE COLLEGE 3

DATA STRUCTURES UNIT-5 KHK

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.

VASAVI DEGREE COLLEGE 4

DATA STRUCTURES UNIT-5 KHK

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.

Graph Representation
Graph is a mathematical structure and finds its application is many areas, where the
problem is to be solved by computers. The problems related to graph G must be
represented in computer memory using any suitable data structure to solve the same.
There are four standard ways of maintaining a graph G in the memory of a computer.

VASAVI DEGREE COLLEGE 5

DATA STRUCTURES UNIT-5 KHK

 Adjacency matrix.
 Adjacency list.
 Adjacency array.
 Edge list.
Adjacency Matrix:
Let G =( V, E) be a graph with n vertices , n>= 1 . The adjacency matrix of G is a
two dimensional n × n array say A , with the property that A[ i , j ] =1 if the edge ( i , j)
is in E(G). the element A[ i , j]=0 if there is no such edge in G.
 The adjacency matrix A of a directed graph G = (V, E) can be represented

 An undirected graph can be represented using adjacency matrix. Considered an

undirected graph in Fig.

VASAVI DEGREE COLLEGE 6

DATA STRUCTURES UNIT-5 KHK

 To represent a weighted graph using adjacency matrix, weight of the edge (i, j) is simply
stored as the entry in i th row and j th column of the adjacency matrix.
The adjacency matrix A for a directed weighted graph G = (V, E, We ) can be
represented as
Aij = Wij { if there is an edge from Vi to Vj then represent its weight Wij.}
Aij = – 1 or very –very large +ve infinite number { if there is no edge from Vi to Vj}

The adjacency matrix is a simple way to represent a graph, but it has two disadvantages.
1. It takes n2 space to represent a graph with n vertices, even for a spars graph and
2. It takes O(n2 ) time to solve the graph problem

VASAVI DEGREE COLLEGE 7

DATA STRUCTURES UNIT-5 KHK

Adjacency Lists:
In this representation of graph the “n” rows of the adjacency list are represented as n
linked lists. There is one list for each vertex in G. The nodes in list “ i” represent the
vertices that are adjacent from vertex “i”. each node has at least two fields: vertex and
link. The vertex field contains the indices of the vertices adjacent to vertex „i‟.

Adjacency lists are not well suited for parallelism since the lists require that we traverse
the neighbors of a vertex sequentially.
Adjacency array.
Similar to an adjacency list, an adjacency array keeps the neighbors of all vertices, one
after another, in an array adj; and separately, keeps an array of indices that tell us where
in the adj array to look for the neighbors of each vertex.

Traversing Techniques a Graph

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)

VASAVI DEGREE COLLEGE 8

DATA STRUCTURES UNIT-5 KHK

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).
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

The Breadth first of the above graph is

VASAVI DEGREE COLLEGE 9

DATA STRUCTURES UNIT-5 KHK

Depth First Search:

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

VASAVI DEGREE COLLEGE 10

DATA STRUCTURES UNIT-5 KHK

Explain Spanning Tree

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.

VASAVI DEGREE COLLEGE 11

DATA STRUCTURES UNIT-5 KHK

 Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree
is maximally acyclic.
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
Explain Minimum spanning tree
A minimum spanning tree (MST) for a graph G = (V, E) is a sub graph G1 = (V1, E1) of G
contains all the vertices of G.
1. The vertex set V1 is same as that at graph G.
2. The edge set E1 is a subset of G.
3. And there is no cycle.
If a graph G is not a connected graph, then it cannot have any spanning tree. Suppose a graph G
with n vertices then the MST will have (n – 1) edges, assuming that the graph is connected.
A minimum spanning tree (MST) for a weighted graph is a spanning tree with minimum weight.
That is all the vertices in the weighted graph will be connected with minimum edge with
minimum weights.

VASAVI DEGREE COLLEGE 12

DATA STRUCTURES UNIT-5 KHK

Minimum spanning tree for the above connected graph is

Two algorithms can be used to obtain a minimum spanning tree of a connected weighted and
undirected graph.
 Kruskal‟s Algorithm
 Prim‟s Algorithm

Explain KRUSKAL’S ALGORITHM

This is a one of the popular algorithm and was developed by Joseph Kruskal. To create a
minimum cost spanning trees, using Kruskalls, we begin by choosing the edge with the
minimum cost and add it to the spanning tree. In the next step, select the edge with next
lowest cost, and so on, until we have selected (n – 1) edges to form the complete
spanning tee. The only thing of which beware is that we don‟t form any cycles as we add
edges to the spanning tree.

ALGORITHM
Suppose G = (V, E) is a graph, and T is a minimum spanning tree of graph G.
1. Initialize the spanning tree T to contain all the vertices in the graph G but no edges.
2. Choose the edge e with lowest weight from graph G.
3. Check if both vertices from e are within the same set in the tree T, for all such sets of T.
If it is not present, add the edge e to the tree T, and replace the two sets that this edge
connects.
4. Delete the edge e from the graph G and repeat the step 2 and 3 until there is no more edge
to add or until the panning tree T contains (n-1) vertices.
5. Exit

VASAVI DEGREE COLLEGE 13

DATA STRUCTURES UNIT-5 KHK

VASAVI DEGREE COLLEGE 14

DATA STRUCTURES UNIT-5 KHK

Explain Prim's Algorithm

 Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a
connected weighted undirected graph.
 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.
 This algorithm is directly based on the MST( minimum spanning tree) property.

ALGORITHM
Suppose G = (V,E) is a graph and T is a minimum spanning tree of graph G.
1. Initialize the spanning tree T to contain a vertex v1.
2. Choose an edge e = (v1, v2) of G such that v2 not equal to v1 and e has smallest weight
among the edges of G incident with v1.
3. Select an edge e = (v2, v3) of G such that v2 is not equal to v3 and e has smallest weight
among the edge of G incident with v2.
4. Suppose the edge e1, e2, e3, ...... ei Then select an edge ei + 1 = (Vj, Vk) such that
(a) Vj ∈ {v1, v2, v3, ...... vi, vi + 1} and
(b) Vk ∉ {v1, v2, v3, ...... vi, vi + 1} such that ei+1 has smallest weight among the edge
of G
5. Repeat the step 4 until (n – 1) edges have been chosen
6. Exit

VASAVI DEGREE COLLEGE 15

DATA STRUCTURES UNIT-5 KHK

Topological Sorting
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices
such that for every directed edge uv, vertex u comes before v in the ordering. Topological
Sorting for a graph is not possible if the graph is not a DAG.

For example, a topological sorting of the graph is “5 4 2 3 1

0”. There can be more than one topological sorting for a
graph. For example, another topological sorting of the
following graph is “4 5 2 3 1 0”. The first vertex
in topological sorting is always a vertex with in-degree as 0
(a vertex with no in-coming edges).

VASAVI DEGREE COLLEGE 16