BCA-MAWT 4th Semester

Design and Analysis of Algorithm (BMT40106) (T)

Academic Session - 2025-2026 EVEN

Study Material

(Design and analysis of algorithm and BCA47111)

Table of contents
Module 4 - Graph and Tree Algorithms

1. Graph traversal algorithms

2. Depth First Search (DFS)

3. Breadth First Search (BFS)

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

GRAPH ALGORITHMS

• Graph G is a pair (V, E), where V is a finite set (set of vertices) and E is a finite set of pairs from V
(set of edges). We will often denote n := |V|, m := |E|.

• Graph G can be directed, if E consists of ordered pairs, or undirected, if E consists of unordered pairs.
If (u, v)  E, then vertices u, and v are adjacent.

• We can assign weight function to the edges: wG(e) is a weight of edge e  E. The graph which has
such function assigned is called weighted.

• Degree of a vertex v is the number of vertices u for which (u, v)  E (denote deg(v)). The number of
incoming edges to a vertex v is called in–degree of the vertex (denote indeg(v)). The number of
outgoing edges from a vertex is called out-degree (denote outdeg(v)).

Representation of Graphs:

Consider graph G = (V, E), where V= {v1, v2,….,vn}.

Adjacency matrix represents the graph as an n x n matrix A = (ai,j), where
 1,
a i, j =  if (vi , vj ) E,

 0, otherwise

The matrix is symmetric in case of undirected graph, while it may be asymmetric if the
graph is directed.
We may consider various modifications. For example for weighted graphs, we may
have
 w (vi, vj ),
if (vi , vj )  E, otherwise,
a i, j = 
 default,

Where default is some sensible value based on the meaning of the weight function (for
example, if weight function represents length, then default can be , meaning value larger
than any other value).

Adjacency List: An array Adj [1 ............... n] of pointers where for 1 < v < n, Adj [v] points
to a linked list containing the vertices which are adjacent to v (i.e. the vertices that can be
reached from v by a single edge). If the edges have weights then these weights may also be
stored in the linked list elements.

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Paths and Cycles:

A path is a sequence of vertices (v1, v2,............. , vk), where for all i, (vi, vi+1)  E. A path is
simple if all vertices in the path are distinct.

A (simple) cycle is a sequence of vertices (v1, v2,............ , vk, vk+1 = v1), where
for all i, (vi, vi+1)  E and all vertices in the cycle are distinct except pair v1,
vk+1.

Subgraphs and Spanning Trees:

Subgraphs: A graph G’ = (V’, E’) is a subgraph of graph G = (V, E) iff V’  V and E’


E.

The undirected graph G is connected, if for every pair of vertices u, v there

exists a path from u to v. If a graph is not connected, the vertices of the graph
can be divided into connected components. Two vertices are in the same
connected component iff they are connected by a path.

Tree is a connected acyclic graph. A spanning tree of a graph G = (V, E)

is a tree that contains all vertices of V and is a subgraph of G. A single graph
can have multiple spanning trees.

Lemma 1: Let T be a spanning tree of a graph G. Then

1. Any two vertices in T are connected by a unique simple path.
2. If any edge is removed from T, then T becomesdisconnected.
3. If we add any edge into T, then the new graph will contain acycle.
4. Number of edges in T is n-1.

Techniques for graphs:

Given a graph G = (V, E) and a vertex V in V (G) traversing can be done in twoways.

1. Depth first search

2. Breadth first search
3. D-search (Depth Search)

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Depth first search:

With depth first search, the start state is chosen to begin, then some successor of the start
state, then some successor of that state, then some successor of that and so on, trying to reach
a goal state.

If depth first search reaches a state S without successors, or if all the successors of a state S
have been chosen (visited) and a goal state has not get been found, then it “backs up” that
means it goes to the immediately previous state or predecessor formally, the state whose
successor was ‘S’ originally.

For example consider the figure. The circled letters are state and arrows are branches.
D

A
E

ST A RT J
S B

H G GOA L

C F
K

Suppose S is the start and G is the only goal state. Depth first search will first visit S, then
A then D. But D has no successors, so we must back up to A and try its second successor,
E. But this doesn’t have any successors either, so we back up to A again. But now we have
tried all the successors of A and haven’t found the goal state G so we must back to ‘S’. Now
‘S’ has a second successor, B. But B has no successors, so we back up to S again and choose
its third successor, C. C has one successor, F. The first successor of F is H, and the first of
H is J. J doesn’t have any successors, so we back up to H and try its second successor. And
that’s G, the only goal state. So the solution path to the goal is S, C, F, H and G and the
states considered were in order S, A, D, E, B, C, F, H, J, G.

Disadvantages:

1. It works very fine when search graphs are trees or lattices, but can get struck in an infinite loop
on graphs. This is because depth first search can travel around a cycle in the graph forever.

To eliminate this keep a list of states previously visited, and never permit search
to return to any of them.

2. One more problem is that, the state space tree may be of infinite depth, to prevent consideration
of paths that are too long, a maximum is often placed on the depth of nodes to be expanded, and
any node at that depth is treated as if it had no successors.

3. We cannot come up with shortest solution to the problem.

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Time Complexity:
Let n = |V| and e = |E|. Observe that the initialization portion requires  (n) time. Since we
never visit a vertex twice, the number of times we go through the loop is at most n (exactly
n assuming each vertex is reachable from the source). As, each vertex is visited at most once.
At each vertex visited, we scan its adjacency list once. Thus, each edge is examined at most
twice (once at each endpoint). So the total running time is O (n + e).

Alternatively,

If the average branching factor is assumed as ‘b’ and the depth of the solution as ‘d’, and
maximum depth m ≥ d.

The worst case time complexity is O(bm ) as we explore bm nodes. If many solutions exists
DFS will be likely to find faster than the BFS.

Space Complexity:
We have to store the nodes from root to current leaf and all the unexpanded siblings of
each node on path. So, We need to store bm nodes.

Breadth first search:

Given an graph G = (V, E), breadth-first search starts at some source vertex S and
“discovers" which vertices are reachable from S. Define the distance between a vertex
V and S to be the minimum number of edges on a path from S to V. Breadth-first search
discovers vertices in increasing order of distance, and hence can be used as an algorithm for
computing shortest paths (where the length of a path = number of edges on the path).
Breadth-first search is named because it visits vertices across the entire breadth.

To illustrate this let us consider the following tree:

D

A
E

ST A RT J
S B

H G GOA L

C F
K

Breadth first search finds states level by level. Here we first check all the immediate
successors of the start state. Then all the immediate successors of these, then all the
immediate successors of these, and so on until we find a goal node. Suppose S is the start
state and G is the goal state. In the figure, start state S is at level 0; A, B and C are at level
1; D, e and F at level 2; H and I at level 3; and J, G and K at level 4. So breadth first search,
will consider in order S, A, B, C, D, E, F, H, I, J and G and then stop because it has reached
Department of Computational Sciences
Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Time Complexity:
The running time analysis of BFS is similar to the running time analysis of many graph
traversal algorithms. Let n = |V| and e = |E|. Observe that the initialization portion requires
 (n) time. Since we never visit a vertex twice, the number of times we go through the loop
is at most n (exactly n, assuming each vertex is reachable from the source). So, Running
time is O (n + e) as in DFS. For a directed graph the analysis is essentially the same.

Alternatively,

If the average branching factor is assumed as ‘b’ and the depth of the solution as ‘d’.

In the worst case we will examine 1 + b + b2 + b3 + . . . + bd = (bd + 1 - 1) / (b –1) = O(bd ).

In the average case the last term of the series would be bd / 2. So, the complexity is still
O(bd)

Space Complexity:

Before examining any node at depth d, all of its siblings must be expanded and
stored. So, space requirement is also O(bd).

Depth Search (D-Search):

The exploration of a new node cannot begin until the node currently being explored is fully
explored. D-search like state space search is called LIFO (Last In First Out) search which
uses stack data structure. To illustrate the D-search let us consider the following tree:
D

A
E

ST A RT J
S B

H G GOA L

C F
K

The search order for goal node (G) is as follows: S, A, B, C, F, H, I, J, G.

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Time Complexity:

The time complexity is same as Breadth first search.

Representation of Graphs and Digraphs by Adjacency List:

We will describe two ways of representing digraphs. We can represent undirected graphs
using exactly the same representation, but we will double each edge, representing the
undirected edge {v, w} by the two oppositely directed edges (v, w) and (w, v). Notice that
even though we represent undirected graphs in the same way that we represent digraphs, it
is important to remember that these two classes of objects are mathematically distinct from
one another.

Let G = (V, E) be a digraph with n = |V| and let e = |E|. We will assume that the vertices of
G are indexed {1, 2, , n}.

A v, w =
1 if (v,w) E

otherwise
0

Adjacency List: An array Adj [1 ...............n] of pointers where for 1 < v < n, Adj [v] points
to a linked list containing the vertices which are adjacent to v (i.e. the vertices that can be
reached from v by a single edge). If the edges have weights then these weights may also be
stored in the linked list elements.

1 2 3
1 1 2 3
1 1 1 1

2 3
2 0 0 1

3 1 3 2
0 0

(a) Adjacency Matrix (b) Adjacency List

Adjacency matrix and adjacency list

An adjacency matrix requires Θ (n2) storage and an adjacency list requires Θ (n + e) storage.

Adjacency matrices allow faster access to edge queries (for example, is (u, v)  E) and
adjacency lists allow faster access to enumeration tasks (for example, find all the vertices
adjacent to v).

Depth First and Breadth First Spanning Trees:

BFS and DFS impose a tree (the BFS/DFS tree) along with some auxiliary edges (cross
edges) on the structure of graph. So, we can compute a spanning tree in a graph. The
computed spanning tree is not a minimum spanning tree. Trees are much more structured
objects than graphs. For example, trees break up nicely into subtrees, upon which
subproblems can be solved recursively. For directed graphs the other edges of the graph can
be classified as follows:

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Back edges: (u, v) where v is a (not necessarily proper) ancestor of u in the tree. (Thus, a
self-loop is considered to be a back edge)

Department of Computational Sciences

Brainware University, Kolkata
 Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and
analysis of algorithm(T)

Depth first search and traversal:

Depth first search 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' is
initiated. When a vertex 'u' is reached such that all its 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 depth first search from W. The search terminates when no unvisited vertex can be
reached from any of the visited ones.

Let us consider the following Graph (G):

2 3

4 5 6 7

Gra ph

The adjacency list for G is:

V ert e x

If the depth first is initiated from vertex 1, then the vertices of G are visited in the order: 1,
2, 4, 8, 5, 6, 3, 7. The depth first spanning tree is as follows:

Department of Computational Sciences

Brainware University, Kolkata
Programme Name: BCA (Hons)
Semester: 4th
Course Name : Design and analysis of algorithm(T) Course Code :
BCA47111(T)
Academic Session: 2024-25 EVEN

2 3

4 5 6 7

De pt h F irst Spa nnin g Tre e

The spanning trees obtained using depth first searches are called depth first spanning trees.
The edges rejected in the context of depth first search are called a back edges. Depth first
spanning tree has no cross edges.

Breadth first search and traversal:

Starting at vertex 'V' and marking it as visited, BFS differs from DFS in that all unvisited
vertices adjacent to V are visited next. Then unvisited vertices adjacent to there vertices
are visited and so on. A breadth first search beginning at vertex 1 of the graph would first
visit 1 and then 2 and 3.

2 3

4 5 6 7

Bre a dt h F irst Spa n nin g T re e

Next vertices 4, 5, 6 and 7 will be visited and finally 8. The spanning trees obtained using
BFS are called Breadth first spanning trees. The edges that were rejected in the breadth
first search are called cross edges.

Department of Computational Sciences

Brainware University, Kolkata