Chapter 8: graphs

Representation of Graph
• Graph terminology including these terms: Vertex, edge, adjacent, incident, degree, cycle, path,
connected component, and spanning tree.
• Three types of graphs : Undirected, directed, and weighted
• Common graph representations: adjacency matrix, packed – adjacency lists, and linked – adjacency
lists.
• Standard graph search methods: breadth-first and depth- first search.

8.1 DEFINITIONS: A graph G= (V, E) is an ordered pair of finite sets V and E. The elements of V
are called as vertices are also called as nodes and points. The elements of E are called edges
are also called arcs and lines. Each edge in E joins two different vertices of V and is denoted by
the tuple (i,j), where i and j are the two vertices joined by E.
8.1.1 Graph Display: A graph generally represented as figure in which the vertices represented by
circles and the edges by lines. Examples, of graphs are as follows:
Some of the edges in this figure are oriented (that they have arrow heads) while other are not. An
edge with an orientation is a directed while an edge with no orientations is an undirected edge. The
undirected edges (i,j) and (j,i) are the same; the directed edge (i,j) is different from the directed edge(j,i)
the former being oriented from I to j and the latter from j to i.
Example: -

1 1

2 4 2

3
3
Undirected Graph G1 Directed graph G2
V ( G1 ) = { 1, 2, 3, 4}; E ( G1 ) = { ( 1, 2 ), ( 1, 3 ), ( 1, 4 ), ( 2, 3 ), ( 2, 4 ), (3, 4 ) }
V ( G2 ) = { 1, 2, 3 }; E ( G2 ) = { < 1, 2 >, < 2, 1 >, < 2, 3 > }
The edges of a directed graph are drawn with an arrow from the tail to the head.
For undirected graph:

1
n(n −1)
2 3 = 3 edges
2

=======================================================================
=======================================================================
For directed graph:

1
3
2 n2 = 9 edges
n(n
−1)
The [Link] possible edges in an undirected graph is and in a directed graph is n2.
2
8.1.2 Directed Graph:
A directed graph or di-graph is a pair G = (V,E) where V is a set whose elements are called
vertices(nodes) and E is a set of ordered pairs of elements of V called edges or directed edges or arcs. For
directed edges(v,w) in E, ‘v’ is its tail and ‘w’ is its head. (v,w) is represented in the diagrams as the arrow,
v w, i.e simply vw.

Vertices = {1,2,3,4}
2 4
Edges = {(1,2), (1,4), (2,4), (3,1),
(3,2), (3,4)}
3

8.1.3 Undirected Graph:

An undirected graph is a pair G = (V,E), where V is a set whose elements are called vertices(nodes)
and E is a set of unordered pairs of distinct elements of V called edges or undirected edges. Each edge
may be considered as a subset of V containing two elements, {v,w} denotes an undirected edge,
represented as v-w i.e simply vw . Of course vw = wv for undirected graph.

Vertices = {1,2,3,4}
2 4 Edges = {(1,2), (1,4), (1,3),
(2,4), (2,3), (3,4)}

Note:
i) An E set cannot have duplicate elements.
ii) An edge that connects a vertex to itself is not possible.
8.1.4 Subgraph:
A subgraph of graph G = (V,E) is a graph G’=(V’,E’) such that V’ ⊆V and E’ ⊆E.

=======================================================================
=======================================================================
Graph G1

2 4

Some of the subgraphs for the graph G1:

1
1 2 4
2 4

2 4 3 3
G1’ G1’
G1’
8.1.5 Symmetric Digraph:
A symmetric digraph is a directed graph such that for every edge vw there is also the reverse edge

wv.

Example: A

B
8.1.6 Symmetric Undirected graph:
Every undirected graph is a symmetric digraph by interpreting each undirected edge as a pair of

directed edges in opposite directions.A

B C
8.1.7 Complete graph:
A complete graph is a graph normally undirected with an edge between each pair of vertices.
Example
A B

C D

8.1.8 Incident edge:

The edge vw is said to be incident, if it is incident on the vertices v and w, and vice versa.

8.1.9 Adjacency Relation:

Adjacency relation in digraph is represented by vAw ( w is adjacent to v ) if and only if vw is in
E. If G is undirected graph, the adjacency relation (A) is symmetric (i.e. wAv if and only if vAw)

=======================================================================
[]
=======================================================================
8.1.10 Path:
A path from v to w in a graph G = (V,E) is a sequence of edges, v 0v1, v1v2,…..vk-1vk, Where v=v0 and
w=vk. The length of the path is k.
Therefore, Length of a path = [Link] edges traversed
Example:
A
Path length
from A to D is 2 A B

C D

.
Note: Path length from vertex V to itself is zero

8.1.11 Connected graph:

An undirected graph is connected if and only if, for each pair of vertices v and w, there is a path from

v to w.
Example: A
A B

B C

C D
D E F G
8.1.11 Strongly Connected Graph:
A directed graph is strongly connected if and only if, for each pair of vertices v and w, there is a path

from v to w. i.e, strong connectivity means travelling the one-way streets in their correct direction from
anywhere to anywhere.

Example: D

A B

8.1.12 Cycle:
Cycle in a directed graph is a simple cycle in which no vertex is repeated except that the first and last
are identical.
A
Example:

B C

Cycle= A B C A

=======================================================================
=======================================================================
The definition of cycle is same for undirected graph also, but there is a requirement that if any edge
appears more than once it always with the same orientation. i.e using the path definition if v i = x and vi+1
= y for 0 ≤ i < k , then there cannot be a j such that vj = y and vj+1 = x.
Example:
A

C
8
.
1
.
1
4

A
c
y
c
l
i
c

g
r
a
p
h
:
y
c
l
e

A
B
C
A
 A

g
r
a
p
h

i
s

a
c
y
c
l
i
c

g
r
a
p
h

i
f
i
t
h
a
s

n
o

c
y
c
l
e
s
.
Examp
le:
(
a
)
A
C

(
b
)
A
Undirected ac
C
B

8.1.15 Co
nn
ec
te
d
co
m
po
ne
nt:
A

c
o
n
n
e
c
t
e
d

c
o
m
p
o
n
e
n
t
o
f
a
n

u
n
d
i
r
e
c
t
e
d

g
r
a
p
h

i
s

m
a
x
i
m
a
l
c
o
n
n
e
c
t
e
d
 s
u
b
g
r
a
p
h

o
f
G
.
Maxim
al: A
graph
is said
to be
maxim
al
within
some
collecti
on of
graphs
if it is
not a
proper
subgra
ph of
any
graph
in that
collecti
on.
The
word
“collec
tion”
means
that all
connec
ted
subgra
phs of
G.

8.1.16 W
ei
gh
te
d
gr
ap
h:
A

w
e
i
g
h
t
e
d

g
r
a
p
h

i
s

t
r
i
p
l
e
(
V
,
E
,
W
)
w
h
e
r
e

(
V
,
E
)
i
s

g
r
a
p
h

(
d
i
r
e
c
t
e
d

o
r
u
 n
d
i
r
e
c
t
e
d
)
a
n
d

i
s

f
u
n
c
t
i
o
n
f
r
o
m
E
i
n
t
o
R
.
F
o
r
a
n
e
d
g
e
E
,
W
(
E
)
i
s
c
a
l
l
e
d
t
h
e
w
e
i
g
h
t
o
f
E
.
E
x
a
m
p
l
e
:

1
0

A
—
D
8
=
.
1 1
. 0
1 ,
7
r
D e
e p
r
g e
r s
e e
e n
t
s

w
e
i
g
h
t

o
f

t
h
e

e
d
g
e
.
 The
numbe
r of
edges
inciden
t on a
vertex
determ
ines its
degree
. The
degree
of the
vertex
V is
written
as
degree
(V).
T

V
,

r
t

x
V

r
 t

====
====
====
====
====
====
====
====
====
====
====
====
====
====
====
====
====
===
=======================================================================
8.2 GRAPH REPRESENTATIONS AND DATA STRUCTURE:
Let G=(V,E) be a graph with n=|V|, number of vertices, m=|E|, number of Edges and
V={v1,v2,v3…….vn}There are several representations for graphs are possible. We can discuss only three
most commonly used. They are
1. Adjacency matrices
2. Adjacency lists
3. Adjacency multilists
4. Incidence matrix
The choice of a particular representation will depend upon the application we expect on graph

8.2.1 Adjacency Matrix Representation:

There are mainly two components in a graph (i.e) nodes and edges. Adjacent matrix is the matrix,
which keeps the information of adjacent nodes. This matrix keeps the information that whether a node is
adjacent to any other node or not.
Let G = ( V, E ) be a graph with n vertices, n ≥ 1. The adjacency matrix of G is a 2 – dimensional n * n
or array[n][n], where the first subscript will be row and second subscript will be column of that matrix, say
A, with the property that
A ( i, j ) = 1 if there is an edge from node Vi, to Vj and is in E ( G )
= 0 if there is no edge from node Vi, to Vj
Hence all the entries of this matrix will be either 1 or 0. The edge weight is 1 for an undirected graph.
A graph containing n vertices can be represented by a matrix with n rows and n columns. The matrix is
formed by storing the edge weight in its i th row and jth column of the matrix, if there exists an edge
between ith and jth vertex of the graph and a ‘0’ if there is no edge between i th and jth vertex of the graph,
such a matrix is referred as an adjacency matrix.
AdjMat[i][j] = Weight of the edge, if there is a path from vertex Vi to
Vj AdjMat[i][j] = 0, otherwise
Now we are going to form a adjacency matrix for,
1. Adjacency matrix for Directed graph
2. Adjacency matrix for Undirected graph
3. Adjacency matrix for Weighted graph
1. Adjacency matrix for Directed graph
Let us consider the graph. The corresponding adjacency matrix for this graph will be

A B
A B 0 1 0 1
A

B 1 0 1 1
C
D C 0 0 0 1
D 1 0 1 0
Adjacency Matrix
The adjacency matrix is maintained in the array arr[4][4]. Here the entry of matrix arr[0][1] = 1, which
represents there is an edge in the graph from node A to B. Similarly arr[2][0]= 0, which represents
there is no edge from node C to node A.

=======================================================================
=======================================================================
2. Adjacency matrix for Undirected graph:
Let us consider an undirected graph and the corresponding adjacency matrix for this graph will be,

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

B D 1 0 1 0
Adjacency Matrix
The adjacent matrix for an undirected graph will be a symmetric matrix. This implies that for every I
and j, A[i][j] = A[j][i] in an undirected graph.
3. Adjacency matrix for Weighted graph:
3 A B
C
A 0 2 ∞ 8
A B
2 B 3 0 4 7
C
9 87 4 ∞∞0 5
D 6 C D 9 ∞ 6 0
Adjacency Matrix
5
The space needed to represent a graph using its adjacency matrix is n 2 bits.
Disadvantages:
1. Takes O(n2) space to represents the graph
2. It takes O(n2) time to solve the most of the problems.

8.2.2 Adjacency List Representation:

A graph containing n vertices and m edges can be represented using a linked list, referred to as
adjacency list. The number of vertices in the graph forms a singly linked list.
In this representation the n rows of the adjacency matrix are represented as n linked lists.
Each vertex have a separate linked list, with nodes equal to the number of edges connected from
the corresponding vertex. The nodes in list i represent the vertices that are adjacent from vertex i.
Each node has atleast two fields: VERTEX and LINK. VERTEX fields contain the indices of the
vertices adjacent to vertex i.
Advantages:
Eventhough adjacency list is a difficult way of representing graphs, a graph with large number of
nodes will use small amount of memory.
In adjacency list representation of graph, we will maintain two lists. First list will keep track of all
the nodes in the graph and second list will maintain a list of adjacent nodes for each node.
1. Adjacency lists for Directed graph:

A B

D C

=======================================================================
=======================================================================
Adjacency list for the above graph is as follows:

Vertex 1 A B D

Vertex 2 B A C D

Vertex 3 C D

Vertex 4 D A C
2. Adjacency lists for Undirected graph:
Let us consider the following undirected graph,

C D

B
The adjacency list for the above graph is as follows:

Vertex 1 A B C D

Vertex 2 B A C D

Vertex 3 C A B D

Vertex 4 D A B D

In this representation each list had a head node. The head nodes are sequential providing easy
random access to the adjacency list for any particular vertex. For an undirected graph with n vertices and
m edges this representation requires n head nodes and 2m list nodes. The storage required is then log n +
log m for the list nodes and O ( log n ) for head nodes because 2 fields in each node.
The structure of header node is:
Name of the node
Pointer which points to the first node adjacent to header node

Pointer which points to the next node in header node list

The total number of edges in G may, therefore can be determined by counting the number of
nodes on its adjacency list. In order to determine in-degree of a vertex easily, we can maintain one more
list called inverse-adjacency lists for each vertex. Each list will contain a node for each vertex adjacent to
the vertex it represents.
Disadvantages:
It takes O(n) time to determine whether there is an arc from vertex i to vertex j. Since there can be
O(n) vertices on the adjacency list for vertex i.

=======================================================================
=======================================================================
8.2.3 Adjacency Multilists Representation:
In adjacency list representation of an undirected graph each edge (V i, Vj) is represent by two entries,
one on the list for V i and other on the List for V j. Using Multilists each edge will be in exactly one node, but
this node will be in two lists. i.e the adjacency lists for each of the two nodes it is incident to the node
structural now becomes
M V1 V2 Link1 for V1 Link2 for V2

Here M is a one bit mark field that may be used to indicate whether or not the edge has been examined.

8.2.4 Incidence Matrix Representation:

A graph containing n vertices and m edges can be represented by a matrix with n rows and m
columns. The matrix is formed by storing: ‘1’ in its i th row and jth column corresponding to the matrix, if
there exists as a ith vertex, connected to one end of the j th edge and a ‘0’ if there is no j th vertex
connected to an end of the jth edge of the graph, such a matrix is referred as an incidence matrix.
IncMat[i][j] = 1, if there is an edge Ej from Vi.
IncMat[i][j] = 0, otherwise
Example 1: Let us consider the following undirected graph,

V1 E1

V2 E2 V4
E3
V3
The incidence matrix for the above graph is as follows:
E1 E2 E3
V1 1 0 0
V2 0 1 0
V3 0 0 1
V4 1 1 1
Disadvantage of Incidence matrix:
1. Eventhough incidence matrix is an easy way of representing graphs, a graph with considerable
number of nodes could use a large amount of memory.
2. Most of the incidence matrices will be sparse matrices only( a matrix with lot of zeros in it).

8.3 APPLICATIONS OF GRAPHS:

The problems using graph representation are useful in many fields for different operations. Some
examples are:
8.3.1 Airline route map-undirected graph
The vertices are cities, a line connects two cities if and only if there is a nonstop flight between
them in both directions. A

C D

B
A graph between four cities = {A, B, C, D}

=======================================================================
=======================================================================
8.3.2 An electrical circuit:
The vertices could be diodes, transistors, capacitors, Switches and so on. Two vertices are
connected by a line if there is a wire connecting them.

8.3.3 Flowcharts – Directed graph

The vertices are the flowchart boxes; the connecting arrows are the flowchart arrows.
Flowchart: Directed graph:

1 Start 1

2 Read n 2

3 Sum=0 3
i=1
4
7
4 While No 5
i<=n 7
8
Print sum 6
5 Yes
8
Sum=sum+i
Stop
6
i=i+1

8.3.4 Computer Networks:

The vertices are computers. The lines (undirected graph) or arrows (directed graph) are the
communication links.
Example:

a) A star network b) A ring network

(undirected graph) (directed graph)
=======================================================================
8.4 GRAPH TRAVERSALS
Graph traversal is defined as visiting all the vertices of the graph G = (V, E), where V is the set of
vertices and E is the set of edges.
Two different types of traversal strategies are:
1. Depth First Search ( DFS )
2. Breadth First Search ( BFS )
8.4.1 Depth First Search ( DFS ) :
DFS is otherwise known as Depth first Traversal(DFT), it is kind of tree
traversal. DFS technique is as follows:
♦ Starting vertex may be determined by the problem or chosen arbitrarily. Visit the start vertex v, next an
unvisited vertex w adjacent to v is selected and a DFS from w is initiated. When a vertex u is reached
such that all the adjacent vertices have been visited, we back up to the last vertex visited which has an
unvisited vertex w adjacent to it and initiate a DFS from w. The search terminates when no unvisited
vertex can be reached from any of the initiated vertices.

♦ If path exists from one node to another node walk across the edge – exploring the edge.
♦ If path does not exist from one specific node to any other node, return to the previous node
where we have been before – backtracking.
The theme of DFS is to explore if possible, otherwise backtrack.
Algorithm:
Procedure DFS(u)

VISITED (u) ← 1
for each vertex w adjacent to v do
if VISITED ( w ) = 0 then call DFS ( w )
end
end DFS
Example:

a) A D
A directed graph G=(V,E) is given, where
B V={ A, B, C, D, E, F, G }
G For simplicity, assume the start vertex is A
and exploration is done in alphabetical order.
F C E

b) A D

B From start vertex A explores to B, now AB is

G
explored edge.
F C E

c)
A D

B G
From vertex B either C or D to be explored,
but C is explored as per the alphabetical order.
F C E There is nowhere to explore from C, therefore
=======================================================================
C is a dead end.

]
=======================================================================
d)

A DB
Since C is a dead end, backtrack to B, from there
explore to D
G

F C E
e)
A D From D it is possible to explore A, this would
complete a cycle, but trees should not have
B cycles.
G Again backtrack to B, from there backtrack to
F C E A, explore the path to F.
f)

A D From F it is possible to traverse either A or C, but

both the nodes are discovered nodes. So F
B is also a dead end.
G From the above diagram it is possible to say that G
and E are never traversed.
F C E
8.4.2 Breadth First Search:
Starting at vertex v and marking it as visited. BFS performs simultaneous explorations starting from a
common point and spreading out independently.
Breadth firs search differs from depth first search in that all unvisited vertices adjacent to v are visited
next. Then unvisited vertices adjacent to these vertices are visited and so on. A breadth first search
beginning at vertex v1 of the graph in above figure would first visit root node and then one by one in the
same level and passes to other level.
BFS Technique steps:
1. Put the ending node (the root node) in the queue.
2. Pull a node from the beginning of the queue and examine it.
o If the searched element is found in this node, quit the search and return a result.
o Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this
node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and
return "not found".
4. Repeat from Step 2.
Procedure BFS
//Breadth first search of G is carried out beginning at vertex v. All the vertices
visited are
marked as VISITED(i) = [Link] graph G and array VISITED are global and VISITED is
initialized to zero //
VISITED (v) ← 1
Initialize Q to be empty // Q is queue //

=======================================================================
=======================================================================
Loop
for all vertices w adjacent to v do
if VISITED(w) = 0 // add w to queue //
then [ call ADDQ(w, Q); VISITED(w) ← 1 ]
end // mark w as VISITED//
if Q is empty then return
call DELETEQ ( v, Q )
forever
end BFS
Implementation:
void BFS(VLink G[], int v)
{
int w; VISIT(v); /*visit vertex v*/
visited[v] = 1; /*mark v as visited : 1 */
ADDQ(Q,v);
while(!QMPTYQ(Q))
{
v = DELQ(Q); /*Dequeue v*/
w = FIRSTADJ(G,v); /*Find first neighbor, return -1 if no neighbor*/
while(w != -1)
{
if(visited[w] == 0)
{
VISIT(w); /*visit vertex v*/
ADDQ(Q,w); /*Enqueue current visited vertex w*/
visited[w] = 1; /*mark w as visited*/
}
W = NEXTADJ(G,v); /*Find next neighbor, return -1 if no neighbor*/
}
}
}

Main Algorithm of apply Breadth-first search to graph

G=(V,E)： void TRAVEL_BFS(VLink G[], int visited[], int n)
{
int i;
for(i = 0; i < n; i ++)
{
visited[i] = 0; /* Mark initial value as 0 */
}
for(i = 0; i < n; i ++)

if(visited[i] == 0)

=======================================================================
=======================================================================
BFS(G,i);
}
Applications of Graph Traversal: -
1. Finding the components of a graph and
2. Finding a spanning tree of a connected graph
3. Finding the shortest path between two nodes u and v (in an unweighted graph)

Example:
a)
A D
A directed graph G=(V,E) is given, where V={ A,
B B, C, D, E, F, G }
G Assume the start vertex is A. Explore all
paths from vertex A
F C EA
b)
DB

F C EA G From A the explored edges are AF, AB

DB

c) Explore all paths from vertex B and F. From B

the explored edges are BD, BC. From F the
explored edges are FA, FC.
F C E
G The dashed lines shows the edges that were explored
d) but went to vertices that were previously
discovered.(i.e FA, FC)
A D From D the explored edge is DA.
But A is already exist in the discovered
B G vertices list. So we will say that the edge DA
is checked rather than explored.
F C E
* There is no backtracking in BFS and E and G are unreachable.
8.4.3 DFS vs BFS
Depth first search Breadth first search
Backtracking is possible from a dead end 1. Backtracking is not possible.
Vertices from which exploration is incomplete 2. The vertices to be explored are organized as a
are processed in a LIFO order. FIFO queue.
Search is done in one particular direction at the 3. Search is done parallely in all possible direction.
time.