Data Structures
Module 6
Graph
Computer Science and Engineering
26-04-2025
Introduction
• Graph
• A group of vertices and edges that are used to connect
these vertices
• A graph can be seen as a cyclic tree, where the vertices
(nodes) maintain any complex relationship among them
instead of having parent child relationship
Cont…
• Definition
• An ordered set G(V, E)
• V(G) represents the set of vertices
• E(G) represents the set of edges which are used to
connect these vertices
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C), (C,E),
(E,D), (D,B), (D,A)) is shown in the following figure.
Cont…
• A graph can be directed or undirected
• In an undirected graph,
• Edges are not associated with the directions with them.
• If an edge exists between vertex A and B then the vertices
can be traversed from B to A as well as A to B
Cont…
• In a directed graph,
• Edges form an ordered pair
• Edges represent a specific path from some vertex A to
another vertex B
• Node A is called initial node while node B is called
terminal node
Graph Terminology
• Path
• The sequence of nodes that are followed in order to reach
some terminal node V from the initial node U
• Simple Path
• If all the nodes of the path are distinct
• Closed Path
• A path will be called as closed path if the initial node is
same as terminal node. A path will be closed path if V0=VN
• Cycle
• The path which has no repeated edges or vertices except
the first and last vertices
Cont…
• Connected Graph
• A connected graph is the one in which some path exists
between every two vertices (u, v) in V. There are no
isolated nodes in connected graph
• Complete Graph
• A complete graph is the one in which every node is
connected with all other nodes
• A complete graph contain n(n-1)/2 edges where n is the
number of nodes in the graph
• Weighted Graph
• In a weighted graph, each edge is assigned with some data
such as length or weight
Cont…
• Digraph
• A digraph is a directed graph in which each edge of the
graph is associated with some direction and the traversing
can be done only in the specified direction
• Loop
• An edge that is associated with the similar end points
• Adjacent Nodes
• If two nodes u and v are connected via an edge e, then the
nodes u and v are called as neighbors or adjacent nodes
• Degree of the Node
• A degree of a node is the number of edges that are
connected with that node
• A node with degree 0 is called as isolated node
Graph Representation
• Graph Representation
• Technique used - to store graph into computer's memory
• Two ways to store Graph
• 1. Sequential Representation
• Adjacency Matrix
• 2. Linked Representation
• Adjacency List
Cont…
• Sequential Representation
• Adjacency Matrix is used to store the mapping
represented by vertices and edges
• In Adjacency Matrix,
• The rows and columns are represented by the graph
vertices
• A graph having n vertices, will have a dimension n x n
• An entry Mij in the Adjacency Matrix representation of an
undirected graph G will be 1 if there exists an edge
between Vi and Vj
Cont…
• Example: Sequential Representation of Undirected graph
Cont…
• Example: Sequential Representation of Directed graph
Cont…
• Example: Sequential Representation of Weighted Directed
graph
Cont…
• Advantages of Adjacency Matrix
• Very convenient and simple to implement
• Adding or removing time of an edge can be done in O(1)
time. Same time is required to check, if there is an edge
between two vertices
• Disadvantages of Adjacency Matrix
• Consumes huge amount of memory for storing big graphs
• Requires huge efforts for adding or removing a vertex
• Adjacency matrix is quite slow for big graphs
Cont…
• Linked Representation
• Adjacency List is used to store the Graph into the
computer's memory
• Adjacency list
• stores the node value and a pointer to the next
adjacent node to the respective node
• If all the adjacent nodes are traversed
• then store the NULL in the pointer field of last node of
the list
• The sum of the lengths of adjacency lists
• equal to the twice of the number of edges present in
an undirected graph
Cont…
• Example: Linked Representation of Undirected graph
Cont…
• Example: Linked Representation of Directed graph
Cont…
• Example: Linked Representation of Weighted Directed graph
Adjacency list of Graph
#include <stdio.h> struct Node* createNode(int v) {
#include struct Node* newNode = (struct Node*)malloc(sizeof(struct
<stdlib.h> Node));
newNode->vertex = v;
struct Node { newNode->next = NULL;
int vertex; return newNode;
struct Node* next; }
};
void addEdgeOneSide(int u, int v) {
#define V 5 struct Node* newNode = createNode(v);
// number of vertices
if (adj[u] == NULL) {
struct Node* adj[V]; adj[u] = newNode;
// adjacency list }
void init() { else {
// initialize list struct Node* temp = adj[u];
for (int i = 0; i < V; while (temp->next != NULL) {
i++) { temp = temp->next;
adj[i] = NULL; }
} temp->next = newNode;
} }
}
Adjacency list of Graph
void printGraph() {
for (int i = 0; i < V; i++) {
struct Node* temp = adj[i];
printf("Vertex %d: ", i);
while (temp != NULL) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("NULL\n"); int main() {
}
} addEdge(0, 1);
addEdge(0, 4);
addEdge(1, 2);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 3);
addEdge(3, 4);
printGraph();
return 0;
}
Cont…
• Advantages of Adjacency List
• Adjacency list requires less amount of memory
• It allows to get the list of adjacent vertices in O(1) time
• Disadvantages of Adjacency List
• It is not easy for adding or removing an edge to/from
adjacent list.
• It does not allow to make an efficient implementation, if
dynamically change of vertices number is required.
Graph Traversal
• Traversing the graph
• Examining all the nodes and vertices of the graph
• Process of visiting and exploring a graph for processing is
called graph traversal.
• visiting and exploring each vertex and edge in a graph
such that all the vertices are explored exactly once
Graph Traversal
Depth First Search Breadth First Search
Breadth First Search (BFS)
• Breadth First Search (BFS)
• Starts traversing the graph from initial node and explores
all the neighboring nodes
• It then selects the nearest node and explore all the
unexplored nodes
• The algorithm follows the same process for each of the
nearest node until it finds the goal
• BFS Algorithm
• Starts with examining the node A and all of its neighbors
• In the next step, the neighbors of the nearest node of A
are explored and process continues in the further steps
• The algorithm explores all neighbors of all the nodes and
ensures that each node is visited exactly once and no
node is visited twice
Cont…
• Depth first search (DFS) algorithm
• Starts with the initial node of the graph G, and then goes
to deeper and deeper until we find the goal node or the
node which has no children
• The algorithm, then backtracks from the dead end
towards the most recent node that is yet to be completely
unexplored
• The data structure which is being used in DFS is Stack
• In DFS,
• The edges that leads to an unvisited node are called
discovery edges
• The edges that leads to an already visited node are called
block edges
DFS: Depth First Search
Cont…
• Depth First Search Complexity
• Time complexity
• O(V + E) when Adjacency List is used
• O(V2) when Adjacency Matrix is used
• Space complexity - O(V)
• Applications
• For finding the path
• To test if the graph is bipartite
• For finding the strongly connected components of a graph
• For detecting cycles in a graph
Cont…
• Time complexity
• O(V + E) when Adjacency List is used
• O(V2) when Adjacency Matrix is used
where V stands for vertices and E stands for edges
Cont…
BFS DFS
BFS(Breadth First Search) uses Queue data DFS(Depth First Search) uses Stack data
structure for finding the shortest path. structure.
BFS can be used to find single source shortest
path in an unweighted graph, because in BFS, In DFS, we might traverse through more edges
we reach a vertex with minimum number of to reach a destination vertex from a source.
edges from a source vertex.
BFS is more suitable for searching vertices DFS is more suitable when there are solutions
which are closer to the given source. away from source.
DFS is more suitable for game or puzzle
BFS considers all neighbors first and therefore
problems. We make a decision, then explore all
not suitable for decision making trees used in
paths through this decision. And if this decision
games or puzzles.
leads to win situation, we stop.
The Time complexity of BFS is O(V + E) when The Time complexity of DFS is also O(V + E)
Adjacency List is used and O(V^2) when when Adjacency List is used and O(V^2) when
Adjacency Matrix is used, where V stands for Adjacency Matrix is used, where V stands for
vertices and E stands for edges. vertices and E stands for edges.
Here, siblings are visited before the children Here, children are visited before the siblings
Topological Sorting
• Txoapmoplole
gical 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.
• Note: Topological Sorting for a graph is not possible if the graph is
not a DAG.
• There are two main ways to implement Topological Sort:
1) Kahn’s Algorithm (BFS-based approach) — Uses in-
degree (number of incoming edges).
2) DFS-Based Approach — Uses a stack to order nodes after visiting
dependencies.
Topological Sorting: BFS approach
• Compute the in-degree (number of incoming edges) for each node.
• Add all nodes with in-degree 0 to a queue (they have no
dependencies).
• Process the queue:
• Remove a node, add it to the sorted list.
• Reduce the in-degree of its dependent nodes.
• If a dependent node’s in-degree becomes 0, add it to the queue.
• Repeat until all nodes are processed.
Topological Sorting: BFS approach
Output: 5 4 2 3 1 0
Explanation: The first vertex in topological sorting is always a vertex with an in-
degree of 0 (a vertex with no incoming edges). 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. Another
topological sorting of the following graph is “4 5 2 3 1 0”.
Topological Sorting DFS approach
Algorithm for Topological Sorting using DFS:
• Create a graph with n vertices and m-directed edges.
• Initialize a stack and a visited array of size n.
• For each unvisited vertex in the graph, do the following:
• Call the DFS function with the vertex as the parameter.
• In the DFS function, mark the vertex as visited and recursively call
the DFS function for all unvisited neighbors of the vertex.
• Once all the neighbors have been visited, push the vertex onto
the stack.
• After all, vertices have been visited, pop elements from the stack
and append them to the output list until the stack is empty.
• The resulting list is the topologically sorted order of the graph.
Topological Sorting
Time Complexity: O(V+E).
Topological Sorting
• Kahn’s Algorithm is better for task scheduling & parallel
execution.
• DFS-Based Approach is useful when you only need to find the
order without modifying in-degree values(recursion based).
• Why Topological Sort is not possible for graphs with undirected
edges?
This is due to the fact that undirected edge between two
vertices u and v means, there is an edge from u to v as well as
from v to u. Because of this both the nodes u and v depend upon
each other and none of them can appear before the other in the
topological ordering without creating a contradiction.
Single-Source Shortest Path Problem
The problem of finding shortest paths from a source vertex v to all
other vertices in the graph.
Dijkstra Algorithm-
• Dijkstra Algorithm is a very famous greedy algorithm.
• It is used for solving the single source shortest path problem.
• It computes the shortest path from one particular source
node to all other remaining nodes of the graph.
Applications
- Maps (Map Quest, Google Maps)
- Routing Systems
Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source shortest
path problem in graph theory.
Works on both directed and undirected graphs. However, all edges
must have nonnegative weights.
Input: Weighted graph G={E,V} and source vertex v∈V, such that all
edge weights are nonnegative
Output: Lengths of shortest paths (or the shortest paths
themselves) from a given source vertex v∈V to all other vertices
Approach
• The algorithm computes for each vertex u the distance to u
from the start vertex v, that is, the weight of a shortest path
between v and u.
• the algorithm keeps track of the set of vertices for which the
distance has been computed, called the cloud C
• Every vertex has a label D associated with it. For any vertex u,
D[u] stores an approximation of the distance between v and
u. The algorithm will update a D[u] value when it finds a
shorter path from v to u.
• When a vertex u is added to the cloud, its label D[u] is equal
to the actual (final) distance between the starting vertex v and
vertex u.
42
Dijkstra pseudocode
Dijkstra(v1, v2):
for each vertex v: // Initialization
v's distance := infinity.
v's previous := none.
v1's distance := 0.
List := {all vertices}.
while List is not empty:
v := remove List vertex with minimum distance.
mark v as known.
for each unknown neighbor n of v:
dist := v's distance + edge (v, n)'s weight.
if dist is smaller than n's distance:
n's distance := dist.
n's previous := v.
reconstruct path from v2 back to v1,
following previous pointers.
43
Example: Initialization
Distance(source) = 0 ∞ Distance (all vertices
0 A
2
B but source) = ∞
4 1 3 10
2 2 ∞
∞ C D E
5 8 ∞ 4 6
1
F G
∞ ∞
Pick vertex in List with minimum distance.
44
Example: Update neighbors' distance
0 2
2
A B
4 1 3 10
2 2 ∞
∞ C D E
5 8 1 4 6
Distance(B) = 2 1
F G
Distance(D) = 1
∞ ∞
45
Example: Remove vertex with
minimum distance
0 2
2
A B
4 1 3 10
2 2 ∞
∞ C D E
5 8 1 4 6
1
F G
∞ ∞
Pick vertex in List with minimum distance, i.e., D
46
Example: Update neighbors
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
Distance(C) = 1 + 2 = 3 1
F G
Distance(E) = 1 + 2 = 3
Distance(F) = 1 + 8 = 9 9 5
Distance(G) = 1 + 4 = 5
47
Example: Continued...
Pick vertex in List with minimum distance (B) and update neighbors
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
Note : distance(D) not
F
1
G updated since D is
already known and
9 5 distance(E) not updated
since it is larger than
Pick vertex in List with minimum distance, i.e., B previously computed
48
Example: Continued...
Pick vertex List with minimum distance (E) and update neighbors
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
1
F G
No updating
9 5
49
Example: Continued...
Pick vertex List with minimum distance (C) and update neighbors
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
Distance(F) = 3 + 5 = 8 1
F G
8 5
50
Example: Continued...
Pick vertex List with minimum distance (G) and update neighbors
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
1
F G
Previous distance
6 5
Distance(F) = min (8, 5+1) = 6
51
Example (end)
0 2
2
A B
4 1 3 10
2 2
3 C D E 3
5 8 1 4 6
1
F G
6 5
Pick vertex not in S with lowest cost (F) and update neighbors
52
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Another Example
Implementations and Running Times
If adjacency matrix is used.
O(V^2)
For sparse graphs, or graphs with very few edges and many nodes, it can
be implemented more efficiently storing the graph in an adjacency list
using a binary heap or priority queue. This will produce a running time of
O((E+V) log V)