CSF102: Data Structures

Session: 2025

B. Tech 2nd Semester

Course Coordinator
Mr. Mohd Khalid
Assistant Professor, School of Computing

Course Instructor
Dr. Madhu Sharma
Assistant Professor, School of Computing
 DATA STRUCTURE
Unit 4: Graph (7 L)
• Graphs:
• Introduction to Graph and their Terminologies,
• Types of Graph,
• Representations of Graph,
• Graph traversal algorithms,
• Topological Sorting,
• Minimum Spanning Tree,
• Shortest Path Algorithms:
• Single Source Shortest Path like Bellman-Ford, Dijkstra and All Pair Shortest Path like Floyd-Warshall.
Introduction to Graph
 Types of Graph
• Null Graph:
• A graph is known as null graph if there are no edges in the graph.
 Types of Graph
• Trivial Graph
• Graph having only a single vertex, it is the smallest
graph possible.

• Undirected Graph
• A graph in which edges do not have any direction. That
is the nodes are unordered pairs in the definition of
every edge.

• Directed Graph
• A graph in which edge has direction. That is the nodes
are ordered pairs in the definition of every edge.
 Types of Graph
• Connected Graph
• The graph in which from one node we
can visit any other node in the graph is
known as a connected graph.

• Disconnected Graph
• The graph in which at least one node is
not reachable from a node is known as a
disconnected graph.
 Types of Graph
• Regular Graph
• The graph in which the degree of every
vertex is equal to the other vertices of
the graph.

• Let the degree of each vertex be K then

the graph is called K-regular.

• Complete Graph
• The graph in which from each node
there is an edge to each other node.
 Types of Graph
• Cycle Graph
• The graph in which the graph is a cycle in itself, the degree of
each vertex is 2..

• Cyclic Graph
• A graph containing at least one cycle is known as a Cyclic
graph.

• Directed Acyclic Graph

• A Directed Graph that does not contain any cycle.

• Bipartite Graph
• A graph in which vertex can be divided into two sets such
that vertex in each set does not contain any edge between
them..
 Types of Graph
• Tree v/s Graph

• Trees are the restricted types of graphs, just with some more rules. Every tree will always be a graph but not all
graphs will be trees.

• Linked List, Trees, and Heaps all are special cases of graphs.
 representation of Graph
• There are two ways to store a graph:

• Adjacency Matrix:
• the graph is stored in the form of the 2D matrix where
rows and column denote vertices.

• Each entry in the matrix represents the weight of the edge

between those vertices.

• Adjacency List:
• This graph is represented as a collection of linked lists.

• There is an array of pointer which points to the edges

connected to that vertex.
 representation of Graph
• Comparison between Adjacency list and Adjacency matrix
• When the graph contains a large number of edges then it is good to store it as a matrix because only some entries
in the matrix will be empty.

• An algorithm such as Prim’s and Dijkstra adjacency matrix is used to have less complexity.

Action Adjacency Matrix Adjacency List

Adding Edge O(1) O(1)

Removing and edge O(1) O(N)

Initializing O(N*N) O(N)

 Graph Traversal Algorithm
• Traversing the graph means examining all the nodes and vertices of the graph. There are two standard methods
by using which, we can traverse the graphs. Lets discuss each one of them in detail.
• Breadth First Search

• Depth First Search

 Breadth First Search
• Breadth First Search
• Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a tree.

• The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again.

• To avoid processing a node more than once, we use a boolean visited array.

• For simplicity, it is assumed that all vertices are reachable from the starting vertex.
 Breadth First Search
• Breadth First Search
• For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look
for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will
be processed again and it will become a non-terminating process. A Breadth First Traversal of the following
graph is 2, 0, 3, 1.
 Breadth First Search
Breadth First Search // Loop until the queue is empty

BFS(graph, start_node): while queue is not empty:

// Initialize an empty queue to store nodes to be visited // Dequeue a node from the queue
queue = empty Queue current_node = dequeue from queue

print current_node
// Initialize a set to keep track of visited nodes
// Explore all adjacent nodes of the current node
visited = empty Set
for each neighbor_node of current_node:

// Mark the start node as visited and enqueue it if neighbor_node is not in visited:

mark start_node as visited mark neighbor_node as visited

enqueue start_node into queue enqueue neighbor_node into queue
 Breadth First Search
• Breadth First Search Example
Breadth First Search
Breadth First Search
Breadth First Search
Breadth First Search
 Breadth First Search
• Breadth First Search

• Note that the above traverses only the vertices reachable from a given source vertex.

• All the vertices may not be reachable from a given vertex (example Disconnected graph).

• Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.
 Depth First Search
• Depth First Search

• It is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going
ahead, if possible, else by backtracking.

• Here, the word backtrack means that when you are moving forward and there are no more nodes along the current path,
you move backwards on the same path to find nodes to traverse. All the nodes will be visited on the current path till all
the unvisited nodes have been traversed after which the next path will be selected.

• This recursive nature of DFS can be implemented using stacks. The basic idea is as follows:

• Pick a starting node and push all its adjacent nodes into a stack.

• Pop a node from stack to select the next node to visit and push all its adjacent nodes into a stack.

• Repeat this process until the stack is empty. However, ensure that the nodes that are visited are marked. This will
prevent you from visiting the same node more than once. If you do not mark the nodes that are visited and you
visit the same node more than once, you may end up in an infinite loop.
 Depth First Search
• Depth First Search
• DFS-iterative (G, s): //Where G is graph and s is source
vertex
• let S be stack
• S.push( s ) //Inserting s in stack
• mark s as visited.
• while ( S is not empty):
• //Pop a vertex from stack to visit next
• v = S.top( )
• S.pop( )
• //Push all the neighbours of v in stack that are not visited
• for all neighbours w of v in Graph G:
• if w is not visited :
• S.push( w )
• mark w as visited Time complexity = O (V+E)
•
 Topological SoRting
• Topological sorting for Directed Acyclic Graph (DAG) is a linear
ordering of vertices such that for every directed edge u v, 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 following 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 incoming edges).
 Spanning Tree
• A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have
many spanning trees;
• If a graph is a complete graph with n vertices, then total number of spanning trees is n^(n-2) where n is the
number of nodes in the graph. For instance the complete graph on four vertices there are 16 spanning tree.
 Minimum Spanning Tree
• Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the
vertices together.

• A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, undirected graph is a
spanning tree with a weight less than or equal to the weight of every other spanning tree.

• The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

• How many edges does a minimum spanning tree has?

• A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.
• What are the applications of the Minimum Spanning Tree?
• telephone, electrical, hydraulic, TV cable, computer, road
• traveling salesperson problem
• There are two famous algorithm to find the minimum spanning tree:
1. Kruskal’s Algorithm

2. Prim Algorithm
 Kruskal’s algorithm
• Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree.

• Kruskal's algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the
growing spanning tree.
1. Sort all the edges in non-decreasing order of their weight.

2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else,
discard it.

3. Repeat step#2 until there are (V-1) edges in the spanning tree.
 Kruskal’s algorithm
1. Pick edge 7-6: No cycle is 2. Pick edge 8-2: No cycle is 3. Pick edge 6-5: No cycle is
formed, include it. formed, include it. formed, include it.

4. Pick edge 0-1: No cycle is 5. Pick edge 2-5: No cycle is 6. Pick edge 8-6: Since including
formed, include it. formed, include it. this edge results in the cycle,
discard it.
7. Pick edge 2-3: No cycle is
formed, include it.
 Kruskal’s algorithm
8. Pick edge 7-8: Since including this edge
results in the cycle, discard it. 10. Pick edge 1-2: Since including this edge results
9. Pick edge 0-7: No cycle is formed, include it. in the cycle, discard it.
11. Pick edge 3-4: No cycle is formed, include it.

Since the number of edges included equals (V – 1), the

algorithm stops here.
 Kruskal’s algorithm
• Time Complexity:
• O(ElogE) or O(ElogV).

• Sorting of edges takes O(ELogE) time.

• After sorting, we iterate through all edges and apply the find-union algorithm. The find and union operations can take at
most O(LogV) time.

• So overall complexity is O(E LogE + E LogV) time.

• The value of E can be at most O(V2), so O(LogV) is O(LogE) the same.

• Therefore, the overall time complexity is O(ElogE) or O(ElogV)

 Prim’s algorithm
• Prim’s Algorithm also use Greedy approach to find the minimum spanning tree. In Prim’s Algorithm we grow the
spanning tree from a starting position. Unlike an edge in Kruskal's, we add vertex to the growing spanning tree in Prim's.

• Algorithm Steps:

• Maintain two disjoint sets of vertices. One containing vertices that are in the growing spanning tree and other that
are not in the growing spanning tree.

• Select the cheapest vertex that is connected to the growing spanning tree and is not in the growing spanning tree and
add it into the growing spanning tree. This can be done using Priority Queues. Insert the vertices, that are connected
to growing spanning tree, into the Priority Queue.

• Check for cycles. To do that, mark the nodes which have been already selected and insert only those nodes in the
Priority Queue that are not marked.
 Prim’s algorithm

• Algorithm Complexity:
• The time complexity of the Prim’s Algorithm is O((V+E) log V) because each vertex is inserted in
the priority queue only once and insertion in priority queue take logarithmic time.
 shortest path problem
• The shortest path problem is about finding a path between vertices in a graph such that the total sum of the edges
weights is minimum.
• The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following
variations:
• The single-source shortest path problem, in which we have to find shortest paths from a source vertex v to all
other vertices in the graph.
• The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the
directed graph to a single destination vertex v. This can be reduced to the single-source shortest path problem by
reversing the arcs in the directed graph.
• The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices v, v' in
the graph.

• Dijkstra's algorithm solves the single-source shortest path problem with non-negative edge weight.
• Bellman–Ford algorithm solves the single-source problem if edge weights may be negative.
• Floyd–Warshall algorithm solves all pairs shortest paths.
 Dijkstra’s algorithm
• Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph.

• Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree.

• Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root.

• We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included
in shortest path tree.

• At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum
distance from the source.
 Dijkstra’s algorithm
• Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single source vertex to all other
vertices in the given graph.

• Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance
from source is calculated and finalized. Initially, this set is empty.

2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for
the source vertex so that it is picked first.

3) While sptSet doesn’t include all vertices

….a) Pick a vertex u which is not there in sptSet and has minimum distance value.

….b) Include u to sptSet.

….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For
every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of
v, then update the distance value of v.
 Dijkstra’s algorithm
• Let us understand with the following example:

• The set sptSet is initially empty and distances assigned to vertices

are {0, INF, INF, INF, INF, INF, INF, INF} where INF indicates
infinite.

• Now pick the vertex with minimum distance value.

• The vertex 0 is picked, include it in sptSet. So sptSet becomes {0}.

• After including 0 to sptSet, update distance values of its adjacent

vertices.

• Adjacent vertices of 0 are 1 and 7. The distance values of 1 and 7

are updated as 4 and 8.

• Following subgraph shows vertices and their distance values, only

the vertices with finite distance values are shown. The vertices
included in SPT are shown in green colour.
 Dijkstra’s algorithm
S2: Pick the vertex with minimum distance value and
not already included in SPT (not in sptSET). The vertex 1
is picked and added to sptSet. So sptSet now becomes
{0, 1}. Update the distance values of adjacent vertices
of 1. The distance value of vertex 2 becomes 12.
 Dijkstra’s algorithm
S3: Pick the vertex with minimum distance value and
not already included in SPT (not in sptSET). Vertex 7 is
picked. So sptSet now becomes {0, 1, 7}. Update the
distance values of adjacent vertices of 7. The distance
value of vertex 6 and 8 becomes finite (15 and 9
respectively).
 Dijkstra’s algorithm
S4: Pick the vertex with minimum distance value and
not already included in SPT (not in sptSET). Vertex 6 is
picked. So sptSet now becomes {0, 1, 7, 6}. Update the
distance values of adjacent vertices of 6. The distance
value of vertex 5 and 8 are updated.
 Dijkstra’s algorithm
S5: We repeat the above steps until sptSet does include
all vertices of given graph. Finally, we get the following
Shortest Path Tree (SPT).

• Complexity:
• Time Complexity of the implementation is O(V^2)
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm
 Bellman–Ford algorithm
algorithm
• Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may
contain negative weight edges.

• Algorithm
1) This step initializes distances from the source to all vertices as infinite and distance to the source itself as 0. Create an array dist[] of size |V|
with all values as infinite except dist[src] where src is source vertex.

2) This step calculates shortest distances. Do following |V|-1 times where |V| is the number of vertices in given graph.

…..a) Do following for each edge u-v

………………If dist[v] > dist[u] + weight of edge uv, then update dist[v]

………………….dist[v] = dist[u] + weight of edge uv

3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-v

……If dist[v] > dist[u] + weight of edge uv, then “Graph contains negative weight cycle”

The idea of step 3 is, step 2 guarantees the shortest distances if the graph doesn’t contain a negative weight cycle. If we iterate through all edges
one more time and get a shorter path for any vertex, then there is a negative weight cycle
 Bellman–Ford algorithm
algorithm
• Example
• Step1:

• Let us understand the algorithm with following example graph. The images are taken from this source.

• Let the given source vertex be 0. Initialize all distances as infinite, except the distance to the source itself. Total number of vertices in the graph is 5,
so all edges must be processed 4 times.
 Bellman–Ford algorithm
algorithm
• Step2:
• Let all edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). We get the following
distances when all edges are processed the first time. The first row shows initial distances. The second row shows distances when
edges (B, E), (D, B), (B, D) and (A, B) are processed. The third row shows distances when (A, C) is processed. The fourth row
shows when (D, C), (B, C) and (E, D) are processed.
 Bellman–Ford algorithm
algorithm
• Step3:
• The first iteration guarantees to give all shortest paths which are at most 1 edge long. We get the following distances when all edges
are processed second time (The last row shows final values).

• The second iteration guarantees to give all shortest paths which are at most 2 edges long. The algorithm processes all edges 2 more
times. The distances are minimized after the second iteration, so third and fourth iterations don’t update the distances.
 Bellman–Ford algorithm
algorithm
• Note:

1) Negative weights are found in various applications of graphs. For example, instead of paying cost for a path, we may
get some advantage if we follow the path.

2) Bellman-Ford works better (better than Dijksra’s) for distributed systems. Unlike Dijkstra’s where we need to find
the minimum value of all vertices, in Bellman-Ford, edges are considered one by one.
 FLOYD Warshals algorithm
We initialize the solution matrix same as the input graph matrix as a first step. Then we update the solution matrix by
considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and updates all shortest paths
which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an
intermediate vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every pair (i, j) of the
source and destination vertices respectively, there are two possible cases.

1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.

2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j] if dist[i][j]
> dist[i][k] + dist[k][j]

The following figure shows the above optimal substructure property in the all-pairs shortest path problem.
 FLOYD Warshals algorithm

Example: Note that the value of graph[i][j] is 0 if i is equal to j

And graph[i][j] is INF (infinite) if there is no edge from
Input: vertex i to j.
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF}, Output:
{INF, INF, 0, 1}, Shortest distance matrix
{INF, INF, INF, 0} } 0 5 8 9
which represents the following graph INF 0 3 4
INF INF 0 1
INF INF INF 0
 REFERENCES
1. Presentation for use with the textbook, Algorithm Design and Applications, by M. T.
Goodrich and R. Tamassia, Wiley, 2015
2. Reema thareja
3. Naveen Garg
4. Geeks for geeks