SR

M SCIENCE AND
INSTITUTE OF
TECHNOLOGY,
CHENNAI.
18CSC201J
DATA STRUCTURES AND ALGORITHMS
Unit- V
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

• GRAPH TERMINOLOGY
• GRAPH TRAVERSAL
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

• A graph - an abstract data structure that is used to

implement the graph concept from mathematics.
• 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

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-way roads, shipping routes, etc.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

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 B C

Fig:a
Definition D E
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

A graph can be directed (Fig a)or undirected (Fig b).

A B C

Fig:a
D E

A B C

Fig:bDefinition
D E
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

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 regular graph with vertices of
degree k is called a k‑regular graph or regular
graph of degree k.

1 regular graph 2 regular graph

O regular graph
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
• 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
• 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, where n is the number of nodes
in G.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
• 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

(a) Multi-graph (b) Tree (c) Weighted Graph

3 4
e1
A B C
e4 A B C
A B
e2
2
e3
7 1

C e6 D E F
e5 e7 D B
3
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Terminologies in 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 out-degree 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
• 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
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Transitive Closure of a Directed Graph:
• It is same as the adjacency list in graph terminology.
• It is stored as a matrix T.

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 pair 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

• A binary relation indicates only whether the node A is connected to

node B, whether node B is connected to node C, etc.
• But once the transitive closure is constructed as shown in Fig.
• we can easily determine in O(1) time whether node E is reachable
from node A or not.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
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
pair 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.

• A binary relation indicates only whether the node A is connected to node B,

whether node B is connected to node C, etc. But once the transitive closure is
constructed as shown in Fig. we can easily determine in O(1) time whether
node E is reachable from node A or not.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Graph Representation:
• There are three common ways of storing graphs in the computer’s
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 multi-list which is an extension of linked
representation.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Adjacency Matrix Representation:

• An adjacency matrix is used to represent which nodes are adjacent to one another.
By definition, two nodes are said to be adjacent if there is an edge connecting
them.
• In this representation, graph can be represented using a matrix of size V*V.
• No matter how few edges the graph has, the matrix has O(n^2) in memory.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Adjacency List Representation:

• An adjacency list is another way in which graphs can be represented in the
computer’s 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 it.
• The key advantages of using an adjacency list are:
• 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
the computer’s 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 matrix is a
difficult task, as the size of the matrix needs to be changed and existing
nodes may have to be reordered.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Adjacency List Representation:

 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Adjacency Multi-list Representation:
• Graphs can also be represented using multi-lists which can be said
to be modified version of adjacency lists.
• Adjacency multi-list is an edge-based rather than a vertex-based
representation of graphs.
• A multi-list representation basically consists of two parts—
• a directory of nodes’ information and a set of linked lists storing
information about edges.
• While there is a single entry for each node in the node directory,
every node, on the other hand, appears in two adjacency lists
(one for the node at each end of the edge).
• For example, the directory entry for node i points to the
adjacency list for node i. This means that the nodes are shared
among several lists.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

In a multi-list representation, the information about an edge (vi, vj) of

an undirected graph can be stored using the following attributes:
M: A single bit field to indicate whether the edge has been examined
or not.
vi: A vertex in the graph that is connected to vertex vj by an edge.
vj: A vertex in the graph that is connected to vertex vi by an edge.
Link i for vi: A link that points to another node that has an edge
incident on vi.
Link j for vi: A link that points to another node that has an edge
incident on vj.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Adjacency Multi-list Representation:

Consider the undirected graph given in Fig. The adjacency multi-list for the graph can be
given as:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
GRAPH TRAVERSAL ALGORITHMS:
• This technique is used for searching a vertex in a graph.
• It is also used to decide the order of vertices to be visit in the search
process.
• There are two standard methods of graph traversal:
1. Breadth-first search
2. Depth-first search
• While breadth-first search uses a queue as an auxiliary data
structure to store nodes for further processing.
• The depth-first search scheme uses a stack.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Breadth-First Search Algorithm:

• It 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.
• This technique is used for searching a vertex in a graph.
• It produces a spanning tree as a final result.
• Spanning tree is a graph without any loops.
• Here we use Queue data structure with maximum size of total
number of vertices in the graph.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Breadth-First Search Algorithm:

STEPS:
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
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Breadth-First Search Algorithm:
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Features of Breadth-First Search Algorithm:
• Space complexity
• In the breadth-first search algorithm, all the nodes at a particular level must
be saved until their child nodes in the next level have been generated.
• The space complexity is therefore proportional to the number of nodes at
the deepest level of the graph. Given a graph with branching factor b
(number of children at each node) and depth d, the asymptotic space
complexity is the number of nodes at the deepest level O(bd).
• Time complexity
• In the worst case, breadth-first search has to traverse through all paths to all
possible nodes, thus the time complexity of this algorithm asymptotically
approaches O(bd).
• However, the time complexity can also be expressed as O( | E | + | V | ),
since every vertex and every edge will be explored in the worst case.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

• Completeness
• Breadth-first search is said to be a complete algorithm because
if there is a solution, breadth-first search will find it regardless
of the kind of graph.
• But in case of an infinite graph where there is no possible
solution, it will diverge.
• Optimality
• Breadth-first search is optimal for a graph that has edges of
equal length, since it always returns the result with the fewest
edges between the start node and the goal node.
• But generally, in real-world applications, we have weighted
graphs that have costs associated with each edge, so the goal
next to the start does not have to be the cheapest goal available.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Applications of Breadth-First Search Algorithm:

• Breadth-first search can be used to solve many problems such
as:
• Finding all connected components in a graph G.
• Finding all nodes within an individual connected component.
• Finding the shortest path between two nodes, u and v, of an
unweighted graph.
• Finding the shortest path between two nodes, u and v, of a
weighted graph.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

• The depth-first search algorithm progresses by expanding the
starting node of G and then going deeper and deeper until the 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, depth-first search 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.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

• During the execution of the algorithm, if we reach a path that has
a node N that has already been processed, then we backtrack to
the current node. Otherwise, the unvisited (unprocessed) node
becomes the current node.
• This technique is used for searching a vertex in a graph.
• It produces a spanning tree as a final result.
• Spanning tree is a graph without any loops.
• Here we use Stack data structure with maximum size of total
number of vertices in the graph.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

Consider the graph and find the spanning tree,
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Depth-first Search Algorithm:

 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.
Features of Depth-First Search Algorithm
Space complexity The space complexity of a depth-first search is
lower than that of a breadthfirst
search.
Time complexity The time complexity of a depth-first search is
proportional to the number of
vertices plus the number of edges in the graphs that are traversed. The
time complexity can be
given as (O(|V| + |E|)).
Completeness Depth-first search is said to be a complete algorithm. If
there is a solution, depthfirst search will find it regardless of the kind
of graph. But in case of an infinite graph, where there is no possible
solution, it will diverge.
 SR
M AND TECHNOLOGY,
INSTITUTE OF SCIENCE
CHENNAI.

Applications of Depth-First Search Algorithm

Depth-first search is useful for:
• Finding a path between two specified nodes, u and v, of an
unweighted graph.
• Finding a path between two specified nodes, u and v, of a weighted
graph.
• Finding whether a graph is connected or not.
• Computing the spanning tree of a connected graph.
References:
ReemaThareja, “Data Structures Using C”,
Oxford Higher Education , First Edition,
2011