A SEMINAR REPORT ON
Minimum Spanning Tree of all institutes and schools of Samarth
Sankul of Nutan Maharashtra Vidya Prasarak Mandal Pune in
Maharashtra State using Kruskal’s algorithm.
SUBMITTED TO THE SAVITRIBAI PHULE PUNE UNIVERSITY,
PUNE,IN THE PARIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE AWARD OF THE DEGREE
OF
THIRD YEAR COMPUTER ENGINEERING
BY
BHAGYADA SAMEER WAGH.
UNDER THE GUIDANCE OF
PROF. NEHA BHAGWAT.
Nutan Maharashtra Vidya Prasarak Mandal's
NUTAN MAHARASHTRA INSTITUTE OF ENGINEERING & TECHNOLOGY, PUNE
Samarth Vidya Sankul, Vishnupuri,
Talegaon Dabhade, Maharashtra 410507
ACADEMIC YEAR : 2024-2025
NOV-DEC 2024
CERTIFICATE
This is to certify that the seminar entitled
“Minimum Spanning Tree of all institutes and schools of
Samarth Sankul of Nutan Maharashtra Vidya Prasarak
Mandal Pune in Maharashtra State using kruskal’s
algorithm.”
Submitted by
Bhagyada Sameer Wagh.
Exam Seat No.: T1905504340
is a bonafide work carried out by him/ her under the supervision of Prof. Neha Bhagwat and it is
approved for the partial fulfillment of the requirement of Savitribai Phule Pune University, Pune
for the award of the degree of Third Year Computer Engineering
The seminar work has not been earlier submitted to any other institute or university for the
award of degree or diploma.
Prof. Neha Bhagwat Prof. Vaishali Dhawas [Link] Dhore
(Seminar Guide) Subject Incharge HOD
Dr. S. N. Sapali
Principal
NMIET, Talegaon
Place: Pune
Date:
I
Acknowledgement
I take this opportunity to express my deepest sense of gratitude and sincere thanks to everyone
who helped me to complete this work successfully. I express my sincere thanks to Dr. Prasad
Dhore, Head of Department, Computer Engineering, NMVP and PCET’s Nutan Maharashtra
Institute of Engineering Technology, Talegaon. for providing me with all the necessary
facilities and support.
I would like to express my sincere gratitude to the Seminar Coordinator Prof. Vaishali
Dhawas Assistant Professor, Department of Computer Engineering, NMIET for their support
and co-operation.
I would like to place on record my sincere gratitude to my seminar guide Prof. Neha
Bhagwat, Assistant Professor, Department of Computer Engineering, NMIET for the
guidance and mentorship throughout the course.
Finally, I thank my family, and friends who contributed to the successful fulfilment of this
seminar work.
Miss. Bhagyada Sameer Wagh.
II
ABSTRACT
Minimum Spanning Tree is very effective algorithm to find minimum distance which covers all
nodes .
There are various algorithm to find Minimum Spanning Tree. Kruskal’s and Prim’s algorithms
are widely used to find Minimum Spanning Tree.
In this research paper we have find Minimum spanning tree for NMVPM’s campus.
For finding Minimum Spanning Tree we consider all the main locations as nodes and the
distance between two nodes as edge having weight as distance.
Kruskal’s algorithm is used for finding Minimum Spanning Tree which has less Time
Complexity and also it is Simple To Implement.
Keywords: Kruskal’s algorithm, Minimum Spanning Tree, vertices, Time Complexity, etc.
III
CONTENTS
CERTIFICATE I
ACKNOWLEDGEMENT II
ABSTRACT III
LIST OF CONTENTS IV
LIST OF FIGURES V
CHAPTER TITLE PAGE NO
1. INTRODUCTION
1.1 BACKGROUND /OVERVIEW OF TOPIC 1
1.2 PROBLEM STATEMENT 2
1.3 OBJECTIVES 2
1.4 SCOPE OF THE STUDY 3
1.5 ORGANIZATION OF PROJECT REPORT. 6
2. LITERATURE SURVEY
2.1 REVIEW OF PREVIOUS WORK 7
2.2 KEY THEORIES AND CONCEPTS 8
3. DESIGN/TECHNOLOGY/METHODOLOGY
3.1 DESIGN/TECHNOLOGY OVERVIEW 9
3.2 ANALYTICAL APPROACH 10
3.3 EXPERIMENTAL WORK (IF ANY) 13
4. RESULTS AND ANALYSIS
4.1 PRESENTATION OF DATA 16
4.2 INTERPRETATION OF RESULT 17
4.3 COMPARISON 19
5. DISCUSSIONS
5.1 CRITICAL EVALUATION 20
5.2 LIMITATIONS 23
5.3 IMPLICATIONS FOR FUTURE RESEARCH 24
6. CONCLUSION
6.1 SUMMARY OF FINDINGS 26
6.2 FUTURE DIRECTIONS 26
7. REFERENCES/BIBLIOGRAPHY
7.1 LIST OF REFERENCES 28
IV
LIST OF FIGURES
3.1 Longitude and Latitude of locations in NMVPM campus 13
3.2 Location-to-Location Road Showing Distance in Meter 14
3.3 Existence ways among locations 14
3.4 Shortest path in NMVPM’s Campus using Kruskal’s algorithm 15
V
1
