Chapter 13

Graphs

Introduction

A graph is an abstract data structure that is used to implement

the graph concept from mathematics. A graph is basically, a
collection of vertices (also called nodes) and edges that connect
these vertices. A graph is often viewed as a generalization of the
tree structure, where instead of a having a purely parent-to-child
relationship between tree nodes, any kind of complex
relationships between the nodes can be represented.

Why graphs are useful?

Graphs are widely used to model any situation where entities or
things are related to each other in pairs; for example, the
following information can be represented by graphs:
Family trees in which the member nodes have an edge from
parent to each of their children.
Transportation networks in which nodes are airports,
intersections, ports, etc. The edges can be airline flights, one-

Definition
A graph G is defined as an ordered set (V, E), where
V(G) represent the set of vertices and E(G) represents
the edges that connect the vertices.
The figure given shows a graph with V(G) = { A, B, C,
D and E} and E(G) = { (A, B), (B, C), (A, D), (B, D), (D,
E), (C, E) }. Note that there are 5 vertices or nodes
and 6 edges in the graph.
A

Definition
A graph can be directed or undirected. In an
undirected graph, the edges do not have any
direction associated with them. That is, if an edge is
drawn between nodes A and B, then the nodes can be
traversed from A to B as well as from B to A. The
above figure shows an undirected graph because it
does not gives any information about the direction of
the edges.
The given figure shows a directed graph. In a
directed graph, edges form an ordered pair. If there is
an edge from A to B, then
there
is a path
from A to B
A
B
C
but not from B to A. The edge (A, B) is said to initiate
from node A (also known as initial node) and
D
E
terminate at node B (terminal
node).

Graph Terminology
Adjacent Nodes or Neighbors: For every edge, e = (u,
v) that connects nodes u and v; the nodes u and v are
the end-points and are said to be the adjacent nodes
or neighbors.
Degree of a node: Degree of a node u, deg(u), is the
total number of edges containing the node u. If deg(u)
= 0, it means that u does not belong to any edge and
such a node is known as an isolated node.
Regular graph: Regular graph is a graph where each
vertex has the same number of neighbors. That is
every node has the same
degree. A 2regular
graph with
1 regular graph
regular graph
regular graph
vertices Oof
degree k is called a kregular graph or
regular graph of degree k.

Graph Terminology

Path: A path P, written as P = {v0, v1, v2,.., vn), of length n

from a node u to v is defined as a sequence of (n+1) nodes. Here,
u = v0, v = vn and vi-1 is adjacent to vi for i = 1, 2, 3, , n.
Closed path: A path P is known as a closed path if the edge has
the same end-points. That is, if v0 = vn.
Simple path: A path P is known as a simple path if all the nodes in
the path are distinct with an exception that v0 may be equal to
vn. If v0 = vn, then the path is called a closed simple path.
Cycle: A closed simple path with length 3 or more is known as a
cycle. A cycle of length k is called a k cycle.

Connected graph: A graph in which there exists a path between

any two of its nodes is called a connected graph. That is to say
that there are no isolated nodes in a connected graph. A
connected graph that does not have any cycle is called a tree.

Complete graph: A graph G is said to be a complete, if all its nodes

are fully connected, that is, there is a path from one node to every
other node in the graph. A complete graph has n(n-1)/2 edges,

Graph Terminology
Labeled graph or weighted graph: A graph is said to be
labeled if every edge in the graph is assigned some data.
In a weighted graph, the edges of the graph are assigned
some weight or length. Weight of the edge, denoted by
w(e) is a positive value which indicates the cost of
traversing the edge.
Multiple edges: Distinct edges which connect the same
end points are called multiple edges. That is, e = {u, v)
and e = (u, v) are known as multiple edges of G.
Loop: An edge that has identical end-points is called a
loop. That is, e = (u, u).
Multi- graph: A graph with multiple edges and/or a loop is
called a multi-graph.
Size of the graph: The size of a graph is the total number
of edges in it.

Graph Terminology

(b) Tree

(a) Multi-graph

(c) Weighted Graph

3

e1

e4

B
e3

D
e6

C
e7

B
2

e2

e5

F
D

B
3

Directed Graph
A directed graph G, also known as a digraph, is a
graph in which every edge has a direction assigned
to it. An edge of a directed graph is given as an
ordered pair (u, v) of nodes in G. For an edge (u, v) The edge begins at u and terminates at v
U is known as the origin or initial point of e.
Correspondingly, v is known as the destination or
terminal point of e
U is the predecessor of v. Correspondingly, v is the
successor of u
nodes u and v are adjacent to each other.

Terminology of a Directed
Graph

Out-degree of a node: The out degree of a node u,

written as outdeg(u), is the number of edges that
originate at u.
In-degree of a node: The in degree of a node u,
written as indeg(u), is the number of edges that
terminate at u.
Degree of a node: Degree of a node written as
deg(u) is equal to the sum of in-degree and outdegree of that node. Therefore, deg(u) = indeg(u) +
outdeg(u)
Source: A node u is known as a source if it has a
positive out-degree but an in-degree = 0.
Sink: A node u is known as a sink if it has a positive
in degree but a zero out-degree.
Reachability: A node v is said to be reachable from
node u, if and only if there exists a (directed) path
from node u to node v.

Terminology of a Directed
Graph

Strongly connected directed graph: A digraph is said

to be strongly connected if and only if there exists a
path from every pair of nodes in G. That is, if there is
a path from node u to v, then there must be a path
from node v to u.
Unilaterally connected graph: A digraph is said to be
unilaterally connected if there exists a path from any
pair of nodes u, v in G such that there is a path from
u to v or a path from v to u but not both.
Parallel/Multiple edges: Distinct edges which connect
the same end points are called multiple edges. That
is, e = {u, v) and e = (u, v) are known as multiple
edges of G.
Simple directed graph: A directed graph G is said to
be a simple directed graph if and only if it has no
parallel edges. However, a simple directed graph
may contain cycle with an exception that it cannot
have more than one loop at a given node

Directed Graph
Definition:
For a directed graph G = (V,E), where V is the set of vertices and E
is the set of edges, the transitive closure of G is a graph G* =
(V,E*). In G*, for every vertex v, w in V there is an edge (v, w) in E*
if and only if there is a valid path from v to w in G.
Why and where is it needed?
Finding the transitive closure of a directed graph is an important
problem in many computational tasks that listed below.
Transitive closure is used to find the reachability analysis of
transition networks representing distributed and parallel systems
It is used in the construction of parsing automata in compiler
construction
Recently, transitive closure computation is being used to evaluate
recursive database queries (because almost all practical recursive
queries are transitive in nature).

Directed Graph
Algorithm
The algorithm to find transitive enclosure of a graph G
is given in figure below. In order to determine the
transitive closure of a graph, we define a matrix t
where tkij = 1, (for i, j, k = 1, 2, 3, n) if there exists
a path in G from the vertex i to vertex j with
intermediate vertices in the set (1, 2, 3, .., k) and 0
otherwise. That is, G* is constructed by adding an
edge (i, j) into E* if and only if tkij = 1.

Directed Graph
When k = 0

T0ij =

0 if (i, j) is not in E
1 if (I, j) is in E

When k 1

Tkij = Tk-1ij V (Tk-1ik Tk-1kj)

Transitive_Closure( A, t, n)
Step
Step
Step
Step

Step
Step
Step
Step
Step
Step
Step
Step

1: SET i=1, j=1, k=1

2: Repeat Steps 3 and 4 while i<=n
3:
Repeat Step 4 while j<=n
4:
IF (A[i][j] = 1), then
SET t[i][j] = 1
ELSE
SET t[i][j] = 0
INCREMENT j
INCREMENT i
5: Repeat Steps 6 to 11 while k<=n
6:
Repeat Step 7 to 10 while i<=n
7:
Repeat Step 8 and 9 while j<=n
8:
SET t[i,j] = t[i][j] V ( t[i][k] t[k][j])
9:
INCREMENT j
10:
INCREMENT i
11: INCREMENT k
12: END

Bi Connected Graphs
A vertex v of G is called an articulation point if
removing v along with the edges incident to v, results
in a graph that has at least two connected
components.
A bi-connected graph is defined as a connected graph
that has no articulation vertices. That is, a biconnected graph is connected and non-separable, in
the sense that even if we remove any vertex from the
graph, the resultant graph is still connected. By
definition,
A bi-connected undirected graph is a connected
graph that is not broken into disconnected pieces by
deleting any single vertex

Bi Connected Graphs
A

H
A

I
B

J
D

F
E

Note that the graph shown on the left is not a biconnected graph as deleting vertex C from the
graphs results in two connected components of the
original graph (figure on right)

Bi Connected Graphs
A

Bi-connected graph. Removal of any vertex from the

graph will not disconnect the graph

Like graphs, there is a related concept for edges. An edge in a

graph is called a bridge, if removing that edge results in a
disconnected graph. Also, an edge on the graph that does not lie
on a cycle is a bridge. This means that a bridge has at least one
articulation point at its end, although it is not necessary that the
A
B
articulation point is linked in a bridge.
C

REPRESENTATION OF GRAPHS
There are two common ways of storing graphs in computers
memory. They are:
Sequential representation by using an adjacency matrix
Linked representation by using an adjacency list that stores the
neighbors of a node using a linked list

Adjacency Matrix
Representation
An adjacency matrix is used to represent which nodes are
adjacent to one another. By definition, we have learnt that,
two nodes are said to be adjacent if there is an edge
connecting them.
In a directed graph G, if node v is adjacent to node u, then
surely there is an edge from u to v. That is, if v is adjacent to
u, we can get from u to v by traversing one edge. For any
graph G having n nodes, the adjacency matrix will have
dimensions of n X n.
In an adjacency matrix, the rows and columns are labeled by
graph vertices. An entry aij in the adjacency matrix will
1
if v is adjacent to v , that is there is an edge (v , v )
contain
1,
if
vertices
vi
and vj are adjacent to each other.
aij
0
otherwise
However, if the nodes
are not adjacent, aij will be set to zero.
i

Since an adjacency matrix contains only 0s and 1s, it is called a

bit matrix or a Boolean matrix. The entries in the matrix depend
on the ordering of the nodes in G. therefore, a change in the
order of nodes will result in a different adjacency matrix.

Adjacency Matrix
Representation

Adjacency Matrix
Representation

Adjacency Matrix
Representation
From adjacency matrix A1, we have learnt that an entry 1 in
the ith row and jth column means that there exists a path of
length 1 from vi to vj. Now consider, A2, A3 and A4
aij 2 = aik akj
Any entry aij = 1 if aik = akj = 1. That is, if there is an edge (vi,
vk) and (vk, vj). This implies that there is a path from vi to vj of
length 2.
Similarly, every entry in the ith row and jth column of A3 gives
the number of paths of length 3 from node vi to vj.
In general terms, we can conclude that every entry in the ith
row and jth column of An (where n is the number of nodes in
the graph) gives the number of paths of length n from node vi

Adjacency List
The adjacency list is another way in which graphs can be
represented in computers memory. This structure consists of a
list of all nodes in G. Furthermore, every node is in turn linked to
its own list that contains the names of all other nodes that are
adjacent to itself.
The key advantage of using an adjacency list includes:

It is easy to follow, and clearly shows the adjacent nodes of a

particular node

It is often used for storing graphs that have a small to

moderate number of edges. That is an Adjacency list is
preferred for representing sparse graphs in computers
memory; otherwise, an adjacency matrix is a good choice.
Adding new nodes in G is easy and straightforward when G is
represented using an Adjacency list. Adding new nodes in an

Adjacency List
A

X
A

Graph G and its adjacency list

For a directed graph, the sum of lengths of all adjacency lists
is equal to the number of edges in G. However, for an
undirected graph, the sum of lengths of all adjacency lists is
equal to twice the number of edges in G because an edge (u,
v) means an edge from node u to v as well as an edge v to u.
The adjacency list can also be modified to store weighted
graphs.

Adjacency List

X
D

X
E X
X

Graph Traversal Algorithms

By traversing a graph, we mean the method of
examining the nodes and edges of the graph. There
are two standard methods of graph traversal which we
will discuss in this section. These two methods are Breadth first search
Depth first search
While breadth first search will use a queue as an
auxiliary data structure to store nodes for further
processing, the depth-first search scheme will use a
stack. But both these algorithms will make use of a
variable STATUS. During the execution of the
algorithm, every node in the graph will have the
variable STATUS set to 1, 2 or depending on its current
state. Table I shows the value of status and its

Graph Traversal Algorithms

STATUS
1

STATE OF THE
NODE

DESCRIPTION

Ready

The initial state of the node N

Waiting

Node N is placed on the queue or

stack and waiting to be
processed

Processed

Node N has been completely

processed

Breadth First Search

Breadth-first search (BFS) is a graph search algorithm
that begins at the root node and explores all the
neighboring nodes. Then for each of those nearest
nodes, the algorithm explores their unexplored
neighbor nodes, and so on, until it finds the goal.
That is, we start examining the node A and then all
the neighbors of A are examined. In the next step we
examine the neighbors of neighbors of A, so on and
so forth

Breadth First Search

Algorithm for breadth-first search in a graph G beginning at a starting node A
Step 1: SET STATUS = 1 (ready state) for each node in G.
Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4:
Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5:
Enqueue all the neighbors of N that are in the ready state
(whose STATUS =
1) and set their STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT

Example: Consider the graph G given below. The

adjacency list of G is also given. Assume that G
represents the daily flights between different cities and
we want to fly from city A to I with minimum stops.
That is, find the minimum path P from A to I given that
every edge has length = 1.

Breadth First Search

A

Adjacency Lists
B

a)Initially add A to QUEUE and add NULL

to ORIG, so
QUEUE = A
FRONT = 1
REAR = 1

ORIG = \0

A: B, C, D
B: E
C: B, G
D: C, G
E: C, F
F: C, H
G: F, H, I
H: E, I
I: F

Breadth First Search

Dequeue a node by setting FRONT = FRONT + 1 (remove the
FRONT element of QUEUE) and enqueue the neighbors of A. Also
add A as the ORIG of its neighbors, so
FRONT = 2
REAR = 4

QUEUE = A B C D
ORIG = \0 A A A

Dequeue a node by setting FRONT = FRONT + 1 and enqueue

the neighbors of B. Also add B as the ORIG of its neighbors, so
FRONT = 3
REAR = 5

QUEUE = A B C D E
ORIG = \0 A A A B

Dequeue a node by setting FRONT = FRONT + 1 and enqueue the

neighbors of C. Also add C as the ORIG of its neighbors. Note that
C has two neighbors B and G. Since B has already been added to
the queue and it is not in the Ready state, we will not add B and
add only G, so
FRONT = 4
REAR = 6

QUEUE = A B C D E G
ORIG = \0 A A A B C

Breadth First Search

Dequeue a node by setting FRONT = FRONT + 1 and
enqueue the neighbors of D. Also add D as the ORIG of
its neighbors. Note that D has two neighbors C and G.
Since both of them have already been added to the
queue and they are not in the Ready state, we will not
add them again, so
FRONT = 5
REAR = 6

QUEUE = A B C D E G
ORIG = \0 A A A B C

Dequeue a node by setting FRONT = FRONT + 1 and

enqueue the neighbors of E. Also add E as the ORIG of
its neighbors. Note that E has two neighbors C and F.
Since C has already been added to the queue and it is
not in the Ready state, we will not add C and add only F,
so

Breadth First Search

FRONT = 6
REAR = 7

QUEUE = A B C D E G F
ORIG = \0 A A A B C G

Dequeue a node by setting FRONT = FRONT + 1 and

enqueue the neighbors of G. Also add G as the ORIG of
its neighbors. Note that G has three neighbors F, H and
I.
FRONT = 7
REAR = 10

QUEUE = A B C D E G F H I
ORIG = \0 A A A B C G G G

Since I is our final destination, we stop the execution of

this algorithm as soon as it is encountered and added to
the QUEUE. Now backtrack from I using ORIG to find the
minimum path P. thus, we have P as A -> C -> G -> I.

Depth First Search Algorithm

The Depth First Search algorithm progresses by
expanding the starting node of G and thus going deeper
and deeper until a goal node is found, or until a node
that has no children is encountered. When a dead- end
is reached, the algorithm backtracks, returning to the
most recent node that has not been completely
explored.
In other words, the Depth- First Search algorithm begins
at a starting node A which becomes the current node.
Then it examines each node N along a path P which
begins at A. That is, we process a neighbor of A, then a
neighbor of neighbor of A and so on. During the
execution of the algorithm, if we reach a path that has a
node N that has already been processed, then we

Depth First Search Algorithm

Algorithm for depth-first search in a graph G beginning at a starting node A

Step 1: SET STATUS = 1 (ready state) for each node in G.
Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting
state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4:
Pop the top node N. Process it and set its STATUS = 3
(processed state).
Step 5:
Push on to the stack all the neighbors of N that are in
the ready state (whose STATUS = 1) and set their STATUS = 2
(waiting
state)
[END OF LOOP]
Step 6: EXIT

Depth First Search Algorithm

Example: Consider the graph G given below. The
adjacency list of G is also given. Suppose we want to
print all nodes that can be reached from the node H
(including H itself). One alternative is to use a DepthFirst Search of G starting at node H. the procedure can
be explained as below.
A
Adjacency Lists

A: B, C, D
B: E
C: B, G
D: C, G
E: C, F
F: C, H
G: F, H, I
H: E, I
I: F

Depth First Search Algorithm

a)Push H on to the stack

STACK: H

Pop and Print the top element of the STACK, that is, H. Push all the
neighbors of H on to the stack that are in the ready state. The
STACK now becomes:
STACK: E, I

Pop and Print the top element of the STACK, that is, I. Push all the
neighbors of I on to the stack that are in the ready state. The
STACK now becomes:
PRINT: I

STACK: E, F

Pop and Print the top element of the STACK, that is, F. Push all the
neighbors of F on to the stack that are in the ready state. (Note F
has two neighbors C and H. but only C will be added as H is not in
the ready state). The STACK now becomes:
PRINT: F
STACK: E, C
Pop and Print the top element of the STACK, that is, C. Push all
the neighbors of C on to the stack that are in the ready state. The
STACK now becomes:

Depth First Search Algorithm

PRINT: C

STACK: E, B, G

Pop and Print the top element of the STACK, that is, G. Push all the
neighbors of G on to the stack that are in the ready state. Since
there are no neighbors of G that are in the ready state no push
operation is performed. The STACK now becomes:
PRINT G:

STACK: E, B

Pop and Print the top element of the STACK, that is, B. Push all the
neighbors of B on to the stack that are in the ready state. Since
there are no neighbors of B that are in the ready state no Push
operation is performed. The STACK now becomes:
PRINT e:

STACK: E

Pop and Print the top element of the STACK, that is, E. Push all the
neighbors of E on to the stack that are in the ready state. Since there
are no neighbors of E that are in the ready state no Push operation is
performed. The STACK now becomes empty: PRINT: E. Since the
STACK is now empty, the depth-first search of G starting at node H is
complete and the nodes which were printed are-H, I, F, C, G, B E.
These are the nodes which are reachable from the node H.

Topological Sorting

Topological sort of a directed acyclic graph (DAG) G, is defined

as a linear ordering of its nodes in which each node comes
before all nodes to which it has outbound edges. Every DAG has
one or more number of topological sorts.
That is, atopological sort of a directed acyclic graph (DAG)G is
an ordering of the vertices ofG such that if Gcontains an edge
(u, v), then u appears before v in the ordering.
Note that topological sort is possible only on directed acyclic
graphs that do not have any cycle. For a DAG that contains
cycle, no linear ordering of its vertices is possible.
In simple words, a topological ordering of a DAG G, is an
ordering of its vertices such that any directed path in
G,traverses vertices in increasing order.
Topological sorting is widely used in scheduling applications, jobs
or tasks. The jobs that have to be completed are represented by
nodes, and there is an edge from node u to v if job u must be
completed before job v can be started. A topological sort of such
a graph gives an order in which the given jobs must be

Topological Sorting
Algorithm to find a Topological Sort T of a Directed Acyclic Graph, G
Step 1:
Step 2:
Step 3:
Step 4:
FRONT +
Step 5:

Find the indegree INDEG(N) of every node in the graph

Enqueue all the nodes with a zero in-degree
Repeat Steps 4 and 5 until the QUEUE is empty
Remove the front node N of the QUEUE by setting FRONT =
1
Repeat for each neighbor M of node N:
a) Delete the edge from N to M by setting INDEG(M) =
INDEG(M) 1
b) IF INDEG(M) = 0, then Enqueue M, that is, add M to the
rear of the queue
[END OF INNER LOOP]
[END OF LOOP]
Step 6: Exit