Made byBobr AI

EV Charging Network Design Using MST Algorithms

Learn how Kruskal's and Prim's Minimum Spanning Tree (MST) algorithms optimize EV charging station networks to minimize infrastructure costs.

#ev-charging-network#minimum-spanning-tree#kruskals-algorithm#prims-algorithm#graph-theory#smart-campus#algorithm-analysis#python-implementation
Watch
Pitch

Using Minimum Spanning Tree (MST) Algorithms

EV Charging Station Network Design Using Minimum Spanning Tree

Model campus blocks as nodes and cable cost as weights. Design a minimum-cost layout to connect EV charging stations and calculate total cost.

Network Graphic

Kruskal's Algorithm | Prim's Algorithm | Comparison & Cost Analysis

Report Submitted for the Subject of Design & Analysis of Algorithms (DAA)

Project Guide

Under the Guidance of Mrs. Vaidehi Vishal Patil

Academic Period

A.Y. 2025-26

Project Team

  • 25
    Joel Nadar
  • 26
    Sabina Nadar
  • 27
    Suyog Naik
  • 28
    Adhithya Nair
  • 29
    Ananya Nandgaonkar
  • 30
    Sahil Nishad
  • 31
    Ankit Pal
  • 32
    Sneha Pal
  • 33
    Eklavya Pandey
  • 34
    Pranay Pandey
  • 35
    Soumya Pandey
  • 36
    Utkarsh Pandey

Thakur College of Engineering and Technology

Made byBobr AI

Design & Analysis of Algorithms — DAA Project

Index

Sr. No.
Name of Topic
1
Introduction
2
Problem Statement & Campus Graph Model
3
Theoretical Background – Graph Theory & MST
4
Kruskal's Algorithm – Theory & Trace
5
Prim's Algorithm – Theory & Trace
6
Comparison: Kruskal's vs Prim's
7
Python Code Implementation
8
Real-World Applications
9
Current Trends & Future Scope
10
Conclusion
11
Acknowledgement & References

Thakur College of Engineering and Technology

Made byBobr AI

01 — Introduction

EV Charging Infrastructure on Smart Campuses

Electric Vehicle (EV) charging systems are becoming an important part of modern and smart university campuses. Many institutions like IITs and NITs are planning to install EV charging stations in different blocks. The main goal is to design a network where all locations are connected, but without any unnecessary extra connections that increase cost.

Node (Vertex)

Each campus block/location is modeled as a node in the graph

Edge (Connection)

Each cable connection between blocks is treated as an edge

Weight (Cost)

Cost of laying cable between blocks is the edge weight (₹ thousands)

MST Solution: Connects all nodes | No cycles | Minimum possible total cost | Algorithms: Kruskal's & Prim's

Thakur College of Engineering and Technology

Made byBobr AI

02 — Problem Statement & Campus Graph Model

IIT-Inspired Campus with 10 EV Charging Blocks

Network Graphic

Campus Nodes (Blocks)

10 Nodes
Node Campus Block Description
A Main Gate / Entry Primary entrance and security checkpoint
B Administrative Block Dean's office, accounts, reception
C Library Block Central library, reading halls, digital lab
D Engineering Block – AI/DS AI & Data Science classrooms and labs
E Engineering Block – CS/IT Computer Science & IT classrooms
F Science & Electronics Block Physics, chemistry, electronics labs
G Canteen & Sports Complex Food court, gymnasium, ground
H Hostel Block Boys' and girls' residential hostels
I Research & Innovation Centre R&D labs, startup incubation cell
J Parking & EV Hub Main parking lot and EV charging depot

Edge Weights

Cable Cost (₹K)
A–B 4
A–H 8
B–C 8
B–D 11
B–H 7
C–I 2
C–F 4
D–I 7
D–E 5
D–F 9
E–F 10
F–G 2
G–H 1
H–I 6
I–J 7
G–J 6

Objective Alignment

Connect all 10 blocks
Avoid redundant connections
Achieve minimum total cost

Thakur College of Engineering and Technology

Made byBobr AI

03 — Theoretical Background

Graph Theory & Minimum Spanning Tree (MST)

Icon

3.1 Graph Representation

G = (V, E) where V = vertices (locations) and E = edges (connections)

•

V = {A,B,C,D,E,F,G,H,I,J} → 10 campus blocks

•

E = 16 edges → possible cable connections

•

Weight (w) → cost of laying cable (₹ thousands)

•

Undirected & Connected graph

3.2 Spanning Tree

A spanning tree connects all vertices with exactly n-1 edges and no cycles

•

Includes ALL vertices (all 10 blocks)

•

Has exactly n-1 = 9 edges

•

Contains no cycles (no loops)

•

Minimum connections without forming any loops

Key Concept

3.3 Minimum Spanning Tree (MST)

The MST gives the cheapest cable layout connecting all 10 EV stations

No Cycles
No redundant cables → saves cost
All Nodes Connected
Every block has EV access
Exactly n-1 Edges
9 cables for 10 blocks
Minimum Total Weight
Global minimum cable cost

3.4 Cut Property

If we divide the graph into two groups (a cut), the minimum cost edge connecting these two groups will ALWAYS be part of the MST.

Key Insight

"Both Kruskal's and Prim's use this property — they always pick the cheapest edge while guaranteeing the optimal solution"

Thakur College of Engineering and Technology

Made byBobr AI

Section 4 (Part 1 of 2)

04 — Kruskal's Algorithm

Theory & Core Strategy | Proposed by Joseph Kruskal, 1956

Graph Algorithms · Minimum Spanning Tree

Algorithm Steps

  1. Sort ALL edges by weight in ascending (non-decreasing) order
  2. Initialize every vertex as its own separate component — Disjoint Set Union (DSU)
  3. While MST has fewer than n-1 edges: Pick the smallest edge (u, v)
  4. If u and v are in DIFFERENT components → ADD edge to MST, merge components (Union)
  5. If u and v are in SAME component → SKIP (would create a cycle)
  6. Stop when n-1 edges are added
Time Complexity: O(E log E)
Space Complexity: O(V) — DSU only

Key Characteristics

  • Works best for sparse graphs
  • Builds MST as a forest that gradually merges
  • Does NOT depend on starting vertex
  • Guarantees optimal solution via greedy choice property

Cycle Detection via DSU (Union-Find)

  • Find(x) → identifies the root/parent of a set
  • Union(x, y) → merges two different sets
  • If Find(u) == Find(v) → cycle detected → REJECT
  • With Path Compression & Union by Rank → near O(1) amortized

Step 1: Edges Sorted by Weight

EdgeWght
G – H1
C – I2
F – G2
A – B4
C – F4
D – E5
G – J6
H – I6
EdgeWght
B – H7
D – I7
I – J7
A – H8
B – C8
D – F9
E – F10
B – D11

Thakur College of Engineering and Technology

Made byBobr AI

04 — Kruskal's Algorithm – Step-by-Step Trace

Campus Graph Execution | 10 Nodes, 16 Edges

Network Graphic

Execution Trace · Minimum Spanning Tree

Step-by-Step Execution on Campus Graph

Edge Added
Edge Skipped (Cycle)
Step Edge Blocks ₹K Action (Cycle Check) MST?
1 G–H Canteen – Hostel 1 Different sets → ADD (Smallest edge) ✅
2 C–I Library – Research Centre 2 No cycle → ADD ✅
3 F–G Science – Canteen 2 No cycle → ADD ✅
4 A–B Main Gate – Admin Block 4 No cycle → ADD ✅
5 C–F Library – Science Block 4 Different sets → ADD (merges C,I,F,G,H) ✅
6 D–E AI/DS – CS/IT Block 5 No cycle → ADD ✅
7 G–J Canteen – Parking Hub 6 No cycle → ADD ✅
8 H–I Hostel – Research Centre 6 SAME SET → SKIP (Cycle Formed) ❌
9 D–I AI/DS – Research Centre 7 Different sets → ADD (merges D,E with main) ✅
10 I–J Research – Parking 7 SAME SET → SKIP (Cycle Formed) ❌
11 B–H Admin – Hostel Block 7 Different sets → ADD ← 9th edge: MST COMPLETE! ✅

Kruskal's MST — Final Result

MST Edges: G–H(1) + C–I(2) + F–G(2) + A–B(4) + C–F(4) + D–E(5) + G–J(6) + D–I(7) + B–H(7)

Total Cable Installation Cost

= ₹38,000

Thakur College of Engineering and Technology

Made byBobr AI

Section 5 (Part 1 of 2)

05 — Prim's Algorithm

Theory & Core Strategy | Proposed by Robert Prim, 1957

Graph Algorithms · Minimum Spanning Tree

Algorithm Steps

  1. Start from any arbitrary vertex (we use vertex A — Main Gate)
  2. Initialize a Min-Priority Queue with all vertices; set key[A]=0, all others=∞
  3. While priority queue is not empty: Extract vertex u with minimum key value
  4. For each neighbor v of u: If v is in PQ and weight(u,v) < key[v] → update key[v] = weight(u,v), parent[v] = u
  5. MST edge = (parent[v], v)
  6. Stop when all vertices are extracted
Time Complexity: O(E log V)
Space Complexity: O(V) — Priority Queue

Key Characteristics

  • Grows MST as a single connected tree from a start vertex
  • Greedy: always picks the minimum weight crossing edge
  • Works better on dense graphs
  • MST is built incrementally (vertex by vertex)

Priority Queue (Min-Heap) Concept

  • Extract-Min always gives lowest key
  • Decrease-Key updates when shorter path found
  • Each vertex processed exactly once

Step 1: Initial State

VertexKeyParent
A0NIL
B∞NIL
C∞NIL
D∞NIL
E∞NIL
VertexKeyParent
F∞NIL
G∞NIL
H∞NIL
I∞NIL
J∞NIL

Thakur College of Engineering and Technology

Made byBobr AI

Execution Trace · Minimum Spanning Tree

05 — Prim's Algorithm – Step-by-Step Trace

Campus Graph Execution | Starting from Vertex A (Main Gate)

Graph Algorithms · Prim's Algorithm Trace

Step-by-Step Execution on Campus Graph

Contains Key Updates
Step Vertex Extracted Key Value (₹K) Parent Edge Blocks Connected MST?
1 A 0 — Main Gate (Start) ✅
2 B 4 A–B Admin Block ✅
3 H 7 B–H Hostel Block ✅
4 G 1 G–H KEY UPDATED Canteen & Sports ✅
5 F 2 F–G KEY UPDATED Science Block ✅
6 C 4 C–F KEY UPDATED Library Block ✅
7 I 2 C–I KEY UPDATED Research Centre ✅
8 D 7 D–I KEY UPDATED AI/DS Block ✅
9 E 5 D–E KEY UPDATED CS/IT Block ✅
10 J 6 G–J KEY UPDATED Parking & EV Hub ✅

Prim's MST — Final Result

MST Edges: A–B(4) + B–H(7) + G–H(1) + F–G(2) + C–F(4) + C–I(2) + D–I(7) + D–E(5) + G–J(6)

Total Cable Installation Cost

= ₹38,000

Thakur College of Engineering and Technology

Made byBobr AI

06 — Comparison: Kruskal's vs Prim's

Algorithm Analysis, Complexity & Campus Results

Icon
Criteria
Kruskal's Algorithm
Prim's Algorithm
Proposed By
Joseph Kruskal, 1956
Robert Prim, 1957
Approach
Edge-based (sorts all edges)
Vertex-based (grows from one node)
Data Structure
Disjoint Set Union (DSU)
Min-Priority Queue (Min-Heap)
Time Complexity
O(E log E)
O(E log V)
Space Complexity
O(V)
O(V)
Best For
Sparse Graphs (few edges)
Dense Graphs (many edges)
Cycle Detection
Union-Find check
Not needed (only unvisited vertices)
Starting Point
No specific start
Requires a starting vertex
MST Cost (Campus)
₹38,000
₹38,000 ✅ Same result

Campus Result — Both Algorithms Agree!

MST Edges:

G–H(1), C–I(2), F–G(2), A–B(4), C–F(4), D–E(5), G–J(6), D–I(7), B–H(7)

Total = ₹38,000

Key Conclusion

For our campus EV network with 10 nodes and 16 edges (sparse graph), Kruskal's algorithm is slightly more efficient.

Both algorithms produce the OPTIMAL minimum cost layout of ₹38,000.

Thakur College of Engineering and Technology

Made byBobr AI

Design & Analysis of Algorithms — Python Implementation

07 — Python Code Implementation

Kruskal's & Prim's MST on Campus EV Graph

Kruskal's Algorithm — Python Code 

# Kruskal's MST — Campus EV Network
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])
    dsu = DSU(n)
    mst, cost = [], 0
    for u, v, w in edges:
        if dsu.union(u, v):
            mst.append((u, v, w))
            cost += w
    return mst, cost
Output: MST Cost = ₹38,000 | 9 Edges

Prim's Algorithm — Python Code 

# Prim's MST — Campus EV Network
import heapq

def prim(graph, start=0):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, start, -1)]
    mst, cost = [], 0
    
    while min_heap:
        w, u, parent = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        cost += w
        if parent != -1:
            mst.append((parent, u, w))
        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap,
                    (weight, v, u))
    return mst, cost
Output: MST Cost = ₹38,000 | 9 Edges

Thakur College of Engineering and Technology

Made byBobr AI

08 — Real-World Applications

Where MST Algorithms Shape the Modern World

EV & Smart Grid Networks

MST minimizes cable cost when connecting EV charging stations across cities. Used in smart grid design to reduce power line installation costs and transmission losses.

Telecom & Internet Infrastructure

Internet Service Providers use MST to lay fiber optic cables connecting cities with minimum cost. MST connects routers in backbone networks.

Campus Project

Campus Network Design

Our project directly applies MST to design EV charging cable layout. Same approach used for LAN/WiFi network planning, water/gas pipe networks.

Transportation & Road Networks

Road construction agencies use MST to connect cities/towns with minimum road length. Reduces construction and maintenance cost while ensuring full connectivity.

Medical & Emergency Services

Hospital networks, ambulance routing systems use MST to minimize travel time. Emergency communication infrastructure designed using MST principles.

Cluster Analysis & AI/ML

MST used in machine learning for clustering algorithms (Single-Link clustering). Image segmentation, community detection in social networks.

Thakur College of Engineering and Technology

Made byBobr AI

09 — Current Trends & Future Scope

MST in the Age of EV, Smart Cities & AI

Current Trends

1

Dynamic MST for EV Charging Networks

As EV adoption grows, charging networks need real-time updates. Dynamic MST algorithms add/remove nodes without recomputing from scratch (e.g., new charging station added to campus).

2

AI-Powered Network Optimization

Machine Learning models predict optimal MST configurations based on traffic patterns, usage hours, and energy demand. Reinforcement Learning optimizing cable routing decisions.

3

Green Energy Integration

Smart campuses integrate solar panels with EV charging. MST helps design hybrid energy distribution networks minimizing transmission loss and maximizing renewable usage.

4

5G & IoT Sensor Networks

5G base stations and IoT sensors across smart campuses require minimum-cost connectivity. MST forms the backbone of efficient sensor network topology design.

Future Scope

Future Scope

Extend campus model to multi-campus university networks

Real-time dynamic MST with EV demand forecasting

Integration with autonomous EV routing systems

Quantum computing applications for large-scale MST

Green corridor planning using weighted MST for solar-EV grids

Project Extension Possibilities

Enhancement
Impact
Add real GPS coordinates
Realistic weight computation
Dynamic edge addition
Real-time network updates
Multi-objective MST
Cost + reliability optimization
Visualization tool
Interactive campus EV map

Thakur College of Engineering and Technology

Made byBobr AI

10 — Conclusion

EV Charging Station Network Design Using Minimum Spanning Tree

This project successfully demonstrates the application of Minimum Spanning Tree algorithms to solve a real-world infrastructure problem. By modeling a campus with 10 blocks as graph nodes and cable costs as edge weights, we designed a minimum-cost EV charging network using both Kruskal's and Prim's algorithms, achieving a total cost of ₹38,000 with 9 optimal connections.

10 Campus Blocks (Nodes)
16 Possible Connections (Edges)
9 MST Edges Selected
₹38K Minimum Total Cost

Algorithm Insight

Kruskal's and Prim's both guarantee the optimal MST. Kruskal's is edge-based (O(E log E)), Prim's is vertex-based (O(E log V)). For sparse graphs like ours, Kruskal's is marginally more efficient.

Real-World Relevance

MST is directly applicable to EV charging infrastructure, telecommunications, smart grids, and transportation planning. This project bridges theoretical graph algorithms with practical engineering problems.

Learning Outcomes

Mastered graph representation, spanning tree theory, greedy algorithm design, DSU data structure, priority queue operations, and Python implementation of classical algorithms.

Thakur College of Engineering and Technology

Made byBobr AI

11 — Acknowledgement & References

Credits, Bibliography & Thank You

Acknowledgement

•

We express our sincere gratitude to Mrs. Vaidehi Vishal Patil, our project guide, for her invaluable guidance, constant encouragement, and expert insights throughout this project.

•

We also thank Thakur College of Engineering and Technology for providing us with the resources, infrastructure, and academic environment necessary to conduct this research.

•

Special thanks to our batch mates and the Department of AI & Data Science for their continuous support and constructive feedback.

Submitted by: Roll Nos. 25–36 | A.Y. 2025–26 | Subject: DAA

References

1

Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

2

Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1), 48–50.

3

Prim, R.C. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, 36(6), 1389–1401.

4

GeeksforGeeks — Kruskal's Minimum Spanning Tree Algorithm. (https://www.geeksforgeeks.org)

5

Python Documentation — heapq module. (https://docs.python.org/3/library/heapq.html)

6

NPTEL Lectures — Design & Analysis of Algorithms, IIT Madras.

7

Thakur College of Engineering and Technology — DAA Course Material, A.Y. 2025–26.

Thakur College of Engineering and Technology

Thank You!

Made byBobr AI
Bobr AI

DESIGNER-MADE
PRESENTATION,
GENERATED FROM
YOUR PROMPT

Create your own professional slide deck with real images, data charts, and unique design in under a minute.

Generate For Free

EV Charging Network Design Using MST Algorithms

Learn how Kruskal's and Prim's Minimum Spanning Tree (MST) algorithms optimize EV charging station networks to minimize infrastructure costs.

EV Charging Station Network Design Using Minimum Spanning Tree

Model campus blocks as nodes and cable cost as weights. Design a minimum-cost layout to connect EV charging stations and calculate total cost.

Using Minimum Spanning Tree (MST) Algorithms

Kruskal's Algorithm | Prim's Algorithm | Comparison & Cost Analysis

Report Submitted for the Subject of Design & Analysis of Algorithms (DAA)

Under the Guidance of Mrs. Vaidehi Vishal Patil

A.Y. 2025-26

Thakur College of Engineering and Technology

<li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">25</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Joel Nadar</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">26</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Sabina Nadar</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">27</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Suyog Naik</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">28</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Adhithya Nair</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">29</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Ananya Nandgaonkar</span></li> <li style="margin-bottom: 0px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">30</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Sahil Nishad</span></li>

<li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">31</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Ankit Pal</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">32</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Sneha Pal</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">33</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Eklavya Pandey</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">34</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Pranay Pandey</span></li> <li style="margin-bottom: 22px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">35</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Soumya Pandey</span></li> <li style="margin-bottom: 0px; display: flex; align-items: center;"><div style="width: 38px; height: 38px; background-color: #f1f5f9; border-radius: 50%; display: flex; align-items: center; justify-content: center; font-weight: 700; color: #1a2a4a; font-size: 15px; margin-right: 15px; border: 1px solid #cbd5e1;">36</div><span style="font-size: 22px; color: #334155; font-weight: 500;">Utkarsh Pandey</span></li>

Index

Design & Analysis of Algorithms — DAA Project

Thakur College of Engineering and Technology

<div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">1</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Introduction</div></div> <div style="display: flex; background-color: #f0f5ff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">2</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Problem Statement & Campus Graph Model</div></div> <div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">3</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Theoretical Background – Graph Theory & MST</div></div> <div style="display: flex; background-color: #f0f5ff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">4</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Kruskal's Algorithm – Theory & Trace</div></div> <div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">5</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Prim's Algorithm – Theory & Trace</div></div> <div style="display: flex; background-color: #f0f5ff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">6</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Comparison: Kruskal's vs Prim's</div></div> <div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">7</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Python Code Implementation</div></div> <div style="display: flex; background-color: #f0f5ff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">8</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Real-World Applications</div></div> <div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">9</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Current Trends & Future Scope</div></div> <div style="display: flex; background-color: #f0f5ff; padding: 9px 0; align-items: center; border-bottom: 1px solid #e2e8f0; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">10</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Conclusion</div></div> <div style="display: flex; background-color: #ffffff; padding: 9px 0; align-items: center; flex: 1;"><div style="width: 160px; text-align: center; font-size: 26px; font-weight: 700; color: #1a2a4a;">11</div><div style="flex: 1; font-size: 26px; font-weight: 500; color: #334155; padding-left: 30px;">Acknowledgement & References</div></div>

01 — Introduction

EV Charging Infrastructure on Smart Campuses

Electric Vehicle (EV) charging systems are becoming an important part of modern and smart university campuses. Many institutions like IITs and NITs are planning to install EV charging stations in different blocks. The main goal is to design a network where all locations are connected, but without any unnecessary extra connections that increase cost.

Node (Vertex)

Each campus block/location is modeled as a node in the graph

Edge (Connection)

Each cable connection between blocks is treated as an edge

Weight (Cost)

Cost of laying cable between blocks is the edge weight (₹ thousands)

<b>MST Solution:</b> Connects all nodes <span style="color: #2ecc71; margin: 0 15px;">|</span> No cycles <span style="color: #2ecc71; margin: 0 15px;">|</span> Minimum possible total cost <span style="color: #2ecc71; margin: 0 15px;">|</span> Algorithms: Kruskal's & Prim's

Thakur College of Engineering and Technology

02 — Problem Statement & Campus Graph Model

IIT-Inspired Campus with 10 EV Charging Blocks

Thakur College of Engineering and Technology

<tr style="background-color: #f8fafc; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">A</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Main Gate / Entry</td> <td style="padding: 13px 15px; color: #64748b;">Primary entrance and security checkpoint</td> </tr> <tr style="background-color: #ffffff; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">B</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Administrative Block</td> <td style="padding: 13px 15px; color: #64748b;">Dean's office, accounts, reception</td> </tr> <tr style="background-color: #f8fafc; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">C</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Library Block</td> <td style="padding: 13px 15px; color: #64748b;">Central library, reading halls, digital lab</td> </tr> <tr style="background-color: #ffffff; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">D</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Engineering Block – AI/DS</td> <td style="padding: 13px 15px; color: #64748b;">AI & Data Science classrooms and labs</td> </tr> <tr style="background-color: #f8fafc; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">E</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Engineering Block – CS/IT</td> <td style="padding: 13px 15px; color: #64748b;">Computer Science & IT classrooms</td> </tr> <tr style="background-color: #ffffff; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">F</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Science & Electronics Block</td> <td style="padding: 13px 15px; color: #64748b;">Physics, chemistry, electronics labs</td> </tr> <tr style="background-color: #f8fafc; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">G</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Canteen & Sports Complex</td> <td style="padding: 13px 15px; color: #64748b;">Food court, gymnasium, ground</td> </tr> <tr style="background-color: #ffffff; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">H</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Hostel Block</td> <td style="padding: 13px 15px; color: #64748b;">Boys' and girls' residential hostels</td> </tr> <tr style="background-color: #f8fafc; border-bottom: 1px solid #e2e8f0;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">I</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Research & Innovation Centre</td> <td style="padding: 13px 15px; color: #64748b;">R&D labs, startup incubation cell</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 13px 15px; text-align: center; font-weight: 700; color: #1a2a4a; font-size: 22px;">J</td> <td style="padding: 13px 15px; font-weight: 600; color: #334155;">Parking & EV Hub</td> <td style="padding: 13px 15px; color: #64748b;">Main parking lot and EV charging depot</td> </tr>

<tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">A–B</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">4</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">A–H</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">8</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">B–C</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">8</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">B–D</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">11</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">B–H</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">7</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">C–I</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">2</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">C–F</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">4</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">D–I</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">7</td> </tr>

<tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">D–E</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">5</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">D–F</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">9</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">E–F</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">10</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">F–G</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">2</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">G–H</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">1</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">H–I</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">6</td> </tr> <tr style="background-color: #f8fafc;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">I–J</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">7</td> </tr> <tr style="background-color: #ffffff;"> <td style="padding: 10px 15px; border-radius: 8px 0 0 8px; font-weight: 600; color: #1a2a4a; border: 1px solid #e2e8f0; border-right: none; font-size: 18px;">G–J</td> <td style="padding: 10px 15px; border-radius: 0 8px 8px 0; font-weight: 800; color: #2ecc71; text-align: right; border: 1px solid #e2e8f0; border-left: none; font-size: 20px;">6</td> </tr>

03 — Theoretical Background

Graph Theory & Minimum Spanning Tree (MST)

Thakur College of Engineering and Technology

3.1 Graph Representation

<strong>G = (V, E)</strong> where <strong>V</strong> = vertices (locations) and <strong>E</strong> = edges (connections)

<strong>V = {A,B,C,D,E,F,G,H,I,J}</strong> &rarr; 10 campus blocks

<strong>E = 16 edges</strong> &rarr; possible cable connections

<strong>Weight (w)</strong> &rarr; cost of laying cable (₹ thousands)

<strong>Undirected &amp; Connected</strong> graph

3.2 Spanning Tree

A spanning tree connects all vertices with exactly <strong>n-1 edges</strong> and <strong>no cycles</strong>

Includes <strong>ALL vertices</strong> (all 10 blocks)

Has exactly <strong>n-1 = 9 edges</strong>

Contains <strong>no cycles</strong> (no loops)

<strong>Minimum connections</strong> without forming any loops

3.3 Minimum Spanning Tree (MST)

The MST gives the cheapest cable layout connecting all 10 EV stations

No Cycles

No redundant cables &rarr; saves cost

All Nodes Connected

Every block has EV access

Exactly n-1 Edges

9 cables for 10 blocks

Minimum Total Weight

Global minimum cable cost

3.4 Cut Property

If we divide the graph into two groups (a cut), the <strong>minimum cost edge</strong> connecting these two groups will <strong>ALWAYS</strong> be part of the MST.

Both Kruskal's and Prim's use this property — they always pick the cheapest edge while guaranteeing the optimal solution

Section 4 (Part 1 of 2)

04 — Kruskal's Algorithm

Theory & Core Strategy | Proposed by Joseph Kruskal, 1956

Thakur College of Engineering and Technology

04 — Kruskal's Algorithm – Step-by-Step Trace

Campus Graph Execution | 10 Nodes, 16 Edges

Execution Trace · Minimum Spanning Tree

Thakur College of Engineering and Technology

Section 5 (Part 1 of 2)

05 — Prim's Algorithm

Theory & Core Strategy | Proposed by Robert Prim, 1957

Graph Algorithms &middot; Minimum Spanning Tree

<b>Start</b> from any arbitrary vertex (we use vertex A &mdash; Main Gate)

<b>Initialize</b> a Min-Priority Queue with all vertices; set key[A]=0, all others=&infin;

<b>While</b> priority queue is not empty: Extract vertex u with minimum key value

<b>For each neighbor</b> v of u: If v is in PQ and weight(u,v) &lt; key[v] &rarr; update key[v] = weight(u,v), parent[v] = u

MST edge = <b>(parent[v], v)</b>

<b>Stop</b> when all vertices are extracted

Time Complexity: O(E log V)

Space Complexity: O(V) &mdash; Priority Queue

Grows MST as a single connected tree from a start vertex

Greedy: always picks the minimum weight crossing edge

Works better on dense graphs

MST is built incrementally (vertex by vertex)

<b>Extract-Min</b> always gives lowest key

<b>Decrease-Key</b> updates when shorter path found

Each vertex processed exactly once

Thakur College of Engineering and Technology

Execution Trace · Minimum Spanning Tree

05 — Prim's Algorithm – Step-by-Step Trace

Campus Graph Execution | Starting from Vertex A (Main Gate)

Graph Algorithms · Prim's Algorithm Trace

Thakur College of Engineering and Technology

A–B(4) + B–H(7) + G–H(1) + F–G(2) + C–F(4) + C–I(2) + D–I(7) + D–E(5) + G–J(6)

06 — Comparison: Kruskal's vs Prim's

Algorithm Analysis, Complexity & Campus Results

Proposed By

Joseph Kruskal, 1956

Robert Prim, 1957

Approach

Edge-based (sorts all edges)

Vertex-based (grows from one node)

Data Structure

Disjoint Set Union (DSU)

Min-Priority Queue (Min-Heap)

Time Complexity

O(E log E)

O(E log V)

Space Complexity

O(V)

O(V)

Best For

Sparse Graphs (few edges)

Dense Graphs (many edges)

Cycle Detection

Union-Find check

Not needed (only unvisited vertices)

Starting Point

No specific start

Requires a starting vertex

MST Cost (Campus)

₹38,000

₹38,000 ✅ Same result

Campus Result — Both Algorithms Agree!

G–H(1), C–I(2), F–G(2), A–B(4), C–F(4), D–E(5), G–J(6), D–I(7), B–H(7)

₹38,000

Key Conclusion

For our campus EV network with <strong>10 nodes</strong> and <strong>16 edges</strong> (sparse graph), <strong>Kruskal's algorithm</strong> is slightly more efficient.

Both algorithms produce the OPTIMAL minimum cost layout of ₹38,000.

Thakur College of Engineering and Technology

Design & Analysis of Algorithms — Python Implementation

07 — Python Code Implementation

Kruskal's & Prim's MST on Campus EV Graph

Kruskal's Algorithm — Python Code

Prim's Algorithm — Python Code

Output: MST Cost = ₹38,000 | 9 Edges

Thakur College of Engineering and Technology

08 — Real-World Applications

Where MST Algorithms Shape the Modern World

Thakur College of Engineering and Technology

EV & Smart Grid Networks

MST minimizes cable cost when connecting EV charging stations across cities. Used in smart grid design to reduce power line installation costs and transmission losses.

Telecom & Internet Infrastructure

Internet Service Providers use MST to lay fiber optic cables connecting cities with minimum cost. MST connects routers in backbone networks.

Campus Network Design

Our project directly applies MST to design EV charging cable layout. Same approach used for LAN/WiFi network planning, water/gas pipe networks.

Transportation & Road Networks

Road construction agencies use MST to connect cities/towns with minimum road length. Reduces construction and maintenance cost while ensuring full connectivity.

Medical & Emergency Services

Hospital networks, ambulance routing systems use MST to minimize travel time. Emergency communication infrastructure designed using MST principles.

Cluster Analysis & AI/ML

MST used in machine learning for clustering algorithms (Single-Link clustering). Image segmentation, community detection in social networks.

09 — Current Trends & Future Scope

MST in the Age of EV, Smart Cities & AI

Current Trends

Dynamic MST for EV Charging Networks

As EV adoption grows, charging networks need real-time updates. Dynamic MST algorithms add/remove nodes without recomputing from scratch (e.g., new charging station added to campus).

AI-Powered Network Optimization

Machine Learning models predict optimal MST configurations based on traffic patterns, usage hours, and energy demand. Reinforcement Learning optimizing cable routing decisions.

Green Energy Integration

Smart campuses integrate solar panels with EV charging. MST helps design hybrid energy distribution networks minimizing transmission loss and maximizing renewable usage.

5G & IoT Sensor Networks

5G base stations and IoT sensors across smart campuses require minimum-cost connectivity. MST forms the backbone of efficient sensor network topology design.

Future Scope

Future Scope

Extend campus model to multi-campus university networks

Real-time dynamic MST with EV demand forecasting

Integration with autonomous EV routing systems

Quantum computing applications for large-scale MST

Green corridor planning using weighted MST for solar-EV grids

Project Extension Possibilities

Enhancement

Impact

Add real GPS coordinates

Realistic weight computation

Dynamic edge addition

Real-time network updates

Multi-objective MST

Cost + reliability optimization

Visualization tool

Interactive campus EV map

Thakur College of Engineering and Technology

10 — Conclusion

EV Charging Station Network Design Using Minimum Spanning Tree

This project successfully demonstrates the application of Minimum Spanning Tree algorithms to solve a real-world infrastructure problem. By modeling a campus with <strong style="color: #1a2a4a; font-weight: 700;">10 blocks</strong> as graph nodes and cable costs as edge weights, we designed a minimum-cost EV charging network using both <strong style="color: #1a2a4a; font-weight: 700;">Kruskal's and Prim's</strong> algorithms, achieving a total cost of <strong style="color: #2ecc71; font-weight: 800;">₹38,000</strong> with <strong style="color: #1a2a4a; font-weight: 700;">9 optimal connections</strong>.

10

Campus Blocks (Nodes)

16

Possible Connections (Edges)

9

MST Edges Selected

₹38K

Minimum Total Cost

Algorithm Insight

Kruskal's and Prim's both guarantee the optimal MST. Kruskal's is edge-based (O(E log E)), Prim's is vertex-based (O(E log V)). For sparse graphs like ours, Kruskal's is marginally more efficient.

Real-World Relevance

MST is directly applicable to EV charging infrastructure, telecommunications, smart grids, and transportation planning. This project bridges theoretical graph algorithms with practical engineering problems.

Learning Outcomes

Mastered graph representation, spanning tree theory, greedy algorithm design, DSU data structure, priority queue operations, and Python implementation of classical algorithms.

Thakur College of Engineering and Technology

11 — Acknowledgement & References

Credits, Bibliography & Thank You

Acknowledgement

We express our sincere gratitude to Mrs. Vaidehi Vishal Patil, our project guide, for her invaluable guidance, constant encouragement, and expert insights throughout this project.

We also thank Thakur College of Engineering and Technology for providing us with the resources, infrastructure, and academic environment necessary to conduct this research.

Special thanks to our batch mates and the Department of AI & Data Science for their continuous support and constructive feedback.

Submitted by: Roll Nos. 25–36 | A.Y. 2025–26 | Subject: DAA

References

Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society, 7(1), 48–50.

Prim, R.C. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal, 36(6), 1389–1401.

GeeksforGeeks — Kruskal's Minimum Spanning Tree Algorithm. (https://www.geeksforgeeks.org)

Python Documentation — heapq module. (https://docs.python.org/3/library/heapq.html)

NPTEL Lectures — Design & Analysis of Algorithms, IIT Madras.

Thakur College of Engineering and Technology — DAA Course Material, A.Y. 2025–26.

Thakur College of Engineering and Technology

Thank You!

  • ev-charging-network
  • minimum-spanning-tree
  • kruskals-algorithm
  • prims-algorithm
  • graph-theory
  • smart-campus
  • algorithm-analysis
  • python-implementation