Lab 8.

GDS Data structures and Algorithms CSC10004

Lab 8

Graph Data Structures

1 Introduction to Graph Data Structures

1.1 Graph Basics
A graph G is a pair (V, E) where V is a set of vertices (or nodes) and E is a set of edges connecting
these vertices. Graphs are used to model pairwise relationships between objects, representing
connections, paths, flows, or dependencies.
Graphs can be categorized based on several properties:

• Directed vs. Undirected: In a directed graph (digraph), edges have a direction, going
from one vertex to another. In an undirected graph, edges have no direction and represent
a bidirectional relationship.

• Weighted vs. Unweighted: In a weighted graph, each edge has an associated numerical
value (weight). In an unweighted graph, all edges are considered to have equal importance.

• Cyclic vs. Acyclic: A graph is cyclic if it contains at least one cycle (a path that starts
and ends at the same vertex). A graph without cycles is acyclic.

• Connected vs. Disconnected: A graph is connected if there is a path between every pair
of vertices. Otherwise, it is disconnected and consists of multiple connected components.

• Simple vs. Non-simple: A simple graph has no self-loops (edges connecting a vertex to
itself) and no parallel edges (multiple edges between the same pair of vertices). A non-simple
graph may contain self-loops or parallel edges.

1.2 Graph Representation

There are several ways to represent a graph in computer memory. The choice of representation
depends on the nature of the graph and the operations that will be performed on it.

University of Science Faculty of Information Technology Page 1

Lab 8. GDS Data structures and Algorithms CSC10004

2 2
1 3 1 3
2 2
0 1 0 1

5 4 5 4
3 3

Undirected Weighted Graph Directed Weighted Graph

Figure 1: Examples of weighted graphs: undirected (left) and directed (right).

1.2.1 Adjacency Matrix

An adjacency matrix is a 2D array of size V × V , where V is the number of vertices. For an

unweighted graph, the entry A[i][j] is 1 if there is an edge from vertex i to vertex j, and 0
otherwise. For a weighted graph, A[i][j] contains the weight of the edge from i to j, or a special
value (e.g., ∞ or 0) if no such edge exists.

• Space Complexity: O(V 2 )

• Edge Lookup: O(1)

• Finding All Neighbors: O(V )

• Adding/Removing Edge: O(1)

• Adding/Removing Vertex: O(V 2 )

Adjacency matrices are efficient for dense graphs and when quick edge lookup is required, but
they consume more space for sparse graphs where most entries are zero.

2 0 1 2 3
0 1
0 0 2 3 0
3 1
1 0 0 0 1
2 3
4 2 0 0 0 4
3 0 0 0 0

Figure 2: A directed weighted graph and its adjacency matrix representation.

University of Science Faculty of Information Technology Page 2

Lab 8. GDS Data structures and Algorithms CSC10004

1.2.2 Adjacency List

An adjacency list uses an array of lists, where each array index represents a vertex, and the
corresponding list contains the vertices adjacent to it. For a weighted graph, each entry in the list
also includes the weight of the edge.

• Space Complexity: O(V + E)

• Edge Lookup: O(d) where d is the degree of the vertex

• Finding All Neighbors: O(d)

• Adding/Removing Edge: O(d)

• Adding/Removing Vertex: O(V + E)

Adjacency lists are more space-efficient for sparse graphs and are generally the preferred rep-
resentation in most applications.

2
0 1 0: 1, 2 2, 3
3 1 1: 3 1
2 3 2: 3 4
4
3:

Figure 3: The same graph with its adjacency list representation, showing both destinations and
weights.

1.3 Graph Traversal Algorithms

Traversal algorithms are used to visit every vertex in a graph in a systematic way. The two primary
graph traversal algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).

1.3.1 Breadth-First Search (BFS)

BFS explores a graph level by level, visiting all neighbors of a vertex before moving on to the next
level. It uses a queue data structure to keep track of vertices to be visited.
BFS has several important applications:

• Finding the shortest path in an unweighted graph

University of Science Faculty of Information Technology Page 3

Lab 8. GDS Data structures and Algorithms CSC10004

Algorithm 1 Breadth-First Search

1: procedure BFS(G, start)
2: Let Q be a queue
3: Mark start as visited and enqueue it in Q
4: while Q is not empty do
5: Dequeue a vertex v from Q
6: Process v
7: for each neighbor w of v do
8: if w is not visited then
9: Mark w as visited and enqueue it in Q
10: end if
11: end for
12: end while
13: end procedure

• Finding all connected components in an undirected graph

• Testing if a graph is bipartite

• Finding all nodes within a connected component

• Solving puzzles with the fewest moves

1.3.2 Depth-First Search (DFS)

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses
a stack (often implemented recursively) to keep track of vertices to be visited.

Algorithm 2 Depth-First Search

1: procedure DFS(G, start)
2: Mark start as visited
3: Process start
4: for each neighbor w of start do
5: if w is not visited then
6: DFS(G, w)
7: end if
8: end for
9: end procedure

DFS has several important applications:

• Topological sorting of a directed acyclic graph (DAG)

University of Science Faculty of Information Technology Page 4

Lab 8. GDS Data structures and Algorithms CSC10004

• Finding cycles in a graph

• Finding strongly connected components in a directed graph

• Generating mazes

• Solving puzzles (e.g., finding a path in a maze)

1.4 Minimum Spanning Tree (MST)

A minimum spanning tree of a connected, undirected, weighted graph is a spanning tree (a tree
that includes all vertices) with the minimum possible total edge weight. Two popular algorithms
for finding MSTs are Prim’s algorithm and Kruskal’s algorithm.

1.4.1 Prim’s Algorithm

Prim’s algorithm builds the MST by adding the minimum weight edge that connects a vertex in
the tree to a vertex outside the tree. It starts with an arbitrary vertex and grows the tree one edge
at a time.
B 3 B 2
3 2
A 4 D A 4 D
5 6
C C

Original Graph Minimum Spanning Tree

Figure 4: An example graph and its minimum spanning tree (highlighted in red).

1.5 Shortest Path Algorithms

Shortest path algorithms find the path with the minimum total edge weight from a source vertex
to one or all other vertices in a weighted graph.

1.5.1 Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted
graph with non-negative edge weights. It maintains a set of vertices whose shortest distance from
the source is already determined and expands this set by adding the vertex with the minimum
distance estimate at each step.

University of Science Faculty of Information Technology Page 5

Lab 8. GDS Data structures and Algorithms CSC10004

Algorithm 3 Prim’s Algorithm

1: procedure PrimMST(G)
2: Let T be an empty set (the MST)
3: Let P Q be a priority queue
4: Choose an arbitrary vertex start from G
5: for each vertex v in G do
6: key[v] ← ∞
7: parent[v] ← NIL
8: end for
9: key[start] ← 0
10: Insert all vertices of G into P Q with their key values
11: while P Q is not empty do
12: u ← Extract-Min(P Q)
13: Add edge (parent[u], u) to T if parent[u] is not NIL
14: for each neighbor v of u do
15: if v is in P Q and weight(u, v) < key[v] then
16: parent[v] ← u
17: key[v] ← weight(u, v)
18: Decrease-Key(P Q, v, key[v])
19: end if
20: end for
21: end while
22: return T
23: end procedure

In this lab, you will implement various graph representations, traversal algorithms, and shortest
path algorithms to gain hands-on experience with these fundamental concepts in computer science.

2 Exercise 1: Graph Representation - Adjacency Matrix

Implement a graph data structure using an adjacency matrix representation. The adjacency matrix
is a 2D array where each cell adjMatrix[i][j] represents the weight of the edge from vertex i to
vertex j. If no edge exists, the value is 0. The graph is directed, supports weighted edges, and
allows for the following operations:

• Initialize a graph with V vertices.

• Add a directed edge from vertex src to vertex dest with a given weight.

• Check if an edge exists from src to dest.

University of Science Faculty of Information Technology Page 6

Lab 8. GDS Data structures and Algorithms CSC10004

Algorithm 4 Dijkstra’s Algorithm

1: procedure Dijkstra(G, start)
2: for each vertex v in G do
3: dist[v] ← ∞
4: prev[v] ← NIL
5: visited[v] ← false
6: end for
7: dist[start] ← 0
8: P Q ← empty priority queue
9: Insert all vertices into P Q with their dist values
10: while P Q is not empty do
11: u ← Extract-Min(P Q)
12: visited[u] ← true
13: for each neighbor v of u do
14: if not visited[v] then
15: alt ← dist[u] + weight(u, v)
16: if alt < dist[v] then
17: dist[v] ← alt
18: prev[v] ← u
19: Decrease-Key(P Q, v, dist[v])
20: end if
21: end if
22: end for
23: end while
24: return (dist, prev)
25: end procedure

• Retrieve the weight of an edge from src to dest.

• Print the adjacency matrix in a readable format.

Input:

• Number of vertices V .

• A sequence of edge additions, each specified as (src, dest, weight).

• Queries to check edge existence or retrieve edge weights.

Output:

• The adjacency matrix of the graph.

University of Science Faculty of Information Technology Page 7

 Lab 8. GDS Data structures and Algorithms CSC10004

10
B C
7 11

A 9 2 D
15 14
6
F E
9
2

Figure 5: A graph with the shortest paths from vertex A to all other vertices highlighted in red.

• Results of edge existence checks (true/false).

• Weights of queried edges (or 0 if no edge exists).

Contraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• weight ≥ 1: Edge weights are positive integers.

• The graph is directed, so an edge from src to dest does not imply an edge from dest to
src.

• No parallel edges (adding an edge overwrites the previous weight if the edge already exists).

• No self-loops unless explicitly added (not specified in the example).

Examples:
1 Input :
2 V = 5
3 Edges : (0 ,1 ,2) , (0 ,3 ,1) , (1 ,2 ,3) , (2 ,3 ,4) , (3 ,4 ,5) , (4 ,0 ,6)
4

5 Output :
6 Adjacency Matrix representation of the graph :
7 0 2 0 1 0
8 0 0 3 0 0
9 0 0 0 4 0
10 0 0 0 0 5
11 6 0 0 0 0
12

University of Science Faculty of Information Technology Page 8

 Lab 8. GDS Data structures and Algorithms CSC10004

13 Testing edges :
14 Is there an edge from 0 to 1? Yes
15 Is there an edge from 1 to 0? No
16 Weight of edge from 2 to 3: 4

Initial code for Exercise 01:

1 // File : Exercise_1 . cpp
2 # include < iostream >
3 # include < vector >
4

5 class Graph {
6 private :
7 int V ; // Number of vertices
8 std :: vector < std :: vector < int > > adjMatrix ;
9

10 public :
11 // TODO : Implement constructor to initialize the graph with V vertices
12 Graph ( int vertices ) {
13 // Initialize V and create a V x V adjacency matrix
14 }
15

16 // TODO : Implement function to add an edge from src to dest with weight
17 void addEdge ( int src , int dest , int weight = 1) {
18 // Set the weight in the adjacency matrix
19 }
20

21 // TODO : Implement function to check if there is an edge from src to dest

22 bool isEdge ( int src , int dest ) {
23 // Check if there is an edge ( weight > 0) in the adjacency matrix
24 return false ; // Replace with your implementation
25 }
26

27 // TODO : Implement function to get the weight of an edge from src to dest
28 int getWeight ( int src , int dest ) {
29 // Return the weight from the adjacency matrix , or 0 if no edge exists
30 return 0; // Replace with your implementation
31 }
32

33 // TODO : Implement function to print the adjacency matrix

34 void printGraph () {
35 // Print the adjacency matrix in a readable format
36 }

University of Science Faculty of Information Technology Page 9

 Lab 8. GDS Data structures and Algorithms CSC10004

37 };
38

39 int main () {
40 Graph g (5) ; // Create a graph with 5 vertices (0 to 4)
41

42 g . addEdge (0 , 1, 2) ;
43 g . addEdge (0 , 3, 1) ;
44 g . addEdge (1 , 2, 3) ;
45 g . addEdge (2 , 3, 4) ;
46 g . addEdge (3 , 4, 5) ;
47 g . addEdge (4 , 0, 6) ;
48

49 std :: cout << " Adjacency Matrix representation of the graph : " << std :: endl ;
50 g . printGraph () ;
51

52 // Test isEdge and getWeight

53 std :: cout << " \ nTesting edges : " << std :: endl ;
54 std :: cout << " Is there an edge from 0 to 1? " << ( g . isEdge (0 , 1) ? " Yes " :
" No " ) << std :: endl ;
55 std :: cout << " Is there an edge from 1 to 0? " << ( g . isEdge (1 , 0) ? " Yes " :
" No " ) << std :: endl ;
56 std :: cout << " Weight of edge from 2 to 3: " << g . getWeight (2 , 3) << std ::
endl ;
57

58 return 0;
59 }

3 Exercise 2: Graph Representation - Adjacency List

Implement a graph data structure using an adjacency list representation. The graph should support
weighted edges and provide functionality to add edges, check for edges, get edge weights, and
display the entire graph structure.

• Initialize a graph with V vertices.

• Add a directed edge from vertex src to vertex dest with a given weight.

• Check if an edge exists from src to dest.

• Retrieve the weight of an edge from src to dest.

University of Science Faculty of Information Technology Page 10

 Lab 8. GDS Data structures and Algorithms CSC10004

• Print the adjacency list in a readable format.

Input:

• Number of vertices V .

• A sequence of edge additions, each specified as (src, dest, weight).

• Queries to check edge existence or retrieve edge weights.

Output:

• The adjacency list of the graph, showing each vertex and its outgoing edges (destination and
weight).

• Results of edge existence checks (true/false).

• Weights of queried edges (or 0 if no edge exists).

Contraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• weight ≥ 1: Edge weights are positive integers.

• The graph is directed, so an edge from src to dest does not imply an edge from dest to
src.

• No parallel edges (adding an edge overwrites the previous weight if the edge already exists).

• No self-loops unless explicitly added (not specified in the example).

Examples:
1 Input :
2 V = 5
3 Edges : (0 ,1 ,2) , (0 ,3 ,1) , (1 ,2 ,3) , (2 ,3 ,4) , (3 ,4 ,5) , (4 ,0 ,6)
4

5 Output :
6 Adjacency List representation of the graph :
7 0 -> (1 , 2) (3 , 1)
8 1 -> (2 , 3)

University of Science Faculty of Information Technology Page 11

 Lab 8. GDS Data structures and Algorithms CSC10004

9 2 -> (3 , 4)
10 3 -> (4 , 5)
11 4 -> (0 , 6)
12

13 Testing edges :
14 Is there an edge from 0 to 1? Yes
15 Is there an edge from 1 to 0? No
16 Weight of edge from 2 to 3: 4

Initial code for Exercise 02:

1 // File : Exercise_2 . cpp
2

3 # include < iostream >

4 # include < vector >
5

6 struct Edge {
7 int dest ;
8 int weight ;
9

10 Edge ( int d , int w = 1) : dest ( d ) , weight ( w ) {}

11 };
12

13 class Graph {
14 private :
15 int V ; // Number of vertices
16 std :: vector < std :: vector < Edge > > adjList ;
17

18 public :
19 // TODO : Implement constructor to initialize the graph with V vertices
20 Graph ( int vertices ) {
21 // Initialize V and create an empty adjacency list for each vertex
22 }
23

24 // TODO : Implement function to add an edge from src to dest with weight
25 void addEdge ( int src , int dest , int weight = 1) {
26 // Add an edge to the adjacency list
27 }
28

29 // TODO : Implement function to check if there is an edge from src to dest

30 bool isEdge ( int src , int dest ) {
31 // Check if dest is in the adjacency list of src
32 return false ; // Replace with your implementation

University of Science Faculty of Information Technology Page 12

 Lab 8. GDS Data structures and Algorithms CSC10004

33 }
34

35 // TODO : Implement function to get the weight of an edge from src to dest
36 int getWeight ( int src , int dest ) {
37 // Find dest in the adjacency list of src and return its weight
38 return 0; // Replace with your implementation
39 }
40

41 // TODO : Implement function to print the adjacency list

42 void printGraph () {
43 // Print the adjacency list in a readable format
44 }
45 };
46

47 int main () {
48 Graph g (5) ; // Create a graph with 5 vertices (0 to 4)
49

50 g . addEdge (0 , 1, 2) ;
51 g . addEdge (0 , 3, 1) ;
52 g . addEdge (1 , 2, 3) ;
53 g . addEdge (2 , 3, 4) ;
54 g . addEdge (3 , 4, 5) ;
55 g . addEdge (4 , 0, 6) ;
56

57 std :: cout << " Adjacency List representation of the graph : " << std :: endl ;
58 g . printGraph () ;
59

60 // Test isEdge and getWeight

61 std :: cout << " \ nTesting edges : " << std :: endl ;
62 std :: cout << " Is there an edge from 0 to 1? " << ( g . isEdge (0 , 1) ? " Yes " :
" No " ) << std :: endl ;
63 std :: cout << " Is there an edge from 1 to 0? " << ( g . isEdge (1 , 0) ? " Yes " :
" No " ) << std :: endl ;
64 std :: cout << " Weight of edge from 2 to 3: " << g . getWeight (2 , 3) << std ::
endl ;
65

66 return 0;
67 }

University of Science Faculty of Information Technology Page 13

Lab 8. GDS Data structures and Algorithms CSC10004

4 Exercise 3: Breadth-First Search (BFS)

Implement a graph data structure using an adjacency list representation and perform Breadth-First
Search (BFS) traversal to:

• Traverse the graph starting from a source vertex, printing vertices in the order they are
visited.

• Find the shortest paths (in terms of the number of edges) from a source vertex to all other
vertices in an unweighted, directed graph.

The adjacency list stores, for each vertex, a list of its neighboring vertices. The graph is directed
and unweighted (edges have no weights or are assumed to have a weight of 1 for shortest path
purposes).
Input:

• Number of vertices V when initializing the graph.

• A sequence of directed edges, each specified as (src, dest).

• A source vertex for BFS traversal and shortest path computation.

Output:

• BFS traversal: A sequence of vertices visited starting from the source.

• Shortest paths: For each reachable vertex, the shortest distance (number of edges) from the
source and the path from the source to that vertex.

Contraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• weight ≥ 1: Edge weights are positive integers.

• The graph is directed, so an edge from src to dest does not imply an edge from dest to
src.

• The graph is unweighted (all edges have an implicit weight of 1 for shortest path purposes).

• No parallel edges or self-loops.

University of Science Faculty of Information Technology Page 14

 Lab 8. GDS Data structures and Algorithms CSC10004

Examples:
1 Input :
2 V = 6
3 Edges : (0 ,1) , (0 ,2) , (1 ,3) , (2 ,3) , (2 ,4) , (3 ,4) , (3 ,5) , (4 ,5)
4 Source : 0
5

6 Output :
7 BFS traversal starting from vertex 0:
8 0 1 2 3 4 5
9

10 Shortest paths from vertex 0:

11 Vertex 0: distance = 0 , path = 0
12 Vertex 1: distance = 1 , path = 0 -> 1
13 Vertex 2: distance = 1 , path = 0 -> 2
14 Vertex 3: distance = 2 , path = 0 -> 1 -> 3 or 0 -> 2 -> 3
15 Vertex 4: distance = 2 , path = 0 -> 2 -> 4
16 Vertex 5: distance = 3 , path = 0 -> 2 -> 4 -> 5

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjList : array of lists , where adjList [ i ] stores neighbors of vertex i
4

5 constructor ( vertices ) :
6 V = vertices
7 adjList = allocate V empty lists
8

9 function addEdge ( src , dest ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjList [ src ]. append ( dest )
12

13 function BFS ( source ) :

14 if source < 0 or source >= V :
15 return
16 visited = array of V booleans , all false
17 queue = empty queue
18 visited [ source ] = true
19 queue . push ( source )
20 while queue is not empty :
21 v = queue . pop ()
22 print v
23 for each neighbor w in adjList [ v ]:

University of Science Faculty of Information Technology Page 15

 Lab 8. GDS Data structures and Algorithms CSC10004

24 if not visited [ w ]:
25 visited [ w ] = true
26 queue . push ( w )
27

28 function shortestPath ( source ) :

29 if source < 0 or source >= V :
30 return
31 visited = array of V booleans , all false
32 distance = array of V integers , all -1
33 parent = array of V integers , all -1
34 queue = empty queue
35 visited [ source ] = true
36 distance [ source ] = 0
37 queue . push ( source )
38 while queue is not empty :
39 v = queue . pop ()
40 for each neighbor w in adjList [ v ]:
41 if not visited [ w ]:
42 visited [ w ] = true
43 distance [ w ] = distance [ v ] + 1
44 parent [ w ] = v
45 queue . push ( w )
46 for i from 0 to V -1:
47 if distance [ i ] != -1:
48 print " Vertex i : distance = distance [ i ] , path = "
49 printPath ( parent , i )
50 print newline
51

52 function printPath ( parent , dest ) :

53 if parent [ dest ] == -1:
54 print dest
55 return
56 printPath ( parent , parent [ dest ])
57 print " -> dest "

Initial code for Exercise 03:

1 // File : Exercise_3 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < queue >
5

6 class Graph {

University of Science Faculty of Information Technology Page 16

 Lab 8. GDS Data structures and Algorithms CSC10004

7 private :
8 int V ;
9 std :: vector < std :: vector < int > > adjList ;
10

11 public :
12 Graph ( int vertices ) : V ( vertices ) {
13 adjList . resize ( V ) ;
14 }
15

16 void addEdge ( int src , int dest ) {

17 adjList [ src ]. push_back ( dest ) ;
18 }
19

20 // TODO : Implement BFS traversal starting from source vertex

21 void BFS ( int source ) {
22 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
23 // 2. Create a queue for BFS
24 // 3. Mark the source vertex as visited and enqueue it
25 // 4. While the queue is not empty :
26 // a . Dequeue a vertex and print it
27 // b . Get all adjacent vertices of the dequeued vertex
28 // c . If an adjacent vertex has not been visited , mark it as visited
and enqueue it
29 }
30

31 // TODO : Implement function to find shortest paths from source to all

vertices
32 void shortestPath ( int source ) {
33 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
34 // 2. Create an integer array ’ distance ’ and initialize all entries as
-1 ( infinity )
35 // 3. Create an integer array ’ parent ’ to store the shortest path tree
36 // 4. Mark source as visited , set its distance as 0 , and enqueue it
37 // 5. While the queue is not empty :
38 // a . Dequeue a vertex
39 // b . For all its adjacent vertices :
40 // i . If not visited , mark as visited , set distance , set parent ,
and enqueue it
41 // 6. Print the shortest distances and paths
42 }

University of Science Faculty of Information Technology Page 17

 Lab 8. GDS Data structures and Algorithms CSC10004

43

44 // Helper function to print path from source to destination

45 void printPath ( const std :: vector < int >& parent , int dest ) {
46 if ( parent [ dest ] == -1) {
47 std :: cout << dest ;
48 return ;
49 }
50 printPath ( parent , parent [ dest ]) ;
51 std :: cout << " -> " << dest ;
52 }
53 };
54

55 int main () {
56 Graph g (6) ; // Create a graph with 6 vertices (0 to 5)
57

58 g . addEdge (0 , 1) ;
59 g . addEdge (0 , 2) ;
60 g . addEdge (1 , 3) ;
61 g . addEdge (2 , 3) ;
62 g . addEdge (2 , 4) ;
63 g . addEdge (3 , 4) ;
64 g . addEdge (3 , 5) ;
65 g . addEdge (4 , 5) ;
66

67 std :: cout << " BFS traversal starting from vertex 0: " << std :: endl ;
68 g . BFS (0) ;
69

70 std :: cout << " \ nShortest paths from vertex 0: " << std :: endl ;
71 g . shortestPath (0) ;
72

73 return 0;
74 }

Complexity analysis
Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append a neighbor.

• BFS: O(V +E), as each vertex is enqueued/dequeued once (O(V )) and each edge is processed
once (O(E)).

University of Science Faculty of Information Technology Page 18

 Lab 8. GDS Data structures and Algorithms CSC10004

• shortestPath: O(V + E) for BFS, plus O(V ) for printing paths (assuming path lengths are
bounded by V ).

• printPath: O(V ) in the worst case for a single path.

Space complexity:

• Adjacency list: O(V + E).

• BFS/shortestPath: O(V ) for visited, distance, parent, and the queue.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 6
2 Edges : (0 ,1) , (0 ,2) , (1 ,3) , (2 ,3) , (2 ,4) , (3 ,4) , (3 ,5) , (4 ,5)
3 Source : 0

Graph visualization:
1 0 -> 1 -> 3 -> 5
2 \ / \ /
3 -> 2 -> 4

Step-by-Step:

• Initialization:

– Adjacency list (adjList):

∗ adjList[0]: [1, 2]
∗ adjList[1]: [3]
∗ adjList[2]: [3, 4]
∗ adjList[3]: [4, 5]
∗ adjList[4]: [5]
∗ adjList[5]: []

• BFS Traversal (source = 0):

– Initialize: visited = [false, ..., false], queue = [].

– Enqueue vertex 0: Set visited[0] = true, queue = [0].

University of Science Faculty of Information Technology Page 19

Lab 8. GDS Data structures and Algorithms CSC10004

– Process queue:
∗ Dequeue 0, print 0: Neighbors 1, 2 (unvisited). Enqueue 1, 2: Set visited[1] =
true, visited[2] = true, queue = [1, 2].
∗ Dequeue 1, print 1: Neighbor 3 (unvisited). Enqueue 3: Set visited[3] = true,
queue = [2, 3].
∗ Dequeue 2, print 2: Neighbors 3 (visited), 4 (unvisited). Enqueue 4: Set visited[4]
= true, queue = [3, 4].
∗ Dequeue 3, print 3: Neighbors 4 (visited), 5 (unvisited). Enqueue 5: Set visited[5]
= true, queue = [4, 5].
∗ Dequeue 4, print 4: Neighbor 5 (visited), queue = [5].
∗ Dequeue 5, print 5: No neighbors, queue = [].
– Output: 0 1 2 3 4 5.

• Shortest Paths (source = 0):

– Initialize: visited = [false, ..., false], distance = [-1, ..., -1], parent =
[-1, ..., -1], distance[0] = 0, visited[0] = true, queue = [0].
– Process queue:
∗ Dequeue 0: Neighbors 1, 2.
· For 1: Set visited[1] = true, distance[1] = 1, parent[1] = 0, enqueue
1.
· For 2: Set visited[2] = true, distance[2] = 1, parent[2] = 0, enqueue
2.
· queue = [1, 2].
∗ Dequeue 1: Neighbor 3.
· For 3: Set visited[3] = true, distance[3] = 2, parent[3] = 1, enqueue
3.
· queue = [2, 3].
∗ Dequeue 2: Neighbors 3, 4.
· 3 visited, skip.
· For 4: Set visited[4] = true, distance[4] = 2, parent[4] = 2, enqueue
4.
· queue = [3, 4].

University of Science Faculty of Information Technology Page 20

 Lab 8. GDS Data structures and Algorithms CSC10004

∗ Dequeue 3: Neighbors 4, 5.
· 4 visited, skip.
· For 5: Set visited[5] = true, distance[5] = 3, parent[5] = 3, enqueue
5.
· queue = [4, 5].
∗ Dequeue 4: Neighbor 5 (visited), skip. queue = [5].
∗ Dequeue 5: No neighbors. queue = [].
– Final state:
∗ distance = [0, 1, 1, 2, 2, 3].
∗ parent = [-1, 0, 0, 1, 2, 3].
– Print paths:
∗ Vertex 0: distance = 0, path = 0.
∗ Vertex 1: distance = 1, path = 0 -¿ 1.
∗ Vertex 2: distance = 1, path = 0 -¿ 2.
∗ Vertex 3: distance = 2, path = 0 -¿ 1 -¿ 3.
∗ Vertex 4: distance = 2, path = 0 -¿ 2 -¿ 4.
∗ Vertex 5: distance = 3, path = 0 -¿ 2 -¿ 4 -¿ 5.

Output:
1 BFS traversal starting from vertex 0:
2 0 1 2 3 4 5
3

4 Shortest paths from vertex 0:

5 Vertex 0: distance = 0 , path = 0
6 Vertex 1: distance = 1 , path = 0 -> 1
7 Vertex 2: distance = 1 , path = 0 -> 2
8 Vertex 3: distance = 2 , path = 0 -> 1 -> 3
9 Vertex 4: distance = 2 , path = 0 -> 2 -> 4
10 Vertex 5: distance = 3 , path = 0 -> 2 -> 4 -> 5

5 Exercise 4: Depth-First Search (DFS)

Implement a Depth-First Search (DFS) traversal on a directed graph and detect whether the graph
contains a cycle. The graph is represented using an adjacency list, where each vertex stores a list
of its neighboring vertices. The implementation includes:

University of Science Faculty of Information Technology Page 21

 Lab 8. GDS Data structures and Algorithms CSC10004

• DFS traversal starting from a given source vertex, printing vertices in the order they are
visited.

• Cycle detection to determine if the directed graph contains a cycle.

Input:

• Number of vertices V when initializing the graph.

• A sequence of directed edges, each specified as (src, dest).

• A source vertex for DFS traversal.

• Queries to check for cycles in the graph.

Output:

• DFS traversal: A sequence of vertices visited starting from the source.

• Cycle detection: A boolean (Yes/No) indicating whether the graph contains a cycle.

Contraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• weight ≥ 1: Edge weights are positive integers.

• The graph is directed, so an edge from src to dest does not imply an edge from dest to
src.

• The graph is unweighted (all edges have an implicit weight of 1 for shortest path purposes).

• No parallel edges or self-loops.

Examples:
1 Input :
2 V = 6
3 Edges : (0 ,1) , (0 ,2) , (1 ,3) , (3 ,4) , (4 ,5)
4 Source : 0
5 Additional edge : (5 ,3)
6

7 Output :

University of Science Faculty of Information Technology Page 22

 Lab 8. GDS Data structures and Algorithms CSC10004

8 DFS traversal starting from vertex 0:

9 0 1 3 4 5 2
10

11 Does the graph have a cycle ? No

12

13 After adding edge 5 - >3 , does the graph have a cycle ? Yes

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjList : array of lists , where adjList [ i ] stores neighbors of vertex i
4

5 constructor ( vertices ) :
6 V = vertices
7 adjList = allocate V empty lists
8

9 function addEdge ( src , dest ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjList [ src ]. append ( dest )
12

13 function DFS ( source ) :

14 if source < 0 or source >= V :
15 return
16 visited = array of V booleans , all false
17 DFSUtil ( source , visited )
18

19 function DFSUtil ( vertex , visited ) :

20 visited [ vertex ] = true
21 print vertex
22 for each neighbor in adjList [ vertex ]:
23 if not visited [ neighbor ]:
24 DFSUtil ( neighbor , visited )
25

26 function hasCycle () :
27 visited = array of V booleans , all false
28 recStack = array of V booleans , all false
29 for i from 0 to V -1:
30 if not visited [ i ] and isCyclicUtil (i , visited , recStack ) :
31 return true
32 return false
33

34 function isCyclicUtil ( vertex , visited , recStack ) :

University of Science Faculty of Information Technology Page 23

 Lab 8. GDS Data structures and Algorithms CSC10004

35 visited [ vertex ] = true

36 recStack [ vertex ] = true
37 for each neighbor in adjList [ vertex ]:
38 if not visited [ neighbor ] and isCyclicUtil ( neighbor , visited ,
recStack ) :
39 return true
40 else if recStack [ neighbor ]:
41 return true
42 recStack [ vertex ] = false
43 return false

Initial code for Exercise 04:

1 // File : Exercise_4 . cpp
2 # include < iostream >
3 # include < vector >
4

5 class Graph {
6 private :
7 int V ;
8 std :: vector < std :: vector < int > > adjList ;
9

10 public :
11 Graph ( int vertices ) : V ( vertices ) {
12 adjList . resize ( V ) ;
13 }
14

15 void addEdge ( int src , int dest ) {

16 adjList [ src ]. push_back ( dest ) ;
17 }
18

19 // TODO : Implement DFS traversal starting from source vertex

20 void DFS ( int source ) {
21 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
22 // 2. Call the recursive DFSUtil function
23 }
24

25 // TODO : Implement the recursive DFS utility function

26 void DFSUtil ( int vertex , std :: vector < bool >& visited ) {
27 // 1. Mark the current vertex as visited and print it
28 // 2. Recursively visit all the adjacent vertices that are not visited
29 }

University of Science Faculty of Information Technology Page 24

 Lab 8. GDS Data structures and Algorithms CSC10004

30

31 // TODO : Implement function to detect cycle in the graph

32 bool hasCycle () {
33 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
34 // 2. Create a boolean array ’ recStack ’ to keep track of vertices in
the recursion stack
35 // 3. Call the recursive isCyclicUtil function for all vertices
36 return false ; // Replace with your implementation
37 }
38

39 // TODO : Implement the recursive cycle detection utility function

40 bool isCyclicUtil ( int vertex , std :: vector < bool >& visited , std :: vector < bool
>& recStack ) {
41 // 1. Mark the current vertex as visited and add it to the recursion
stack
42 // 2. Check all adjacent vertices :
43 // a . If an adjacent vertex is not visited , recursively check if it
leads to a cycle
44 // b . If an adjacent vertex is in the recursion stack , there is a
cycle
45 // 3. Remove the vertex from the recursion stack and return false
46 return false ; // Replace with your implementation
47 }
48 };
49

50 int main () {
51 Graph g (6) ; // Create a graph with 6 vertices (0 to 5)
52

53 g . addEdge (0 , 1) ;
54 g . addEdge (0 , 2) ;
55 g . addEdge (1 , 3) ;
56 g . addEdge (3 , 4) ;
57 g . addEdge (4 , 5) ;
58

59 std :: cout << " DFS traversal starting from vertex 0: " << std :: endl ;
60 g . DFS (0) ;
61

62 std :: cout << " \ nDoes the graph have a cycle ? "
63 << ( g . hasCycle () ? " Yes " : " No " ) << std :: endl ;
64

65 // Adding an edge that creates a cycle

University of Science Faculty of Information Technology Page 25

 Lab 8. GDS Data structures and Algorithms CSC10004

66 g . addEdge (5 , 3) ;
67

68 std :: cout << " After adding edge 5 - >3 , does the graph have a cycle ? "
69 << ( g . hasCycle () ? " Yes " : " No " ) << std :: endl ;
70

71 return 0;
72 }

Complexity analysis
Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append a neighbor.

• DFS: O(V + E), as each vertex and edge is processed once.

• DFSUtil: O(V + E) across all calls.

• hasCycle: O(V + E), as it performs a DFS with additional recursion stack tracking.

• isCyclicUtil: O(V + E) across all calls.

Space complexity:

• Adjacency list: O(V + E).

• DFS: O(V ) for visited and recursion stack.

• Cycle detection: O(V ) for visited, recStack, and recursion stack.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 6
2 Edges : (0 ,1) , (0 ,2) , (1 ,3) , (3 ,4) , (4 ,5)
3 Source : 0
4 Additional edge : (5 ,3)

Graph visualization:
1 0 -> 1 -> 3 -> 4 -> 5
2 \ ^
3 -> 2 (5 - >3 after addition )

University of Science Faculty of Information Technology Page 26

Lab 8. GDS Data structures and Algorithms CSC10004

Step-by-Step:

• Initialization:

– Adjacency list (adjList):

∗ adjList[0]: [1, 2]
∗ adjList[1]: [3]
∗ adjList[2]: []
∗ adjList[3]: [4]
∗ adjList[4]: [5]
∗ adjList[5]: []

• DFS Traversal (source = 0):

– Initialize: visited = [false, ..., false].

– Start at vertex 0: Set visited[0] = true, print 0.
∗ Process neighbor 1 (visited[1] = false): Set visited[1] = true, print 1.
· Process neighbor 3 (visited[3] = false): Set visited[3] = true, print 3.
· Process neighbor 4 (visited[4] = false): Set visited[4] = true, print 4.
· Process neighbor 5 (visited[5] = false): Set visited[5] = true, print 5,
no neighbors.
· No more neighbors for 4 or 3.
∗ No more neighbors for 1.
∗ Process neighbor 2 (visited[2] = false): Set visited[2] = true, print 2, no
neighbors.
– Output: 0 1 3 4 5 2.

• Cycle Detection (Initial Graph):

– Initialize: visited = [false, ..., false], recStack = [false, ..., false].

– Vertex 0: Set visited[0] = true, recStack[0] = true.
∗ Process neighbor 1 (visited[1] = false): Set visited[1] = true, recStack[1]
= true.
· Process neighbor 3 (visited[3] = false): Set visited[3] = true, recStack[3]
= true.

University of Science Faculty of Information Technology Page 27

Lab 8. GDS Data structures and Algorithms CSC10004

· Process neighbor 4 (visited[4] = false): Set visited[4] = true, recStack[4]

= true.
· Process neighbor 5 (visited[5] = false): Set visited[5] = true, recStack[5]
= true, no neighbors, set recStack[5] = false, return false.
· Set recStack[4] = false, return false.
· Set recStack[3] = false, return false.
∗ Set recStack[1] = false, return false.
∗ Process neighbor 2 (visited[2] = false): Set visited[2] = true, recStack[2]
= true, no neighbors, set recStack[2] = false, return false.
– Set recStack[0] = false, return false.
– All other vertices visited, no cycles found.
– Output: No cycle.

• Add Edge (5,3):

– Update: adjList[5] = [3].

• Cycle Detection (After Adding Edge):

– Reset: visited = [false, ..., false], recStack = [false, ..., false].

– Vertex 0: Set visited[0] = true, recStack[0] = true.
∗ Process neighbor 1 (visited[1] = false): Set visited[1] = true, recStack[1]
= true.
· Process neighbor 3 (visited[3] = false): Set visited[3] = true, recStack[3]
= true.
· Process neighbor 4 (visited[4] = false): Set visited[4] = true, recStack[4]
= true.
· Process neighbor 5 (visited[5] = false): Set visited[5] = true, recStack[5]
= true.
· Process neighbor 3 (recStack[3] = true): Cycle detected, return true.
· Return true from vertex 5.
· Return true from vertex 4.
· Return true from vertex 3.
∗ Return true from vertex 1.

University of Science Faculty of Information Technology Page 28

 Lab 8. GDS Data structures and Algorithms CSC10004

– Return true from vertex 0.

– Cycle detected (path 3 -¿ 4 -¿ 5 -¿ 3).
– Output: Cycle exists.

Output:
1 DFS traversal starting from vertex 0:
2 0 1 3 4 5 2
3

4 Does the graph have a cycle ? No

5

6 After adding edge 5 - >3 , does the graph have a cycle ? Yes

6 Exercise 5: Topological Sort

Implement a topological sorting algorithm for a directed acyclic graph (DAG) using Depth-First
Search (DFS). Topological sorting orders the vertices of a DAG such that for every directed edge
(u, v), vertex u appears before vertex v in the ordering. The graph is represented using an adjacency
list, and the implementation includes a cycle detection mechanism to ensure the graph is a DAG.
Input:

• Number of vertices V when initializing the graph.

• A sequence of directed edges, each specified as (src, dest).

• A request to perform topological sorting.

Output:

• If the graph is a DAG, a valid topological ordering of the vertices.

• If the graph contains a cycle, a message indicating that topological sorting is not possible.

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is directed, so an edge from src to dest does not imply an edge from dest to
src.

University of Science Faculty of Information Technology Page 29

 Lab 8. GDS Data structures and Algorithms CSC10004

• The graph is unweighted (edges have no weights).

• No parallel edges or self-loops.

Examples:
1 Input :
2 V = 6
3 Edges : (5 ,2) , (5 ,0) , (4 ,0) , (4 ,1) , (2 ,3) , (3 ,1)
4 Graph :
5 5 -> 2 -> 3 -> 1
6 -> 0 ^
7 4 -- -- -- -- > |
8

9 Output :
10 Topological Sort : 5 4 2 3 1 0

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjList : array of lists , where adjList [ i ] stores neighbors of vertex i
4

5 constructor ( vertices ) :
6 V = vertices
7 adjList = allocate V empty lists
8

9 function addEdge ( src , dest ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjList [ src ]. append ( dest )
12

13 function topologicalSort () :
14 visited = array of V booleans , all false
15 stack = empty stack
16 for i from 0 to V -1:
17 if not visited [ i ]:
18 t op o l o gi c a lS o r tU t i l (i , visited , stack )
19 while stack is not empty :
20 print stack . pop ()
21

22 function t o p ol o g ic a l So r t Ut i l ( vertex , visited , stack ) :

23 visited [ vertex ] = true
24 for each neighbor in adjList [ vertex ]:
25 if not visited [ neighbor ]:

University of Science Faculty of Information Technology Page 30

 Lab 8. GDS Data structures and Algorithms CSC10004

26 t op o l o gi c a lS o r tU t i l ( neighbor , visited , stack )

27 stack . push ( vertex )
28

29 function hasCycle () :
30 visited = array of V booleans , all false
31 recStack = array of V booleans , all false
32 for i from 0 to V -1:
33 if not visited [ i ] and isCyclicUtil (i , visited , recStack ) :
34 return true
35 return false
36

37 function isCyclicUtil ( vertex , visited , recStack ) :

38 visited [ vertex ] = true
39 recStack [ vertex ] = true
40 for each neighbor in adjList [ vertex ]:
41 if not visited [ neighbor ] and isCyclicUtil ( neighbor , visited ,
recStack ) :
42 return true
43 else if recStack [ neighbor ]:
44 return true
45 recStack [ vertex ] = false
46 return false

Initial code for Exercise 05:

1 // File : Exercise_5 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < stack >
5

6 class Graph {
7 private :
8 int V ;
9 std :: vector < std :: vector < int > > adjList ;
10

11 public :
12 Graph ( int vertices ) : V ( vertices ) {
13 adjList . resize ( V ) ;
14 }
15

16 void addEdge ( int src , int dest ) {

17 adjList [ src ]. push_back ( dest ) ;
18 }

University of Science Faculty of Information Technology Page 31

 Lab 8. GDS Data structures and Algorithms CSC10004

19

20 // TODO : Implement function to perform topological sort

21 void topologicalSort () {
22 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
23 // 2. Create a stack to store the topological sort result
24 // 3. Call the recursive t op o l og i c al S o rt U t il function for all unvisited
vertices
25 // 4. Pop and print the elements from the stack
26 }
27

28 // TODO : Implement the recursive topological sort utility function

29 void to p o lo g i ca l S o rt U t il ( int vertex , std :: vector < bool >& visited , std :: stack
< int >& stack ) {
30 // 1. Mark the current vertex as visited
31 // 2. Recursively visit all the adjacent vertices that are not visited
32 // 3. Push the current vertex to the stack after visiting all adjacent
vertices
33 }
34

35 // Helper function to check if the graph has a cycle ( optional , for

validation )
36 bool hasCycle () {
37 std :: vector < bool > visited (V , false ) ;
38 std :: vector < bool > recStack (V , false ) ;
39

40 for ( int i = 0; i < V ; i ++) {

41 if (! visited [ i ] && isCyclicUtil (i , visited , recStack ) ) {
42 return true ;
43 }
44 }
45

46 return false ;
47 }
48

49 bool isCyclicUtil ( int vertex , std :: vector < bool >& visited , std :: vector < bool
>& recStack ) {
50 visited [ vertex ] = true ;
51 recStack [ vertex ] = true ;
52

53 for ( int neighbor : adjList [ vertex ]) {

54 if (! visited [ neighbor ] && isCyclicUtil ( neighbor , visited , recStack )

University of Science Faculty of Information Technology Page 32

 Lab 8. GDS Data structures and Algorithms CSC10004

) {
55 return true ;
56 } else if ( recStack [ neighbor ]) {
57 return true ;
58 }
59 }
60

61 recStack [ vertex ] = false ;

62 return false ;
63 }
64 };
65

66 int main () {
67 Graph g (6) ; // Create a graph with 6 vertices (0 to 5)
68

69 g . addEdge (5 , 2) ;
70 g . addEdge (5 , 0) ;
71 g . addEdge (4 , 0) ;
72 g . addEdge (4 , 1) ;
73 g . addEdge (2 , 3) ;
74 g . addEdge (3 , 1) ;
75

76 if ( g . hasCycle () ) {
77 std :: cout << " Graph has a cycle . Topological sort is not possible . " <<
std :: endl ;
78 } else {
79 std :: cout << " Topological Sort : " ;
80 g . topologicalSort () ;
81 }
82

83 return 0;
84 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append a neighbor.

• topologicalSort: O(V + E), as DFS visits each vertex and edge once.

• topologicalSortUtil: O(V + E) across all calls, as each vertex and edge is processed once.

University of Science Faculty of Information Technology Page 33

 Lab 8. GDS Data structures and Algorithms CSC10004

• hasCycle: O(V + E), as it performs a DFS with additional recursion stack tracking.

• isCyclicUtil: O(V + E) across all calls.

b) Space complexity:

• Adjacency list: O(V + E).

• Topological sort: O(V ) for visited, stack, and recursion stack.

• Cycle detection: O(V ) for visited and recStack.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 6
2 Edges : (5 ,2) , (5 ,0) , (4 ,0) , (4 ,1) , (2 ,3) , (3 ,1)

Graph visualization:
1 5 -> 2 -> 3 -> 1
2 -> 0 ^
3 4 -- -- -- -- > |

Step-by-step:

• Initialization:

– Adjacency list (adjList):

∗ adjList[0]: []
∗ adjList[1]: []
∗ adjList[2]: [3]
∗ adjList[3]: [1]
∗ adjList[4]: [0, 1]
∗ adjList[5]: [2, 0]

• Cycle Detection:

– Start at vertex 0:
∗ Set visited[0] = true, recStack[0] = true.

University of Science Faculty of Information Technology Page 34

Lab 8. GDS Data structures and Algorithms CSC10004

∗ No neighbors, set recStack[0] = false.

– Vertex 1:
∗ Set visited[1] = true, recStack[1] = true.
∗ No neighbors, set recStack[1] = false.
– Vertex 2:
∗ Set visited[2] = true, recStack[2] = true.
∗ Neighbor 3 (visited[3] = false):
· Recurse: Set visited[3] = true, recStack[3] = true.
· Neighbor 1: visited[1] = true, recStack[1] = false, no cycle.
· Set recStack[3] = false.
∗ Set recStack[2] = false.
– Vertex 4:
∗ Set visited[4] = true, recStack[4] = true.
∗ Neighbor 0: visited[0] = true, recStack[0] = false, no cycle.
∗ Neighbor 1: visited[1] = true, recStack[1] = false, no cycle.
∗ Set recStack[4] = false.
– Vertex 5:
∗ Set visited[5] = true, recStack[5] = true.
∗ Neighbor 2: visited[2] = true, recStack[2] = false, no cycle.
∗ Neighbor 0: visited[0] = true, recStack[0] = false, no cycle.
∗ Set recStack[5] = false.
– No cycles detected, proceed to topological sort.

• Topological Sort:

– Initialize: visited = [false, ..., false], stack = [].

– Start at vertex 0:
∗ Set visited[0] = true.
∗ No neighbors, push 0 to stack.
∗ stack = [0].
– Vertex 1:

University of Science Faculty of Information Technology Page 35

 Lab 8. GDS Data structures and Algorithms CSC10004

∗ Set visited[1] = true.

∗ No neighbors, push 1 to stack.
∗ stack = [0, 1].
– Vertex 2:
∗ Set visited[2] = true.
∗ Neighbor 3 (visited[3] = false):
· Recurse: Set visited[3] = true.
· Neighbor 1: visited[1] = true, skip.
· Push 3 to stack.
· stack = [0, 1, 3].
∗ Push 2 to stack.
∗ stack = [0, 1, 3, 2].
– Vertex 4:
∗ Set visited[4] = true.
∗ Neighbor 0: visited[0] = true, skip.
∗ Neighbor 1: visited[1] = true, skip.
∗ Push 4 to stack.
∗ stack = [0, 1, 3, 2, 4].
– Vertex 5:
∗ Set visited[5] = true.
∗ Neighbor 2: visited[2] = true, skip.
∗ Neighbor 0: visited[0] = true, skip.
∗ Push 5 to stack.
∗ stack = [0, 1, 3, 2, 4, 5].
– Pop stack and print: 5, 4, 2, 3, 1, 0.

Output:
1 Topological Sort : 5 4 2 3 1 0

University of Science Faculty of Information Technology Page 36

Lab 8. GDS Data structures and Algorithms CSC10004

7 Exercise 6: Connected Components

Connected components are found by performing DFS from each unvisited vertex, collecting all
vertices reachable in each DFS traversal. The adjacency list representation is efficient for sparse
graphs. Connectivity is checked by running DFS once and verifying that all vertices are visited.
Implement an algorithm to find all connected components in an undirected graph and determine
if the graph is connected. The graph is represented using an adjacency list, where each vertex stores
a list of its neighboring vertices. The implementation includes:

• Finding and printing all connected components using Depth-First Search (DFS).

• Checking if the graph is connected (i.e., has exactly one connected component).

Input:

• Number of vertices V when initializing the graph.

• A sequence of undirected edges, each specified as (src, dest).

• Requests to find connected components and check if the graph is connected.

Output:

• Connected components: A list of vertices in each connected component.

• Connectivity check: A boolean (True/False) indicating whether the graph is connected.

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is undirected, so an edge (src, dest) implies (dest, src).

• The graph is unweighted (edges have no weights).

• No parallel edges or self-loops.

Examples:

University of Science Faculty of Information Technology Page 37

 Lab 8. GDS Data structures and Algorithms CSC10004

1 Input :
2 V = 8
3 Edges : (0 ,1) , (1 ,2) , (2 ,0) , (3 ,4) , (4 ,5) , (6 ,7)
4

5 Output :
6 Connected Components :
7 Component 1: 0 1 2
8 Component 2: 3 4 5
9 Component 3: 6 7
10

11 Is the graph connected ? No

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjList : array of lists , where adjList [ i ] stores neighbors of vertex i
4

5 constructor ( vertices ) :
6 V = vertices
7 adjList = allocate V empty lists
8

9 function addEdge ( src , dest ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjList [ src ]. append ( dest )
12 adjList [ dest ]. append ( src )
13

14 function f i n d C o n n e c t e d C o m p o n e n t s () :
15 visited = array of V booleans , all false
16 componentCount = 0
17 for i from 0 to V -1:
18 if not visited [ i ]:
19 component = empty list
20 DFSUtil (i , visited , component )
21 componentCount = componentCount + 1
22 print " Component componentCount : " + component
23

24 function DFSUtil ( vertex , visited , component ) :

25 visited [ vertex ] = true
26 component . append ( vertex )
27 for each neighbor in adjList [ vertex ]:
28 if not visited [ neighbor ]:
29 DFSUtil ( neighbor , visited , component )

University of Science Faculty of Information Technology Page 38

 Lab 8. GDS Data structures and Algorithms CSC10004

30

31 function isConnected () :
32 if V == 0:
33 return true
34 visited = array of V booleans , all false
35 DFSUtil (0 , visited , empty list ) // Ignore component list
36 for i from 0 to V -1:
37 if not visited [ i ]:
38 return false
39 return true

Initial code for Exercise 06:

1 // File : Exercise_6 . cpp
2 # include < iostream >
3 # include < vector >
4

5 class Graph {
6 private :
7 int V ;
8 std :: vector < std :: vector < int > > adjList ;
9

10 public :
11 Graph ( int vertices ) : V ( vertices ) {
12 adjList . resize ( V ) ;
13 }
14

15 void addEdge ( int src , int dest ) {

16 adjList [ src ]. push_back ( dest ) ;
17 adjList [ dest ]. push_back ( src ) ; // For undirected graph
18 }
19

20 // TODO : Implement function to find all connected components

21 void f i n d C o n n e c t e d C o m p o n e n t s () {
22 // 1. Create a boolean array ’ visited ’ and mark all vertices as not
visited
23 // 2. For each unvisited vertex , call the DFS or BFS function to
explore its component
24 // 3. Print each component
25 }
26

27 // TODO : Implement DFS to explore a connected component

28 void DFSUtil ( int vertex , std :: vector < bool >& visited , std :: vector < int >&

University of Science Faculty of Information Technology Page 39

 Lab 8. GDS Data structures and Algorithms CSC10004

component ) {
29 // 1. Mark the current vertex as visited and add it to the component
30 // 2. Recursively visit all the adjacent vertices that are not visited
31 }
32

33 // Optional : Implement function to check if the graph is connected

34 bool isConnected () {
35 // 1. Start DFS from the first vertex
36 // 2. Check if all vertices are visited after the DFS
37 return false ; // Replace with your implementation
38 }
39 };
40

41 int main () {
42 Graph g (8) ; // Create a graph with 8 vertices (0 to 7)
43

44 g . addEdge (0 , 1) ;
45 g . addEdge (1 , 2) ;
46 g . addEdge (2 , 0) ;
47 g . addEdge (3 , 4) ;
48 g . addEdge (4 , 5) ;
49 g . addEdge (6 , 7) ;
50

51 std :: cout << " Connected Components : " << std :: endl ;
52 g . f i n d C o n n e c t e d C o m p o n e n t s () ;
53

54 std :: cout << " \ nIs the graph connected ? "

55 << ( g . isConnected () ? " Yes " : " No " ) << std :: endl ;
56

57 return 0;
58 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append neighbors (two operations).

• findConnectedComponents: O(V + E), as DFS visits each vertex and edge once.

• DFSUtil: O(V + E) across all calls.

University of Science Faculty of Information Technology Page 40

 Lab 8. GDS Data structures and Algorithms CSC10004

• isConnected: O(V + E) for a single DFS.

• Total for main operations: O(V + E).

b) Space complexity:

• Adjacency list: O(V + E).

• DFS: O(V ) for visited, component list, and recursion stack.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 8
2 Edges : (0 ,1) , (1 ,2) , (2 ,0) , (3 ,4) , (4 ,5) , (6 ,7) c

Graph visualization:
1 0 -- 1 3 -- 4 6 -- 7
2 \ / |
3 2 5

Step-by-step:

• Initialization:

– adjList:

adjList[0]: [1, 2]
adjList[1]: [0, 2]
adjList[2]: [0, 1]
adjList[3]: [4]
adjList[4]: [3, 5]
adjList[5]: [4]
adjList[6]: [7]
adjList[7]: [6]

• Find Connected Components:

– Initialize: visited = [false, . . . , false], componentCount = 0.

University of Science Faculty of Information Technology Page 41

Lab 8. GDS Data structures and Algorithms CSC10004

– Vertex 0: visited[0] = false.

∗ Start DFS: component = []. DFS(0): visited[0] = true, add 0 to component.
∗ Neighbor 1: visited[1] = false, recurse: visited[1] = true, add 1.
∗ Neighbor 0 (of 1): visited[0] = true, skip.
∗ Neighbor 2 (of 1): visited[2] = false, recurse: visited[2] = true, add 2.
∗ Neighbors 0, 1 (of 2): both visited, skip.
∗ Neighbor 2 (of 0): visited[2] = true, skip.
∗ Result: component = [0, 1, 2], componentCount = 1. Print: “Component 1: 0 1 2”.
– Vertex 1, 2: visited, skip.
– Vertex 3: visited[3] = false.
∗ Start DFS: component = []. DFS(3): visited[3] = true, add 3.
∗ Neighbor 4: visited[4] = false, recurse: visited[4] = true, add 4.
∗ Neighbor 3 (of 4): visited[3] = true, skip.
∗ Neighbor 5 (of 4): visited[5] = false, recurse: visited[5] = true, add 5.
∗ Neighbor 4 (of 5): visited[4] = true, skip.
∗ Result: component = [3, 4, 5], componentCount = 2. Print: “Component 2: 3 4 5”.
– Vertex 4, 5: visited, skip.
– Vertex 6: visited[6] = false.
∗ Start DFS: component = []. DFS(6): visited[6] = true, add 6.
∗ Neighbor 7: visited[7] = false, recurse: visited[7] = true, add 7.
∗ Neighbor 6 (of 7): visited[6] = true, skip.
∗ Result: component = [6, 7], componentCount = 3. Print: “Component 3: 6 7”.
– Vertex 7: visited, skip.

• Check Connectivity:

– Start DFS from vertex 0: visited = [false, . . . , false].

– DFS(0): Marks 0, 1, 2 as visited.
– Result: visited = [true, true, true, false, false, false, false, false].
– Check: Vertices 3, 4, 5, 6, 7 are unvisited.
– Return: false (graph is not connected).

University of Science Faculty of Information Technology Page 42

 Lab 8. GDS Data structures and Algorithms CSC10004

Output:
1 Connected Components :
2 Component 1: 0 1 2
3 Component 2: 3 4 5
4 Component 3: 6 7
5

6 Is the graph connected ? No

8 Exercise 7: Prim’s Algorithm

Implement Prim’s algorithm to find the Minimum Spanning Tree (MST) of a weighted, undirected
graph using an adjacency matrix representation. The MST is a subset of edges that connects all
vertices with the minimum total edge weight and contains no cycles. The graph is undirected, and
the implementation includes:

• Finding the MST using Prim’s algorithm.

• Printing the edges of the MST along with their weights and the total MST weight.

Input:

• Number of vertices V when initializing the graph.

• A sequence of undirected edges, each specified as (src, dest).

• A request to compute and display the MST.

Output:

• The MST, listed as edges with their weights.

• The total weight of the MST.

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is undirected, so an edge (src, dest, weight) implies (dest, src, weight).

• weight ≥ 1: Edge weights are positive integers.

University of Science Faculty of Information Technology Page 43

 Lab 8. GDS Data structures and Algorithms CSC10004

• The graph is connected (assumed for a valid MST).

• No parallel edges or self-loops.

Examples:
1 Input :
2 V = 5
3 Edges : (0 ,1 ,2) , (0 ,3 ,6) , (1 ,2 ,3) , (1 ,3 ,8) , (1 ,4 ,5) , (2 ,4 ,7) , (3 ,4 ,9)
4

5 Output :
6 Minimum Spanning Tree using Prim ’ s algorithm :
7 Edge Weight
8 0 - 1 2
9 1 - 2 3
10 1 - 4 5
11 0 - 3 6
12 Total MST weight : 16

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjMatrix : V x V matrix , initially 0
4

5 constructor ( vertices ) :
6 V = vertices
7 adjMatrix = allocate V x V matrix with all entries 0
8

9 function addEdge ( src , dest , weight ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjMatrix [ src ][ dest ] = weight
12 adjMatrix [ dest ][ src ] = weight
13

14 function primMST () :
15 key = array of V integers , all INFINITE
16 parent = array of V integers , all -1
17 mstSet = array of V booleans , all false
18 key [0] = 0 // Start with vertex 0
19 for count from 0 to V -1:
20 u = minKey ( key , mstSet )
21 mstSet [ u ] = true
22 for v from 0 to V -1:

University of Science Faculty of Information Technology Page 44

 Lab 8. GDS Data structures and Algorithms CSC10004

23 if adjMatrix [ u ][ v ] > 0 and not mstSet [ v ] and adjMatrix [ u ][ v ] <

key [ v ]:
24 key [ v ] = adjMatrix [ u ][ v ]
25 parent [ v ] = u
26 printMST ( parent )
27

28 function minKey ( key , mstSet ) :

29 min = INFINITE
30 min_index = -1
31 for v from 0 to V -1:
32 if not mstSet [ v ] and key [ v ] < min :
33 min = key [ v ]
34 min_index = v
35 return min_index
36

37 function printMST ( parent ) :

38 totalWeight = 0
39 print " Edge \ tWeight "
40 for i from 1 to V -1:
41 if parent [ i ] != -1:
42 print parent [ i ] + " - " + i + "\ t " + adjMatrix [ i ][ parent [ i ]]
43 totalWeight = totalWeight + adjMatrix [ i ][ parent [ i ]]
44 print " Total MST weight : " + totalWeight

Initial code for Exercise 07:

1 // File : Exercise_7 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < climits >
5

6 class Graph {
7 private :
8 int V ;
9 std :: vector < std :: vector < int > > adjMatrix ;
10

11 public :
12 Graph ( int vertices ) : V ( vertices ) {
13 adjMatrix . resize (V , std :: vector < int >( V , 0) ) ;
14 }
15

16 void addEdge ( int src , int dest , int weight ) {

17 adjMatrix [ src ][ dest ] = weight ;

University of Science Faculty of Information Technology Page 45

 Lab 8. GDS Data structures and Algorithms CSC10004

18 adjMatrix [ dest ][ src ] = weight ; // For undirected graph

19 }
20

21 // TODO : Implement Prim ’s algorithm to find MST

22 void primMST () {
23 // 1. Create arrays to keep track of the MST :
24 // - key []: Key values used to pick minimum weight edge
25 // - parent []: Array to store the MST
26 // - mstSet []: To represent vertices included in MST
27

28 // 2. Initialize key values as INFINITE and mstSet as false

29

30 // 3. Always include the first vertex in MST , set its key as 0

31

32 // 4. While not all vertices are included in the MST :

33 // a . Pick the vertex with minimum key value that is not yet
included
34 // b . Include the picked vertex in the MST
35 // c . Update key and parent values of adjacent vertices
36

37 // 5. Print the MST

38 }
39

40 // TODO : Implement function to find the vertex with minimum key value
41 int minKey ( const std :: vector < int >& key , const std :: vector < bool >& mstSet ) {
42 int min = INT_MAX , min_index = -1;
43

44 // Find the vertex with the minimum key value

45

46 return min_index ;
47 }
48

49 // TODO : Implement function to print the MST

50 void printMST ( const std :: vector < int >& parent ) {
51 std :: cout << " Edge \ tWeight \ n " ;
52 int totalWeight = 0;
53

54 // Print each edge and its weight in the MST

55

56 std :: cout << " Total MST weight : " << totalWeight << std :: endl ;
57 }
58 };

University of Science Faculty of Information Technology Page 46

 Lab 8. GDS Data structures and Algorithms CSC10004

59

60 int main () {
61 Graph g (5) ; // Create a graph with 5 vertices (0 to 4)
62

63 g . addEdge (0 , 1, 2) ;
64 g . addEdge (0 , 3, 6) ;
65 g . addEdge (1 , 2, 3) ;
66 g . addEdge (1 , 3, 8) ;
67 g . addEdge (1 , 4, 5) ;
68 g . addEdge (2 , 4, 7) ;
69 g . addEdge (3 , 4, 9) ;
70

71 std :: cout << " Minimum Spanning Tree using Prim ’s algorithm : " << std :: endl ;
72 g . primMST () ;
73

74 return 0;
75 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append neighbors (two operations).

• primMST:

– Loop runs V times.

– minKey: O(V ) per call, O(V 2 ) total.
– Inner loop to update keys: O(V ) per iteration, O(V 2 ) total.
– Total: O(V 2 ).

• minKey: O(V ) to scan the key array.

• printMST: O(V ) to print edges.

• Overall: O(V 2 ) for Prim’s algorithm with an adjacency matrix.

b) Space complexity:

• Adjacency list: O(V + E).

University of Science Faculty of Information Technology Page 47

 Lab 8. GDS Data structures and Algorithms CSC10004

• Prim’s algorithm: O(V ) for key, parent, and mstSet.

• Total: O(V 2 ).

Example Walkthrough
Input:
1 V = 5
2 Edges : (0 ,1 ,2) , (0 ,3 ,6) , (1 ,2 ,3) , (1 ,3 ,8) , (1 ,4 ,5) , (2 ,4 ,7) , (3 ,4 ,9)

Graph visualization:
1 0
2 2/ \6
3 1 - - -3
4 | 8/|
5 5| /9|
6 4 - - -2
7 7

Adjacency matrix:
1 0 1 2 3 4
2 0 [0 , 2, 0, 6, 0]
3 1 [2 , 0, 3, 8, 5]
4 2 [0 , 3, 0, 0, 7]
5 3 [6 , 8, 0, 0, 9]
6 4 [0 , 5, 7, 9, 0]

Step-by-step:

• Initialization:

– key = [∞, ∞, ∞, ∞, ∞], parent = [−1, −1, −1, −1, −1], mstSet = [false, . . . , false].
– Set key[0] = 0 (start with vertex 0).

• Iteration 1:

– u = minKey([0, ∞, ∞, ∞, ∞], [false, . . .]) = 0.

– mstSet[0] = true.
– Update keys for neighbors (1, 3):
∗ adjMatrix[0][1] = 2 < key[1] = ∞: key[1] = 2, parent[1] = 0.
∗ adjMatrix[0][3] = 6 < key[3] = ∞: key[3] = 6, parent[3] = 0.

University of Science Faculty of Information Technology Page 48

Lab 8. GDS Data structures and Algorithms CSC10004

– key = [0, 2, ∞, 6, ∞], parent = [−1, 0, −1, 0, −1].

• Iteration 2:

– u = minKey([0, 2, ∞, 6, ∞], [true, false, . . .]) = 1.

– mstSet[1] = true.
– Update keys for neighbors (0, 2, 3, 4):
∗ 0: mstSet[0] = true, skip.
∗ adjMatrix[1][2] = 3 < key[2] = ∞: key[2] = 3, parent[2] = 1.
∗ adjMatrix[1][3] = 8 < key[3] = 6: No update.
∗ adjMatrix[1][4] = 5 < key[4] = ∞: key[4] = 5, parent[4] = 1.
– key = [0, 2, 3, 6, 5], parent = [−1, 0, 1, 0, 1].

• Iteration 3:

– u = minKey([0, 2, 3, 6, 5], [true, true, false, false, false]) = 2.

– mstSet[2] = true.
– Update keys for neighbors (1, 4):
∗ 1: mstSet[1] = true, skip.
∗ adjMatrix[2][4] = 7 < key[4] = 5: No update.
– key = [0, 2, 3, 6, 5], parent = [−1, 0, 1, 0, 1].

• Iteration 4:

– u = minKey([0, 2, 3, 6, 5], [true, true, true, false, false]) = 4.

– mstSet[4] = true.
– Update keys for neighbors (1, 2, 3):
∗ 1, 2: mstSet = true, skip.
∗ adjMatrix[4][3] = 9 < key[3] = 6: No update.
– key = [0, 2, 3, 6, 5], parent = [−1, 0, 1, 0, 1].

• Iteration 5:

– u = minKey([0, 2, 3, 6, 5], [true, true, true, false, true]) = 3.

University of Science Faculty of Information Technology Page 49

 Lab 8. GDS Data structures and Algorithms CSC10004

– mstSet[3] = true.
– Update keys for neighbors (0, 1, 4): All mstSet = true, skip.
– key = [0, 2, 3, 6, 5], parent = [−1, 0, 1, 0, 1].

• Print MST:

– Edges (from parent):

∗ Vertex 1: parent[1] = 0, edge 0-1, weight = 2.
∗ Vertex 2: parent[2] = 1, edge 1-2, weight = 3.
∗ Vertex 3: parent[3] = 0, edge 0-3, weight = 6.
∗ Vertex 4: parent[4] = 1, edge 1-4, weight = 5.
– Total weight: 2 + 3 + 6 + 5 = 16.

Output:
1 Minimum Spanning Tree using Prim ’ s algorithm :
2 Edge Weight
3 0 - 1 2
4 1 - 2 3
5 1 - 4 5
6 0 - 3 6
7 Total MST weight : 16

9 Exercise 8: Optimized Prim’s Algorithm

Implement an optimized version of Prim’s algorithm to find the Minimum Spanning Tree (MST)
of a weighted, undirected graph using an adjacency list and a priority queue. The MST is a subset
of edges that connects all vertices with the minimum total edge weight and contains no cycles.
The optimization uses a priority queue to efficiently select the minimum-weight edge, improving
performance for sparse graphs compared to an adjacency matrix approach.
Input:

• Number of vertices V when initializing the graph.

• A sequence of undirected edges, each specified as (src, dest).

• A request to compute and display the MST.

University of Science Faculty of Information Technology Page 50

 Lab 8. GDS Data structures and Algorithms CSC10004

Output:

• The MST, listed as edges with their weights.

• The total weight of the MST.

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is undirected, so an edge (src, dest, weight) implies (dest, src, weight).

• weight ≥ 1: Edge weights are positive integers.

• The graph is connected (assumed for a valid MST).

• No parallel edges or self-loops.

Examples:
1 Input :
2 V = 9
3 Edges : (0 ,1 ,4) , (0 ,7 ,8) , (1 ,2 ,8) , (1 ,7 ,11) , (2 ,3 ,7) , (2 ,8 ,2) , (2 ,5 ,4) , (3 ,4 ,9) ,
(3 ,5 ,14) , (4 ,5 ,10) , (5 ,6 ,2) , (6 ,7 ,1) , (6 ,8 ,6) , (7 ,8 ,7)
4

5 Output :
6 Minimum Spanning Tree using optimized Prim ’ s algorithm :
7 Edge Weight
8 0 - 1 4
9 1 - 2 8
10 2 - 3 7
11 2 - 5 4
12 2 - 8 2
13 5 - 6 2
14 6 - 7 1
15 3 - 4 9
16 Total MST weight : 37

Pseudocode:
1 struct Edge :
2 dest : destination vertex
3 weight : edge weight

University of Science Faculty of Information Technology Page 51

 Lab 8. GDS Data structures and Algorithms CSC10004

5 class Graph :
6 V : number of vertices
7 adjList : array of lists , where adjList [ i ] stores edges from vertex i
8

9 constructor ( vertices ) :
10 V = vertices
11 adjList = allocate V empty lists
12

13 function addEdge ( src , dest , weight ) :

14 if src >= 0 and src < V and dest >= 0 and dest < V :
15 adjList [ src ]. append ( Edge ( dest , weight ) )
16 adjList [ dest ]. append ( Edge ( src , weight ) )
17

18 function primMST () :
19 key = array of V integers , all INFINITE
20 parent = array of V integers , all -1
21 inMST = array of V booleans , all false
22 pq = min - heap priority queue of ( weight , vertex ) pairs
23 key [0] = 0
24 pq . push ((0 , 0) ) // Start with vertex 0
25 while pq is not empty :
26 u = pq . top () . vertex
27 pq . pop ()
28 if inMST [ u ]:
29 continue
30 inMST [ u ] = true
31 for each edge (v , w ) in adjList [ u ]:
32 if not inMST [ v ] and w < key [ v ]:
33 key [ v ] = w
34 parent [ v ] = u
35 pq . push (( w , v ) )
36 printMST ( parent )
37

38 function printMST ( parent ) :

39 totalWeight = 0
40 print " Edge \ tWeight "
41 for i from 0 to V -1:
42 if parent [ i ] != -1:
43 for each edge (j , w ) in adjList [ i ]:
44 if j == parent [ i ]:
45 print parent [ i ] + " - " + i + "\ t " + w

University of Science Faculty of Information Technology Page 52

 Lab 8. GDS Data structures and Algorithms CSC10004

46 totalWeight = totalWeight + w
47 break
48 print " Total MST weight : " + totalWeight

Initial code for Exercise 08:

1 // File : Exercise_8 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < queue >
5 # include < utility > // for std :: pair
6

7 struct Edge {
8 int dest ;
9 int weight ;
10

11 Edge ( int d , int w ) : dest ( d ) , weight ( w ) {}

12 };
13

14 class Graph {
15 private :
16 int V ;
17 std :: vector < std :: vector < Edge > > adjList ;
18

19 public :
20 Graph ( int vertices ) : V ( vertices ) {
21 adjList . resize ( V ) ;
22 }
23

24 void addEdge ( int src , int dest , int weight ) {

25 adjList [ src ]. push_back ( Edge ( dest , weight ) ) ;
26 adjList [ dest ]. push_back ( Edge ( src , weight ) ) ; // For undirected graph
27 }
28

29 // TODO : Implement optimized Prim ’s algorithm using priority queue

30 void primMST () {
31 // 1. Create a priority queue to store vertices and their key values
32 // Use std :: pair < int , int > where first is the weight and second is
the vertex
33

34 // 2. Create vectors for tracking the MST :

35 // - key []: Key values used to pick minimum weight edge
36 // - parent []: Array to store the MST

University of Science Faculty of Information Technology Page 53

 Lab 8. GDS Data structures and Algorithms CSC10004

37 // - inMST []: To represent vertices included in MST

38

39 // 3. Initialize key values as INFINITE and inMST as false

40

41 // 4. Insert the first vertex into the priority queue with key value 0
42

43 // 5. While the priority queue is not empty :

44 // a . Extract the minimum key vertex from the priority queue
45 // b . Include the extracted vertex in the MST
46 // c . For all adjacent vertices , update key values and insert into
the queue if needed
47

48 // 6. Print the MST

49 }
50

51 // TODO : Implement function to print the MST

52 void printMST ( const std :: vector < int >& parent ) {
53 std :: cout << " Edge \ tWeight \ n " ;
54 int totalWeight = 0;
55

56 // Print each edge and its weight in the MST

57

58 std :: cout << " Total MST weight : " << totalWeight << std :: endl ;
59 }
60 };
61

62 int main () {
63 Graph g (9) ; // Create a graph with 9 vertices (0 to 8)
64

65 g . addEdge (0 , 1, 4) ;
66 g . addEdge (0 , 7, 8) ;
67 g . addEdge (1 , 2, 8) ;
68 g . addEdge (1 , 7, 11) ;
69 g . addEdge (2 , 3, 7) ;
70 g . addEdge (2 , 8, 2) ;
71 g . addEdge (2 , 5, 4) ;
72 g . addEdge (3 , 4, 9) ;
73 g . addEdge (3 , 5, 14) ;
74 g . addEdge (4 , 5, 10) ;
75 g . addEdge (5 , 6, 2) ;
76 g . addEdge (6 , 7, 1) ;
77 g . addEdge (6 , 8, 6) ;

University of Science Faculty of Information Technology Page 54

 Lab 8. GDS Data structures and Algorithms CSC10004

78 g . addEdge (7 , 8 , 7) ;
79

80 std :: cout << " Minimum Spanning Tree using optimized Prim ’s algorithm : " <<
std :: endl ;
81 g . primMST () ;
82

83 return 0;
84 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append neighbors (two operations).

• primMST:

– Priority queue operations

∗ Up to V insertions: O(log V ) each, O(V log V ) total.
∗ Up to 2E extractions (each edge may be considered twice): O(log V ) each, O(E log V )
total.
– Iterating edges: O(E) across all vertices.
– Total: O(E log V ), assuming E ≥ V .

• O(E log V ) for Prim’s algorithm with a priority queue and adjacency list.

b) Space complexity:

• Adjacency list: O(V + E).

• Prim’s algorithm: O(V ) for key, parent, inMST, and O(V ) for the priority queue.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 9
2 Edges : (0 ,1 ,4) , (0 ,7 ,8) , (1 ,2 ,8) , (1 ,7 ,11) , (2 ,3 ,7) , (2 ,8 ,2) , (2 ,5 ,4) , (3 ,4 ,9) ,
(3 ,5 ,14) , (4 ,5 ,10) , (5 ,6 ,2) , (6 ,7 ,1) , (6 ,8 ,6) , (7 ,8 ,7)

University of Science Faculty of Information Technology Page 55

 Lab 8. GDS Data structures and Algorithms CSC10004

Graph visualization:
1 0 - - -4 - - -1
2 | | \
3 8 8 11
4 | | \
5 7 - - -1 - - -6 2 - - -8
6 | /| | | \ |
7 7 / 6 2 7 \4
8 |/ | | \
9 8 - - -2 - - -5 - - -14 - - - -3
10 | |
11 10 9
12 | |
13 4 - - - - - - - - -3

Adjacency matrix:
1 0: [(1 ,4) , (7 ,8) ]
2 1: [(0 ,4) , (2 ,8) , (7 ,11) ]
3 2: [(1 ,8) , (3 ,7) , (8 ,2) , (5 ,4) ]
4 3: [(2 ,7) , (4 ,9) , (5 ,14) ]
5 4: [(3 ,9) , (5 ,10) ]
6 5: [(2 ,4) , (3 ,14) , (4 ,10) , (6 ,2) ]
7 6: [(5 ,2) , (7 ,1) , (8 ,6) ]
8 7: [(0 ,8) , (1 ,11) , (6 ,1) , (8 ,7) ]
9 8: [(2 ,2) , (6 ,6) , (7 ,7) ]

Step-by-step:

• Initialization:

– key = [∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞].

– parent = [−1, −1, −1, −1, −1, −1, −1, −1, −1].
– inMST = [false, . . . , false].
– pq = [].
– Set key[0] = 0, push (0, 0) to pq.

• Priority Queue Processing:

– Extract (0, 0), vertex 0: inMST[0] = true. Neighbors: (1,4), (7,8). Updates: key[1] = 4,
parent[1] = 0, push (4, 1); key[7] = 8, parent[7] = 0, push (8, 7). pq = [(4, 1), (8, 7)].

University of Science Faculty of Information Technology Page 56

Lab 8. GDS Data structures and Algorithms CSC10004

– Extract (4, 1), vertex 1: inMST[1] = true. Neighbors: (0,4), (2,8), (7,11). Skip 0
(inMST[0] = true). Updates: key[2] = 8, parent[2] = 1, push (8, 2); skip 7 (11 ¿ 8).
pq = [(8, 2), (8, 7)].
– Extract (8, 2), vertex 2: inMST[2] = true. Neighbors: (1,8), (3,7), (8,2), (5,4). Skip 1.
Updates: key[3] = 7, parent[3] = 2, push (7, 3); key[8] = 2, parent[8] = 2, push (2, 8);
key[5] = 4, parent[5] = 2, push (4, 5). pq = [(2, 8), (8, 7), (7, 3), (4, 5)].
– Extract (2, 8), vertex 8: inMST[8] = true. Neighbors: (2,2), (6,6), (7,7). Skip 2.
Updates: key[6] = 6, parent[6] = 8, push (6, 6); key[7] = 7, parent[7] = 8, push (7, 7).
pq = [(4, 5), (6, 6), (7, 3), (8, 7), (7, 7)].
– Extract (4, 5), vertex 5: inMST[5] = true. Neighbors: (2,4), (3,14), (4,10), (6,2). Skip
2. Updates: key[4] = 10, parent[4] = 5, push (10, 4); key[6] = 2, parent[6] = 5, push
(2, 6). pq = [(2, 6), (6, 6), (7, 3), (8, 7), (7, 7), (10, 4)].
– Extract (2, 6), vertex 6: inMST[6] = true. Neighbors: (5,2), (7,1), (8,6). Skip 5, 8. Up-
date: key[7] = 1, parent[7] = 6, push (1, 7). pq = [(1, 7), (6, 6), (7, 3), (8, 7), (7, 7), (10, 4)].
– Extract (1, 7), vertex 7: inMST[7] = true. Neighbors: (0,8), (1,11), (6,1), (8,7). Skip 0,
1, 6, 8. pq = [(6, 6), (7, 3), (10, 4), (8, 7), (7, 7)].
– Extract (6, 6): Vertex 6 in MST, skip.
– Extract (7, 3), vertex 3: inMST[3] = true. Neighbors: (2,7), (4,9), (5,14). Skip 2, 5.
Update: key[4] = 9, parent[4] = 3, push (9, 4). pq = [(7, 7), (8, 7), (10, 4), (9, 4)].
– Extract (7, 7): Vertex 7 in MST, skip.
– Extract (8, 7): Vertex 7 in MST, skip.
– Extract (9, 4), vertex 4: inMST[4] = true. Neighbors: (3,9), (5,10). Skip 3, 5. pq =
[(10, 4)].
– Extract (10, 4): Vertex 4 in MST, skip.

• Final State:

– parent = [−1, 0, 1, 2, 3, 2, 5, 6, 2].

– inMST = [true, true, true, true, true, true, true, true, true].

• Print MST:

– Edges (from parent):

University of Science Faculty of Information Technology Page 57

 Lab 8. GDS Data structures and Algorithms CSC10004

∗ Vertex 1: parent[1] = 0, edge 0-1, weight = 4.

∗ Vertex 2: parent[2] = 1, edge 1-2, weight = 8.
∗ Vertex 3: parent[3] = 2, edge 2-3, weight = 7.
∗ Vertex 4: parent[4] = 3, edge 3-4, weight = 9.
∗ Vertex 5: parent[5] = 2, edge 2-5, weight = 4.
∗ Vertex 6: parent[6] = 5, edge 5-6, weight = 2.
∗ Vertex 7: parent[7] = 6, edge 6-7, weight = 1.
∗ Vertex 8: parent[8] = 2, edge 2-8, weight = 2.
– Total weight: 4 + 8 + 7 + 9 + 4 + 2 + 1 + 2 = 37.

Output:
1 Minimum Spanning Tree using Prim ’ s algorithm :
2 Edge Weight
3 0 - 1 2
4 1 - 2 3
5 1 - 4 5
6 0 - 3 6
7 Total MST weight : 16

10 Exercise 9: Dijkstra’s Algorithm

Implement Dijkstra’s algorithm to find the shortest path from a source vertex to all other vertices in
a weighted directed graph using an adjacency matrix representation. The graph may have negative
weights, which Dijkstra’s algorithm does not handle correctly, so we must note this limitation. The
implementation computes the shortest path distances from a given source vertex and prints them.
Input:

• Number of vertices V when initializing the graph.

• A sequence of directed edges, each specified as (src, dest, weight).

• A source vertex to compute shortest paths from.

Output:

• A table listing each vertex and its shortest path distance from the source.

University of Science Faculty of Information Technology Page 58

 Lab 8. GDS Data structures and Algorithms CSC10004

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is directed, so an edge (src, dest, weight) does not imply (dest, src, weight).

• weight: Edge weights are positive.

• No parallel edges or self-loops.

• The graph is assumed to be connected for meaningful paths.

Examples:
1 Input :
2 V = 6
3 Edges : (0 ,1 ,5) , (0 ,2 ,3) , (1 ,3 ,6) , (1 ,2 ,2) , (2 ,3 ,7) , (2 ,4 ,4) , (2 ,5 ,2) , (3 ,4 ,1) ,
(4 ,5 ,2)
4 Source : 0
5

6 Output :
7 Shortest paths from vertex 0 using Dijkstra ’ s algorithm :
8 Vertex Distance from Source
9 0 0
10 1 5
11 2 3
12 3 10
13 4 7
14 5 5

Pseudocode:
1 class Graph :
2 V : number of vertices
3 adjMatrix : V x V matrix , initially 0
4

5 constructor ( vertices ) :
6 V = vertices
7 adjMatrix = allocate V x V matrix with all entries 0
8

9 function addEdge ( src , dest , weight ) :

10 if src >= 0 and src < V and dest >= 0 and dest < V :
11 adjMatrix [ src ][ dest ] = weight

University of Science Faculty of Information Technology Page 59

 Lab 8. GDS Data structures and Algorithms CSC10004

12

13 function dijkstra ( source ) :

14 if source < 0 or source >= V :
15 return
16 dist = array of V integers , all INFINITE
17 sptSet = array of V booleans , all false
18 dist [ source ] = 0
19 for count from 0 to V -1:
20 u = minDistance ( dist , sptSet )
21 if u == -1:
22 break // No reachable vertices left
23 sptSet [ u ] = true
24 for v from 0 to V -1:
25 if not sptSet [ v ] and adjMatrix [ u ][ v ] > 0 and dist [ u ] !=
INFINITE and dist [ u ] + adjMatrix [ u ][ v ] < dist [ v ]:
26 dist [ v ] = dist [ u ] + adjMatrix [ u ][ v ]
27 printSolution ( dist )
28

29 function minDistance ( dist , sptSet ) :

30 min = INFINITE
31 min_index = -1
32 for v from 0 to V -1:
33 if not sptSet [ v ] and dist [ v ] < min :
34 min = dist [ v ]
35 min_index = v
36 return min_index
37

38 function printSolution ( dist ) :

39 print " Vertex \ tDistance from Source "
40 for i from 0 to V -1:
41 if dist [ i ] == INFINITE :
42 print i + "\ t " + " INF "
43 else :
44 print i + "\ t " + dist [ i ]

Initial code for Exercise 09:

1 // File : Exercise_9 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < climits >
5

6 class Graph {

University of Science Faculty of Information Technology Page 60

 Lab 8. GDS Data structures and Algorithms CSC10004

7 private :
8 int V ;
9 std :: vector < std :: vector < int > > adjMatrix ;
10

11 public :
12 Graph ( int vertices ) : V ( vertices ) {
13 adjMatrix . resize (V , std :: vector < int >( V , 0) ) ;
14 }
15

16 void addEdge ( int src , int dest , int weight ) {

17 adjMatrix [ src ][ dest ] = weight ;
18 }
19

20 // TODO : Implement Dijkstra ’s algorithm

21 void dijkstra ( int source ) {
22 // 1. Create arrays to store the shortest distance and whether a vertex
is finalized
23 // - dist []: Shortest distance from source to i
24 // - sptSet []: True if vertex i is included in shortest path tree
25

26 // 2. Initialize all distances as INFINITE and sptSet as false

27

28 // 3. Set distance of source vertex as 0

29

30 // 4. Find shortest path for all vertices :

31 // a . Pick the vertex with minimum distance that is not yet
processed
32 // b . Mark the picked vertex as processed
33 // c . Update dist [] values of adjacent vertices
34

35 // 5. Print the shortest distances

36 }
37

38 // TODO : Implement function to find the vertex with the minimum distance
39 int minDistance ( const std :: vector < int >& dist , const std :: vector < bool >&
sptSet ) {
40 int min = INT_MAX , min_index = -1;
41

42 // Find the vertex with the minimum distance value

43

44 return min_index ;
45 }

University of Science Faculty of Information Technology Page 61

 Lab 8. GDS Data structures and Algorithms CSC10004

46

47 // TODO : Implement function to print the shortest distances

48 void printSolution ( const std :: vector < int >& dist ) {
49 std :: cout << " Vertex \ tDistance from Source \ n " ;
50

51 // Print each vertex and its distance from the source

52 }
53 };
54

55 int main () {
56 Graph g (6) ; // Create a graph with 6 vertices (0 to 5)
57

58 g . addEdge (0 , 1, 5) ;
59 g . addEdge (0 , 2, 3) ;
60 g . addEdge (1 , 3, 6) ;
61 g . addEdge (1 , 2, 2) ;
62 g . addEdge (2 , 3, 7) ;
63 g . addEdge (2 , 4, 4) ;
64 g . addEdge (2 , 5, 2) ;
65 g . addEdge (3 , 4, -1) ;
66 g . addEdge (4 , 5, -2) ;
67

68 int source = 0;
69 std :: cout << " Shortest paths from vertex " << source << " using Dijkstra ’s
algorithm : " << std :: endl ;
70 g . dijkstra ( source ) ;
71

72 return 0;
73 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append neighbors (two operations).

• dijkstra:

– Initialization: O(V ).
– Loop runs V times:
∗ minDistance: O(V ) per call, O(V 2 ) total.

University of Science Faculty of Information Technology Page 62

 Lab 8. GDS Data structures and Algorithms CSC10004

∗ Neighbor updates: O(V ) per iteration, O(V 2 ) total.

– Total: O(V 2 ).

• minDistance: O(V ) to scan the distance array.

• Overall: O(V 2 ) for Dijkstra’s algorithm with an adjacency matrix.

b) Space complexity:

• Adjacency matrix: O(V 2 ).

• Dijkstra’s algorithm: O(V ) for dist and sptSet.

• Total: O(V 2 ).

Example Walkthrough
Input:
1 V = 6
2 Edges : (0 ,1 ,5) , (0 ,2 ,3) , (1 ,3 ,6) , (1 ,2 ,2) , (2 ,3 ,7) , (2 ,4 ,4) , (2 ,5 ,2) , (3 ,4 ,1) ,
(4 ,5 ,2)
3 Source : 0

Graph visualization:
1 0 - - - -5 - - - - > 1
2 | |
3 3 2
4 | |
5 v v
6 2 - - - -7 - - - - > 3
7 | |
8 4 1
9 | |
10 v v
11 5 < - - -2 - - - - 4

Adjacency matrix:
1 0 1 2 3 4 5
2 0 [0 , 5, 3, 0, 0, 0]
3 1 [0 , 0, 2, 6, 0, 0]
4 2 [0 , 0, 0, 7, 4, 2]
5 3 [0 , 0, 0, 0, 1, 0]
6 4 [0 , 0, 0, 0, 0, 2]
7 5 [0 , 0, 0, 0, 0, 0]

University of Science Faculty of Information Technology Page 63

Lab 8. GDS Data structures and Algorithms CSC10004

Step-by-step:

• Initialization:

– dist = [∞, ∞, ∞, ∞, ∞, ∞].

– sptSet = [false, false, false, false, false, false].
– Set dist[0] = 0.

• Iteration 1:

– Select u = minDistance([0, ∞, ∞, ∞, ∞, ∞], [false, . . .]) = 0.

– Set sptSet[0] = true.
– Process neighbors (1,5), (2,3): Update dist[1] = 5, dist[2] = 3.
– Result: dist = [0, 5, 3, ∞, ∞, ∞].

• Iteration 2:

– Select u = minDistance([0, 5, 3, ∞, ∞, ∞], [true, false, . . .]) = 2.

– Set sptSet[2] = true.
– Process neighbors (3,7), (4,4), (5,2): Update dist[3] = 10, dist[4] = 7, dist[5] = 5.
– Result: dist = [0, 5, 3, 10, 7, 5].

• Iteration 3:

– Select u = minDistance([0, 5, 3, 10, 7, 5], [true, false, true, false, false, false]) = 1
(tie with 5, pick first).
– Set sptSet[1] = true.
– Process neighbors (2,2), (3,6): Skip 2 (sptSet[2] = true); no update for 3 (5 + 6 =
11 > 10).
– Result: dist = [0, 5, 3, 10, 7, 5].

• Iteration 4:

– Select u = minDistance([0, 5, 3, 10, 7, 5], [true, true, true, false, false, false]) = 5.
– Set sptSet[5] = true.
– No neighbors to process.

University of Science Faculty of Information Technology Page 64

 Lab 8. GDS Data structures and Algorithms CSC10004

– Result: dist = [0, 5, 3, 10, 7, 5].

• Iteration 5:

– Select u = minDistance([0, 5, 3, 10, 7, 5], [true, true, true, false, false, true]) = 4.
– Set sptSet[4] = true.
– Process neighbors (5,2): Skip 5 (sptSet[5] = true).
– Result: dist = [0, 5, 3, 10, 7, 5].

• Iteration 6:

– Select u = minDistance([0, 5, 3, 10, 7, 5], [true, true, true, false, true, true]) = 3.
– Set sptSet[3] = true.
– Process neighbors (4,1): Skip 4 (sptSet[4] = true).
– Result: dist = [0, 5, 3, 10, 7, 5].

Output:
1 Vertex Distance from Source
2 0 0
3 1 5
4 2 3
5 3 10
6 4 7
7 5 5

11 Exercise 10: Optimized Dijkstra’s Algorithm

Implement an optimized version of Dijkstra’s algorithm to find the shortest path from a source
vertex to all other vertices in a weighted directed graph using an adjacency list and a priority
queue. The optimization leverages a min-heap priority queue to efficiently select the vertex with
the minimum distance, improving performance for sparse graphs compared to an adjacency matrix
approach. The implementation computes shortest path distances and paths from a given source
vertex and prints them.
Input:

• Number of vertices V when initializing the graph.

University of Science Faculty of Information Technology Page 65

 Lab 8. GDS Data structures and Algorithms CSC10004

• A sequence of directed edges, each specified as (src, dest, weight).

• A source vertex to compute shortest paths from.

Output:

• A table listing each vertex and its shortest path distance from the source.

Constraints:

• 1 ≤ V ≤ 105 : Number of vertices (though the example uses small V ).

• 0 ≤ src, dest < V : Vertex indices.

• The graph is directed, so an edge (src, dest, weight) does not imply (dest, src, weight).

• weight: Edge weights are positive.

• No parallel edges or self-loops.

• The graph is assumed to be connected for meaningful paths.

• The graph may not be connected, so some vertices may be unreachable.

Examples:
1 Input :
2 V = 6
3 Edges : (0 ,1 ,5) , (0 ,2 ,3) , (1 ,3 ,6) , (1 ,2 ,2) , (2 ,3 ,7) , (2 ,4 ,4) , (2 ,5 ,2) , (3 ,4 ,1) ,
(4 ,5 ,2)
4 Source : 0
5

6 Output :
7 Shortest paths from vertex 0 using optimized Dijkstra ’ s algorithm :
8 Vertex Distance Path
9 0 0 0
10 1 5 0 -> 1
11 2 3 0 -> 2
12 3 10 0 -> 2 -> 3
13 4 7 0 -> 2 -> 4
14 5 5 0 -> 2 -> 5

Note that: the example uses positive edge weights (weight ≥ 1), ensuring Dijkstra’s algorithm
produces correct results. The implementation is optimized for sparse graphs using an adjacency
list and a min-heap priority queue.
Pseudocode:

University of Science Faculty of Information Technology Page 66

 Lab 8. GDS Data structures and Algorithms CSC10004

1 struct Edge :
2 dest : destination vertex
3 weight : edge weight
4

5 class Graph :
6 V : number of vertices
7 adjList : array of lists , where adjList [ i ] stores edges from vertex i
8

9 constructor ( vertices ) :
10 V = vertices
11 adjList = allocate V empty lists
12

13 function addEdge ( src , dest , weight ) :

14 if src >= 0 and src < V and dest >= 0 and dest < V :
15 adjList [ src ]. append ( Edge ( dest , weight ) )
16

17 function dijkstra ( source ) :

18 if source < 0 or source >= V :
19 return
20 dist = array of V integers , all INFINITE
21 parent = array of V integers , all -1
22 visited = array of V booleans , all false
23 pq = min - heap priority queue of ( distance , vertex ) pairs
24 dist [ source ] = 0
25 parent [ source ] = -1
26 pq . push ((0 , source ) )
27 while pq is not empty :
28 d = pq . top () . distance
29 u = pq . top () . vertex
30 pq . pop ()
31 if visited [ u ]:
32 continue
33 visited [ u ] = true
34 for each edge (v , w ) in adjList [ u ]:
35 if not visited [ v ] and dist [ u ] + w < dist [ v ]:
36 dist [ v ] = dist [ u ] + w
37 parent [ v ] = u
38 pq . push (( dist [ v ] , v ) )
39 printPaths ( dist , parent )
40

41 function printPaths ( dist , parent ) :

42 print " Vertex \ tDistance \ tPath "

University of Science Faculty of Information Technology Page 67

 Lab 8. GDS Data structures and Algorithms CSC10004

43 for i from 0 to V -1:

44 if dist [ i ] == INFINITE :
45 print i + "\ tINF \ t \t -"
46 else :
47 print i + "\ t " + dist [ i ] + "\ t \ t "
48 printPath ( parent , i )
49

50 function printPath ( parent , dest ) :

51 if parent [ dest ] == -1:
52 print dest
53 return
54 printPath ( parent , parent [ dest ])
55 print " -> " + dest

Initial code for Exercise 10:

1 // File : Exercise_10 . cpp
2 # include < iostream >
3 # include < vector >
4 # include < queue >
5 # include < utility > // for std :: pair
6 # include < climits >
7

8 struct Edge {
9 int dest ;
10 int weight ;
11

12 Edge ( int d , int w ) : dest ( d ) , weight ( w ) {}

13 };
14

15 class Graph {
16 private :
17 int V ;
18 std :: vector < std :: vector < Edge > > adjList ;
19

20 public :
21 Graph ( int vertices ) : V ( vertices ) {
22 adjList . resize ( V ) ;
23 }
24

25 void addEdge ( int src , int dest , int weight ) {

26 adjList [ src ]. push_back ( Edge ( dest , weight ) ) ;
27 }

University of Science Faculty of Information Technology Page 68

 Lab 8. GDS Data structures and Algorithms CSC10004

28

29 // TODO : Implement optimized Dijkstra ’s algorithm using priority queue

30 void dijkstra ( int source ) {
31 // 1. Create a priority queue to store vertices and their distances
32 // Use std :: pair < int , int > where first is the distance and second is
the vertex
33

34 // 2. Create vectors for tracking :

35 // - dist []: Shortest distance from source to i
36 // - parent []: Parent of vertex i in the shortest path
37 // - visited []: To track processed vertices
38

39 // 3. Initialize all distances as INFINITE and visited as false

40

41 // 4. Set distance of source vertex as 0 and push it into the priority

queue
42

43 // 5. While the priority queue is not empty :

44 // a . Extract the minimum distance vertex from the priority queue
45 // b . If the vertex is already visited , skip it
46 // c . Mark the vertex as visited
47 // d . Update distances of adjacent vertices if there is a shorter
path
48

49 // 6. Print the shortest paths

50 }
51

52 // TODO : Implement function to print the shortest paths

53 void printPaths ( const std :: vector < int >& dist , const std :: vector < int >&
parent ) {
54 std :: cout << " Vertex \ tDistance \ tPath " << std :: endl ;
55

56 // For each vertex , print its distance and path from the source
57 }
58

59 // Helper function to print path from source to destination

60 void printPath ( const std :: vector < int >& parent , int dest ) {
61 if ( parent [ dest ] == -1) {
62 std :: cout << dest ;
63 return ;
64 }
65 printPath ( parent , parent [ dest ]) ;

University of Science Faculty of Information Technology Page 69

 Lab 8. GDS Data structures and Algorithms CSC10004

66 std :: cout << " -> " << dest ;

67 }
68 };
69

70 int main () {
71 Graph g (6) ; // Create a graph with 6 vertices (0 to 5)
72

73 g . addEdge (0 , 1, 5) ;
74 g . addEdge (0 , 2, 3) ;
75 g . addEdge (1 , 3, 6) ;
76 g . addEdge (1 , 2, 2) ;
77 g . addEdge (2 , 3, 7) ;
78 g . addEdge (2 , 4, 4) ;
79 g . addEdge (2 , 5, 2) ;
80 g . addEdge (3 , 4, 1) ;
81 g . addEdge (4 , 5, 2) ;
82

83 int source = 0;
84 std :: cout << " Shortest paths from vertex " << source << " using optimized
Dijkstra ’s algorithm : " << std :: endl ;
85 g . dijkstra ( source ) ;
86

87 return 0;
88 }

Complexity analysis
a) Time complexity:

• Constructor: O(V ) to initialize V empty lists.

• addEdge: O(1) to append neighbors (two operations).

• dijkstra:

– Priority queue operations

∗ Up to V insertions for vertices: O(log V ) each, O(V log V ) total.
∗ Up to E extractions (each edge may add a new distance): O(log V ) each, O(E log V )
total.
– Iterating edges: O(E) across all vertices.
– Total: O(E log V + V log V ) = O((V + E) log V ).

University of Science Faculty of Information Technology Page 70

 Lab 8. GDS Data structures and Algorithms CSC10004

• Overall: O((V + E) log V ) for the algorithm, with O(V 2 ) for printing paths in the worst case.

b) Space complexity:

• Adjacency list: O(V + E).

• Dijkstra’s algorithm:O(V ) for dist, parent, visited, and O(V ) for the priority queue.

• Total: O(V + E).

Example Walkthrough
Input:
1 V = 6
2 Edges : (0 ,1 ,5) , (0 ,2 ,3) , (1 ,3 ,6) , (1 ,2 ,2) , (2 ,3 ,7) , (2 ,4 ,4) , (2 ,5 ,2) , (3 ,4 ,1) ,
(4 ,5 ,2)
3 Source : 0

Graph visualization:
1 0 - - - -5 - - - - > 1
2 | |
3 3 2
4 | |
5 v v
6 2 - - - -7 - - - - > 3
7 | |
8 4 1
9 | |
10 v v
11 5 < - - -2 - - - - 4

Adjacency list:
1 0: [(1 ,5) , (2 ,3) ]
2 1: [(3 ,6) , (2 ,2) ]
3 2: [(3 ,7) , (4 ,4) , (5 ,2) ]
4 3: [(4 ,1) ]
5 4: [(5 ,2) ]
6 5: []

Step-by-step:

• Initialization:

– dist = [∞, ∞, ∞, ∞, ∞, ∞].

University of Science Faculty of Information Technology Page 71

Lab 8. GDS Data structures and Algorithms CSC10004

– parent = [−1, −1, −1, −1, −1, −1].

– visited = [false, false, false, false, false, false].
– pq = [].
– Set dist[0] = 0, parent[0] = −1, push (0, 0) to pq.

• Priority Queue Processing:

– Extract (0, 0), vertex 0:

∗ Set visited[0] = true.
∗ Neighbors (1,5), (2,3): Update dist[1] = 5, parent[1] = 0, push (5, 1); Update
dist[2] = 3, parent[2] = 0, push (3, 2).
∗ pq = [(3, 2), (5, 1)].
– Extract (3, 2), vertex 2:
∗ Set visited[2] = true.
∗ Neighbors (3,7), (4,4), (5,2): Update dist[3] = 10, parent[3] = 2, push (10, 3);
Update dist[4] = 7, parent[4] = 2, push (7, 4); Update dist[5] = 5, parent[5] = 2,
push (5, 5).
∗ pq = [(5, 1), (5, 5), (10, 3), (7, 4)].
– Extract (5, 1), vertex 1:
∗ Set visited[1] = true.
∗ Neighbors (3,6), (2,2): Skip 2 (visited[2] = true); No update for 3 (5 + 6 = 11 >
10).
∗ pq = [(5, 5), (7, 4), (10, 3)].
– Extract (5, 5), vertex 5:
∗ Set visited[5] = true.
∗ No neighbors.
∗ pq = [(7, 4), (10, 3)].
– Extract (7, 4), vertex 4:
∗ Set visited[4] = true.
∗ Neighbors (5,2): Skip 5 (visited[5] = true).
∗ pq = [(10, 3)].

University of Science Faculty of Information Technology Page 72

 Lab 8. GDS Data structures and Algorithms CSC10004

– Extract (10, 3), vertex 3:

∗ Set visited[3] = true.
∗ Neighbors (4,1): Skip 4 (visited[4] = true).
∗ pq = [].

• Final State:

– dist = [0, 5, 3, 10, 7, 5].

– parent = [−1, 0, 0, 2, 2, 2].
– visited = [true, true, true, true, true, true].

• Print Paths:

– Vertex 0: dist[0] = 0, path: 0.

– Vertex 1: dist[1] = 5, path: 0 → 1.
– Vertex 2: dist[2] = 3, path: 0 → 2.
– Vertex 3: dist[3] = 10, path: 0 → 2 → 3.
– Vertex 4: dist[4] = 7, path: 0 → 2 → 4.
– Vertex 5: dist[5] = 5, path: 0 → 2 → 5.

Output:
1 Shortest paths from vertex 0 using optimized Dijkstra ’ s algorithm :
2 Vertex Distance Path
3 0 0 0
4 1 5 0 -> 1
5 2 3 0 -> 2
6 3 10 0 -> 2 -> 3
7 4 7 0 -> 2 -> 4
8 5 5 0 -> 2 -> 5

University of Science Faculty of Information Technology Page 73

Lab 8. GDS Data structures and Algorithms CSC10004

Regulations
Please follow these regulations:

• You are allowed to use any IDE.

• After completing assignment, check your submission before and after uploading to Moodle.

• Prohibited libraries: <set>, <unordered_set>, <map>, <unordered_map>, <algorithm>,

<list>, and <bits/stdc++.h>.

• You can use <vector> or any libraries that are not in the prohibited libraries listed above.

Your source code must be contributed in the form of a compressed file and named your sub-
mission according to the format [Link]. Here is a detail of the directory organization:
StudentID
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]
Exercise [Link]

The end.

University of Science Faculty of Information Technology Page 74