Data Structures and Algorithms (CS-210)
Lab Session-06
Graph Fundamentals and Applications
Dr. M. Abbas Abbasi
1 Objective
Understanding graph data structures, their representations, traversal algorithms, and solving real-world
problems using graph theory concepts.
2 Learning Outcomes
After completing this lab session, students will be able to:
• Implement graphs using adjacency lists and matrices
• Apply BFS and DFS traversal algorithms
• Solve path finding and connectivity problems
• Model real-world scenarios using graphs
• Analyze time and space complexity of graph algorithms
3 Graph Fundamentals
Graphs consist of vertices (nodes) connected by edges. They can be:
• Directed/Undirected: Directed graphs have edges with a direction, while undirected graphs do
not.
• Weighted/Unweighted: Weighted graphs have edges with associated weights, often representing
costs or distances.
• Cyclic/Acyclic: Cyclic graphs contain cycles, whereas acyclic graphs do not.
3.1 Graph Representations
Graphs can be represented using:
• Adjacency Matrix: A 2D array where the cell at row i and column j indicates an edge from
vertex i to vertex j.
• Adjacency List: An array of lists where each list at index i contains the neighbors of vertex i.
3.2 Adjacency List Implementation
1 /*
2 Graph Representation :
3
4 0 -- 1
5 |
6 v
1
7 2
8
9 Adjacency List :
10 0: 1 2
11 1: 0
12 2:
13 3:
14 4:
15
16 Explanation :
17 - 0 is connected to 1 ( undirected ) -> So , 1 is also connected to 0.
18 - 0 has a directed edge to 2 -> So , 2 is not connected back to 0.
19 - Nodes 3 and 4 are isolated ( no edges ) .
20
21 */
22 # include < iostream >
23 # include < vector >
24 # include < list >
25 using namespace std ;
26
27 class Graph {
28 int V ;
29 vector < list < int > > adj ;
30
31 public :
32 Graph ( int V ) : V ( V ) , adj ( V ) {}
33
34 void addEdge ( int v , int w , bool directed = false ) {
35 adj [ v ]. push_back ( w ) ;
36 if (! directed ) adj [ w ]. push_back ( v ) ;
37 }
38
39 void print () {
40 for ( int v = 0; v < V ; ++ v ) {
41 cout << v << " : " ;
42 for ( int neighbor : adj [ v ])
43 cout << neighbor << " " ;
44 cout << endl ;
45 }
46 }
47 };
48
49 int main () {
50 Graph g (5) ;
51 g . addEdge (0 , 1) ; // Undirected
52 g . addEdge (0 , 2 , true ) ; // Directed
53 g . print () ;
54 return 0;
55 }
Listing 1: Graph Class Implementation
4 Graph Traversal Algorithms
4.1 Breadth-First Search (BFS)
BFS explores vertices level by level, starting from a source vertex.
1 /*
2 Graph Representation :
3
4 0
5 / \
2
6 1 2
7 | \
8 3 ---> 4
9
10 Adjacency List :
11 0: 1 2
12 1: 3
13 2: 4
14 3: 4
15 4:
16
17 BFS Traversal starting from node 0:
18 Order : 0 1 2 3 4
19
20 Explanation :
21 1. Start at 0 , visit 1 and 2.
22 2. Visit 1 s neighbor (3) .
23 3. Visit 2 s neighbor (4) .
24 4. Visit 3 s neighbor (4) , but it is already visited .
25 5. End traversal .
26 */
27 # include < iostream >
28 # include < vector >
29 # include < list >
30 # include < queue >
31 using namespace std ;
32
33 void BFS ( const vector < list < int > >& adj , int start ) {
34 vector < bool > visited ( adj . size () , false ) ;
35 queue < int > q ;
36 q . push ( start ) ;
37 visited [ start ] = true ;
38 while (! q . empty () ) {
39 int v = q . front () ;
40 q . pop () ;
41 cout << v << " " ;
42 for ( int neighbor : adj [ v ]) {
43 if (! visited [ neighbor ]) {
44 visited [ neighbor ] = true ;
45 q . push ( neighbor ) ;
46 }
47 }
48 }
49 cout << endl ;
50 }
51
52 int main () {
53 vector < list < int > > graph (5) ;
54 graph [0]. push_back (1) ;
55 graph [0]. push_back (2) ;
56 graph [1]. push_back (3) ;
57 graph [2]. push_back (4) ;
58 graph [3]. push_back (4) ;
59 cout << " BFS Traversal : " ;
60 BFS ( graph , 0) ;
61 return 0;
62 }
Listing 2: BFS Implementation
4.2 Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking.
3
1 /*
2 Graph Representation :
3
4 0
5 / \
6 1 2
7 | \
8 3 ---> 4
9
10 Adjacency List :
11 0: 1 2
12 1: 3
13 2: 4
14 3: 4
15 4:
16
17 DFS Traversal starting from node 0:
18 Order ( Iterative DFS using stack ) : 0 1 3 4 2
19
20 Explanation :
21 1. Start at 0 , push 1 and 2 (2 is pushed last , so it is processed later ) .
22 2. Pop 1 , visit it , push its neighbor 3.
23 3. Pop 3 , visit it , push its neighbor 4.
24 4. Pop 4 , visit it ( no new neighbors to push ) .
25 5. Pop 2 , visit it ( its neighbor 4 is already visited ) .
26 6. End traversal .
27 */
28 # include < iostream >
29 # include < vector >
30 # include < list >
31 # include < stack >
32 using namespace std ;
33
34 void DFS ( const vector < list < int > >& adj , int start ) {
35 vector < bool > visited ( adj . size () , false ) ;
36 stack < int > s ;
37 s . push ( start ) ;
38 while (! s . empty () ) {
39 int v = s . top () ;
40 s . pop () ;
41 if (! visited [ v ]) {
42 visited [ v ] = true ;
43 cout << v << " " ;
44 for ( auto it = adj [ v ]. rbegin () ; it != adj [ v ]. rend () ; ++ it ) {
45 if (! visited [* it ]) {
46 s . push (* it ) ;
47 }
48 }
49 }
50 }
51 cout << endl ;
52 }
53
54 int main () {
55 vector < list < int > > graph (5) ;
56 graph [0]. push_back (1) ;
57 graph [0]. push_back (2) ;
58 graph [1]. push_back (3) ;
59 graph [2]. push_back (4) ;
60 graph [3]. push_back (4) ;
61 cout << " DFS Traversal : " ;
62 DFS ( graph , 0) ;
63 return 0;
4
64 }
Listing 3: DFS Implementation (Iterative)
5 Weighted Graph Implementation
Weighted graphs are used to represent scenarios where edges have associated costs.
1 /*
2 Graph Representation :
3
4 (4)
5 0 ------- 1
6 \ / \
7 (8) \ (8) (11)
8 \ / \
9 2 ------ 3
10 (7)
11
12 Adjacency List :
13 0: (1 ,4) (2 ,8)
14 1: (0 ,4) (2 ,8) (3 ,11)
15 2: (0 ,8) (1 ,8) (3 ,7)
16 3: (1 ,11) (2 ,7)
17 4: ( No edges )
18
19 D i j k s t r a s Algorithm starting from node 0:
20 Shortest distances from node 0:
21
22 Vertex Distance from Source (0)
23 ---------------------------------
24 0 0
25 1 4
26 2 8
27 3 15
28
29 Explanation :
30 1. Start at 0 , distances initialized : [0 , , , ].
31 2. Pick 0 , update neighbors : [0 , 4 , 8 , ].
32 3. Pick 1 ( min dist ) , update neighbors : [0 , 4 , 8 , 15].
33 4. Pick 2 ( min dist ) , update neighbors ( no change ) .
34 5. Pick 3 ( min dist ) , end .
35
36 The shortest paths from 0 to all other vertices are computed using a min - heap (
priority queue ) .
37 */
38 # include < iostream >
39 # include < vector >
40 # include < queue >
41 # include < climits >
42 using namespace std ;
43
44 typedef pair < int , int > iPair ;
45
46 class WeightedGraph {
47 int V ;
48 vector < list < iPair > > adj ;
49 public :
50 WeightedGraph ( int V ) : V ( V ) , adj ( V ) {}
51 void addEdge ( int u , int v , int w ) {
52 adj [ u ]. push_back ({ v , w }) ;
53 adj [ v ]. push_back ({ u , w }) ;
54 }
5
55 void dijkstra ( int src ) {
56 priority_queue < iPair , vector < iPair > , greater < iPair > > pq ;
57 vector < int > dist (V , INT_MAX ) ;
58 pq . push ({0 , src }) ;
59 dist [ src ] = 0;
60 while (! pq . empty () ) {
61 int u = pq . top () . second ;
62 pq . pop () ;
63 for ( auto &[ v , weight ] : adj [ u ]) {
64 if ( dist [ v ] > dist [ u ] + weight ) {
65 dist [ v ] = dist [ u ] + weight ;
66 pq . push ({ dist [ v ] , v }) ;
67 }
68 }
69 }
70 cout << " Vertex \ tDistance from Source \ n " ;
71 for ( int i = 0; i < V ; ++ i )
72 cout << i << " \ t " << dist [ i ] << endl ;
73 }
74 };
75
76 int main () {
77 WeightedGraph g (5) ;
78 g . addEdge (0 , 1 , 4) ;
79 g . addEdge (0 , 2 , 8) ;
80 g . addEdge (1 , 2 , 8) ;
81 g . addEdge (1 , 3 , 11) ;
82 g . addEdge (2 , 3 , 7) ;
83 g . dijkstra (0) ;
84 return 0;
85 }
Listing 4: Weighted Graph with Dijkstra’s Algorithm
6 Real-World Applications
6.1 Social Network Analysis
Graphs can model social networks where vertices represent users and edges represent friendships.
1 /*
2 Friend Network Graph :
3
4 0
5 / \
6 1 2
7 / \
8 3 4
9 \ /
10 5
11
12 Adjacency List Representation :
13 0: 1 , 2
14 1: 3
15 2: 4
16 3: 5
17 4: 5
18 5: ( No outgoing edges )
19
20 Friend Recommendation Process :
21 - User 0 has direct friends : [1 , 2]
22 - Friends of friends ( depth 2) :
23 - Friends of 1: [3] ( added to recommendations )
6
24 - Friends of 2: [4] ( added to recommendations )
25 - Further depth is ignored , so recommendations are : [3 , 4]
26
27 Output :
28 Friend Recommendations for user 0: 3 4
29 */
30 # include < iostream >
31 # include < vector >
32 # include < list >
33 # include < queue >
34 using namespace std ;
35
36 vector < int > f rien dReco mmen datio ns ( const vector < list < int > >& graph , int user ) {
37 vector < bool > visited ( graph . size () , false ) ;
38 vector < int > recommendations ;
39 queue < int > q ;
40
41 // Mark direct friends as visited
42 visited [ user ] = true ;
43 for ( int friendNode : graph [ user ]) {
44 visited [ friendNode ] = true ;
45 q . push ( friendNode ) ;
46 }
47
48 // Find friends of friends ( depth 2)
49 while (! q . empty () ) {
50 int current = q . front () ;
51 q . pop () ;
52
53 for ( int friend_of_friend : graph [ current ]) {
54 if (! visited [ friend_of_friend ]) {
55 recommendations . push_back ( friend_of_friend ) ;
56 visited [ friend_of_friend ] = true ;
57 }
58 }
59 }
60 return recommendations ;
61 }
62
63 int main () {
64 vector < list < int > > graph (6) ;
65 graph [0]. push_back (1) ;
66 graph [0]. push_back (2) ;
67 graph [1]. push_back (3) ;
68 graph [2]. push_back (4) ;
69 graph [3]. push_back (5) ;
70 graph [4]. push_back (5) ;
71
72 vector < int > recommendations = f rien dReco mmen datio ns ( graph , 0) ;
73 cout << " Friend Recommendations for user 0: " ;
74 for ( int rec : recommendations ) {
75 cout << rec << " " ;
76 }
77 cout << endl ;
78 return 0;
79 }
Listing 5: Friend Recommendation System with Testing
6.2 Web Crawler
Graphs can model the web where vertices represent pages and edges represent hyperlinks.
1 /*
7
2 Web Graph Structure :
3
4 (0)
5 / \
6 (1) (2)
7 | |
8 (3) (4)
9 | /
10 (5)
11
12 Adjacency List Representation :
13 0 1, 2
14 1 3
15 2 4
16 3 5
17 4 5
18 5 ( No outgoing links )
19
20 Web Crawler Process :
21 - Starts at page 0 , visits [1 , 2]
22 - Then visits [3] ( from 1) and [4] ( from 2)
23 - Finally , visits page [5] ( from 3 and 4)
24 - Stops when all accessible pages are visited
25
26 Expected Output :
27 Starting web crawling from page 0:
28 Crawling page : 0
29 Crawling page : 1
30 Crawling page : 2
31 Crawling page : 3
32 Crawling page : 4
33 Crawling page : 5
34 */
35 # include < iostream >
36 # include < vector >
37 # include < list >
38 # include < queue >
39 using namespace std ;
40
41 void webCrawler ( const vector < list < int > >& webGraph , int startPage ) {
42 vector < bool > visited ( webGraph . size () , false ) ;
43 queue < int > q ;
44 q . push ( startPage ) ;
45 visited [ startPage ] = true ;
46 while (! q . empty () ) {
47 int current = q . front () ;
48 q . pop () ;
49 cout << " Crawling page : " << current << endl ;
50 for ( int linkedPage : webGraph [ current ]) {
51 if (! visited [ linkedPage ]) {
52 visited [ linkedPage ] = true ;
53 q . push ( linkedPage ) ;
54 }
55 }
56 }
57 }
58
59 int main () {
60 vector < list < int > > webGraph (6) ;
61 webGraph [0]. push_back (1) ;
62 webGraph [0]. push_back (2) ;
63 webGraph [1]. push_back (3) ;
64 webGraph [2]. push_back (4) ;
8
65 webGraph [3]. push_back (5) ;
66 webGraph [4]. push_back (5) ;
67
68 cout << " Starting web crawling from page 0:\ n " ;
69 webCrawler ( webGraph , 0) ;
70 return 0;
71 }
Listing 6: Basic Web Crawler Simulation with Testing
7 Lab Tasks
Task 1: Graph Representation (30 minutes)
Implement a graph class supporting:
• Both directed and undirected edges
• Edge count and existence checking
• Vertex degree calculation
Test Cases:
1. Create a graph with 5 vertices and these edges:
• 0-1 (undirected), 0→2 (directed), 1→3, 2-4 (undirected), 3→4
2. Verify:
• Total edges (should be 5)
• Degree of vertex 0 (should be 2)
• Check if edge exists from 2→4 (should be true)
• Check if edge exists from 4→2 (should be true)
• Check if edge exists from 1→0 (should be false)
Task 2: Traversal Algorithms (45 minutes)
Implement BFS and DFS with the following enhancements:
• Return traversal path as vector¡int¿
• Find connected components
• Detect cycles in undirected graphs
Test Cases:
1. For this graph:
0---1 2---3
| | / | / |
4 5---6---7
2. Verify:
• BFS from 0: [0,1,4,5,2,6,3,7] (or similar)
• DFS from 2: [2,1,0,4,5,6,3,7] (or similar)
• Number of connected components (should be 1)
• Contains cycle (should be true)
9
Task 3: Weighted Graphs (45 minutes)
Implement Dijkstra’s algorithm and:
• Find shortest paths from a source node
• Calculate graph diameter (longest shortest path)
• Find minimum spanning tree (Prim’s algorithm)
Test Cases:
1. For this weighted graph:
• 0-1:4, 0-7:8, 1-7:11, 1-2:8, 7-8:7, 7-6:1,
• 2-8:2, 8-6:6, 2-3:7, 2-5:4, 6-5:2, 3-5:14, 3-4:9, 5-4:10
2. Verify:
• Shortest path from 0 to 4 (should be 21)
• Graph diameter (should be 25 between 0-4)
• MST total weight (should be 37)
Task 4: Real-World Problem (60 minutes)
Choose one to implement:
1. Course Prerequisite System:
• Model course dependencies as a directed graph
• Implement topological sort to find valid course order
• Detect impossible prerequisites (cycles)
2. Transportation Network:
• Model cities and routes as weighted graph
• Find shortest paths between cities
• Calculate most central city (minimum maximum distance)
10
