MINIMUM SPANNING TREE

IN A GIVEN WEIGHTED GRAPH

USING KRUSKAL’S ALGORITHM
A PROJECT REPORT
Submitted by
Fraz Alam (230101120271)
Abu Shama (230101120272)
Affanul Haque (230101120273)
Aditya Kumar (230101120287)
Harsh Raj (230101120288)
Sonu Kumar (230101120300)
GUIDED BY -Dr. Aditya Kumar Pati

in partial fulfillment for the award of

the degree of

BACHELOR OF TECHNOLOGY
in
COMPUTER SCIENCE ENGINEERING

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

SCHOOL OF ENGINEERING AND TECHNOLOGY
PARALAKHEMUNDI CAMPUS
CENTURION UNIVERSITY OF TECHNOLOGY AND MANAGEMENT
ODISHA

MAY 2024
 BONAFIDE CERTIFICATE

Certified that this project report “Minimum Spanning Tree In a Given Weighted

Graph Using Kruskal’s Algorithm” is the bonafide work of “Aditya Kumar” who

carried out the project work under my supervision. This is to further certify to the best

of my knowledge, that this project has not been carried out earlier in this institute and

the university.

<<Signature of the Supervisor>>

SIGNATURE
SIGNATURE
(EXTERNAL) (Dr. Aditya Kumar Pati)
Assistant Professor
Department of Mathematics,
School of Applied Sciences,
CUTM, PKD

Certified that the above-mentioned project has been duly carried out as per the
norms of the college and statutes of the university.

SIGNATURE
(Prof. Debendra Maharana)

Head of the Department /Dean Of The School

DEPARTMENT SEAL
 DECLARATION

I hereby declare that the project entitled “Minimum Spanning Tree In a Given Weighted

Graph Using Kruskal’s Algorithm” submitted for the “Discrete Mathematics” of 2nd

semester B. Tech in Computer Science and Engineering is my original work and the

project has not formed the basis for the award of any Degree / Diploma or any other

similar titles in any other University/Institute.

Name of the Student: Aditya Kumar

Signature of the Student:

Registration No: 230101120287

Place: Paralakhemundi

Date:
 ACKNOWLEDGEMENTS

I wish to express my profound and sincere gratitude to Prof. Aditya Kumar Pati
Department of Mathematics, SoAS, Paralakhemundi Campus, who guided me into the
intricacies of this project nonchalantly with matchless magnanimity.

I thank Prof. Debendra Maharana, Head of the Department of Computer Science

and Engineering, SoET, Paralakhemundi Campus and Prof. Prafulla Kumar Panda,
Dean, School of Engineering and Technology, Paralakhemundi Campus for extending
their support during Course of this investigation.

Name of the Student: Aditya Kumar

Signature of the Student:

Registration No: 230101120287

Place: Paralakhemundi

Date:
 Contents

Chapter 1 Introduction
1.1 Brief overview of the topic

1.2 Importance of studying

Kruskal’s Algorithm

Chapter 2 Methodology
2.1 Implementation along with

example

Chapter 3 Results
3.1 Readings

Chapter 4 Discussion
4.1 Discussion

Conclusion
 ABSTRACT

Kruskal's algorithm is a pivotal tool in the realm of graph theory, specifically

designed for finding the minimum spanning tree (MST) of a connected, undirected graph. In
this abstract, we delve into the core concepts and workings of Kruskal's algorithm,
illuminating its efficiency and effectiveness in generating the optimal MST.

The algorithm operates by iteratively selecting the smallest edge from the graph while
ensuring that the selected edges do not form cycles. This process continues until all vertices
are encompassed within the MST. By prioritizing edges based on their weights, Kruskal's
algorithm guarantees the construction of a tree with the minimum possible total weight.

Our abstract further investigates the algorithm's computational complexity,

highlighting its time complexity of O(E log E), where E represents the number of edges in the
graph. This efficient time complexity renders Kruskal's algorithm suitable for large-scale
graphs, offering a practical solution for diverse real-world applications, including network
design, transportation planning, and circuit layout optimization.

Moreover, we explore the algorithm's versatility, as it can be implemented using

various data structures such as disjoint-set data structures, facilitating seamless integration
into different programming paradigms.

In conclusion, Kruskal's algorithm stands as a cornerstone in the arsenal of graph

algorithms, providing a robust and efficient method for deriving the minimum spanning tree,
thereby underlining its significance in the domain of optimization and algorithmic design.
 Chapter-1
Introduction

1.1 Brief overview of the topic: -

In the vast landscape of graph theory, the pursuit of optimal solutions to fundamental
problems is a central theme driving innovation and advancement. One such problem is the
quest for the minimum spanning tree (MST) in a connected, undirected graph—a challenge
with wide-ranging applications spanning from network infrastructure planning to logistical
optimization. At the forefront of solutions to this problem stands Kruskal's algorithm, a
cornerstone algorithm renowned for its efficiency and simplicity.

Kruskal's algorithm operates on the principle of greediness, iteratively selecting the

smallest edge available while ensuring that no cycles are formed until all vertices are
encompassed within the MST. This elegant approach guarantees the construction of a tree
with the minimum possible total weight—a characteristic that makes Kruskal's algorithm
indispensable in scenarios where resource optimization is paramount.

One of the most compelling aspects of Kruskal's algorithm is its computational

efficiency. With time complexity of O(E log E), where E represents the number of edges in
the graph, the algorithm scales effectively even for large-scale graphs, making it a practical
choice for real-world applications. Furthermore, Kruskal's algorithm offers versatility in
implementation, accommodating various data structures such as disjoint-set data structures,
which enhances its adaptability to different programming paradigms and environments.

Beyond its technical intricacies, Kruskal's algorithm holds profound implications for
problem-solving across diverse domains. From designing cost-effective communication
networks to optimizing supply chain logistics, the algorithm empowers practitioners with a
powerful tool for tackling complex optimization challenges.

In this exploration, we delve into the inner workings of Kruskal's algorithm,

unraveling its principles, examining its computational efficiency, and highlighting its
practical applications. Through this journey, we aim to showcase the enduring relevance and
significance of Kruskal's algorithm in the realm of optimization and algorithmic design.

1.2 Importance of studying “Kruskal’s Algorithm” :-

Studying Kruskal's Algorithm offers a myriad of benefits and holds significant importance in
the field of computer science and beyond. Here's why:

1. Fundamental Understanding of Graph Theory: Kruskal's Algorithm provides a concrete

example of graph theory principles in action. By studying this algorithm, learners gain
insights into fundamental concepts such as spanning trees, connectivity, and graph traversal,
which form the bedrock of graph theory.
2. Optimization Techniques: Kruskal's Algorithm embodies the essence of optimization
techniques by efficiently solving the problem of finding the minimum spanning tree in a
graph. Understanding its workings equips learners with valuable skills in algorithmic
optimization, which are applicable across various domains, including computer science,
engineering, and operations research.

3. Algorithmic Problem-Solving Skills: Analyzing Kruskal's Algorithm enhances one's

problem-solving abilities. By dissecting its steps, understanding its complexities, and
exploring its variations, learners develop a systematic approach to problem-solving that
transcends the specific application domain of graph theory.

4. Real-World Applications: The practical applications of Kruskal's Algorithm are

widespread, ranging from network design and optimization to logistics planning and resource
allocation. Studying this algorithm provides insights into real-world scenarios where efficient
solutions to spanning tree problems are crucial.

5. Algorithmic Design Principles: Kruskal's Algorithm exemplifies key algorithmic design

principles such as greedy algorithms and disjoint-set data structures. Delving into its design
rationale and implementation details enhances learners' understanding of these principles,
which can be applied to solve a wide array of computational problems.

6. Computational Complexity Analysis: Kruskal's Algorithm offers a platform for studying

computational complexity. Analyzing its time complexity and space requirements fosters a
deeper understanding of algorithmic efficiency, enabling learners to evaluate and compare
different algorithms for solving similar problems.

7. Interdisciplinary Insights: The study of Kruskal's Algorithm transcends disciplinary

boundaries, offering insights that are valuable across diverse fields such as mathematics,
computer science, engineering, and operations research. Its principles find applications in
fields as varied as biology, sociology, and economics.

In essence, studying Kruskal's Algorithm enriches learners with a holistic

understanding of fundamental graph theory concepts, algorithmic optimization techniques,
and their real-world applications, thereby fostering analytical thinking, problem-solving
skills, and interdisciplinary insights.
 Chapter-2
Methodology

 Introduction to Minimum Spanning Tree:-

In the realm of graph theory, the concept of a minimum spanning tree (MST) serves
as a linchpin for understanding connectivity, optimization, and algorithmic efficiency. A
minimum spanning tree of a connected, undirected graph is a subgraph that encompasses all
vertices with the minimum possible total edge weight, forming a tree without any cycles. This
foundational concept finds widespread applications in diverse fields, including network
design, transportation planning, and circuit layout optimization.

The quest for finding an MST entails not only theoretical exploration but also
practical algorithmic solutions. Several algorithms have been devised to tackle this problem
efficiently, each offering unique insights into graph traversal, optimization strategies, and
computational complexity. Understanding the principles underlying minimum spanning trees
and the algorithms used to find them not only enhances one's grasp of graph theory
fundamentals but also equips individuals with invaluable problem-solving skills applicable
across various domains. In this exploration, we embark on a journey to unravel the
significance, applications, and algorithmic intricacies of minimum spanning trees, shedding
light on their pivotal role in the landscape of optimization and algorithmic design.

 Implementation of Kruskal’s Algorithm:-

Let’s understand with and example how to find the minimum cost spanning tree suing
Kruskal’s Algorithm

 Input Graph:
The Graph contains 9 vertices and 14 edges. So, the minimum
spanning tree formed will be having (9-1) = 8 edges.
After
sorting Weight Source Destination
we 1 7 6
get:-
2 8 2
2 6 5
4 0 1
4 2 5
6 8 6
7 2 3
7 7 8
8 0 7
8 1 2
9 3 4
10 5 4
11 1 7
14 3 5

Now pick all edges one by one from the sorted list of edges.
◦ Step 1: Pick edge 7-6. No cycle is formed, include it.
◦ Step 2: Pick edge 8-2. No cycle is formed, include it.

◦ Step 3: Pick edge 6-5. No cycle is formed, include it.

◦ Step 4: Pick edge 0-1. No cycle is formed, include it.

◦ Step 5: Pick edge 2-5. No cycle is formed, include it.

◦ Step 6: Pick edge 8-6. Since including this edge results in the cycle,
discard it. Pick edge 2-3: No cycle is formed, include it.

◦ Step 7: Pick edge 7-8. Since including this edge results in the cycle,
discard it. Pick edge 0-7. No cycle is formed, include it.

◦ Step 8: Pick edge 1-2. Since including this edge results in the cycle,
discard it. Pick edge 3-4. No cycle is formed, include it.
 Chapter 3
Results

We triumphantly employed Kruskal's algorithm to unearth the minimum

spanning tree (MST) within the provided graph. This graph boasts 9 vertices,
intricately connected by 14 edges. The MST we meticulously constructed comprises
8 judiciously chosen edges, forming a crucial structure that efficiently connects all
vertices while boasting the coveted minimum total weight.
1. Minimum Spanning Tree Edges:
 Here, meticulously enumerate each edge incorporated into the MST. For each
edge, provide details including the source vertex, destination vertex, and the
corresponding weight.
o For instance: (7, 6, 1) - This signifies an edge connecting vertex 7 to
vertex 6 with a weight of 1.
2. Total Weight:
 Calculate and report the total weight of the minimum spanning tree. Achieve
this by meticulously summing the weights of all edges included within the
MST.
3. Key Insights:
 Concisely reiterate the fundamental steps that underpin Kruskal's algorithm
for uncovering the MST.
 Mention the time complexity of Kruskal's algorithm, which is famously O(E log
V), where E represents the number of edges and V represents the number of
vertices.
4. Real-World Applications:
 Bridge the gap between the theoretical concept of minimum spanning trees
and their practical applications in the real world. Here are some captivating
examples:
o Network Design: Imagine a vast communication network. By
leveraging Kruskal's algorithm, we can strategically design a network
layout that minimizes the total length of cables required for
connections, leading to cost savings and improved efficiency.
o Transportation Planning: Envision a complex transportation network
encompassing numerous cities. Kruskal's algorithm empowers us to
design the most efficient network of roads or railways, ensuring all
cities are connected while minimizing the total distance travelled.
 Chapter 4
Discussions

Kruskal's algorithm effectively identified the minimum spanning tree (MST) for
the given graph. This accomplishment underscores the algorithm's prowess in
efficiently connecting all vertices while minimizing the total edge weight. However,
exploring some additional aspects can further enrich our understanding.
 Alternative Algorithms:
Kruskal's algorithm is not the solitary contender in the realm of MST
algorithms. Prim's algorithm offers another well-regarded approach. While both
algorithms achieve the same objective, they possess distinct characteristics. Briefly
discussing Prim's algorithm and comparing its time and space complexity to
Kruskal's can illuminate the nuances of selecting the most suitable algorithm for a
specific problem.
 Scalability and Practical Considerations:
The provided graph served as a valuable illustration, but real-world graphs
can be significantly larger and more intricate. Kruskal's algorithm demonstrates
favorable scalability, boasting a time complexity of O(E log V). However, for
exceptionally massive graphs, even this complexity might become a concern.
Exploring advanced techniques like heuristics or approximation algorithms that can
handle enormous graphs efficiently could be a valuable discussion point.
 Error and Uncertainty:
In many real-world scenarios, edge weights might not be entirely
deterministic. Factors like traffic congestion in transportation networks or fluctuating
costs in material procurement can introduce uncertainty. Discussing how Kruskal's
algorithm, or MST algorithms in general, can be adapted to handle edge weights with
inherent error or probabilistic distributions can broaden the scope of the discussion.
  Limitations and Future Directions:
While MSTs are potent tools for optimization, they possess limitations. For
instance, MSTs prioritize minimizing total weight, but other factors, like maximizing
reliability or ensuring balanced connectivity, might be crucial in specific situations.
Exploring alternative graph optimization techniques that address these limitations or
introducing the concept of Steiner trees, which can incorporate additional points not
present in the original graph, could pave the way for future exploration.
By incorporating these discussion points, you can enrich your project by showcasing
a deeper understanding of the strengths and potential limitations of Kruskal's
algorithm, as well as its place within the broader landscape of graph optimization
techniques.

Conclusion
In conclusion, this project has comprehensively explored the application of
Kruskal's algorithm for finding the minimum spanning tree (MST) in a weighted
graph. We successfully implemented the algorithm on a sample graph,
demonstrating its effectiveness in efficiently connecting all vertices while minimizing
the total edge weight.
Kruskal's algorithm boasts a favorable time complexity of O(E log V), making
it suitable for various real-world applications, including network design and
transportation planning. We delved into the practical significance of MSTs and how
Kruskal's algorithm empowers us to optimize resource allocation in these scenarios.
The discussion section highlighted the existence of alternative MST algorithms like
Prim's algorithm, prompting consideration of factors like scalability and error handling
in edge weights for real-world problem-solving. We explored potential limitations of
MSTs and acknowledged the existence of alternative graph optimization techniques
that address these limitations.
By studying Kruskal's algorithm, we gained valuable insights into graph theory
concepts, optimization techniques, and algorithmic design principles. This project
has equipped us with a deeper understanding of how algorithmic solutions can be
employed to address optimization challenges in various domains. Future exploration
could involve delving into more intricate graph structures, distributed algorithms, or
even exploring the applications of MSTs in other scientific disciplines.
ASSESSMENT
Internal:
SL FULL
RUBRICS MARKS OBTAINED REMARKS
NO MARK
Understanding the relevance, scope and
1 10
dimension of the project
2 Methodology 10
3 Quality of Analysis and Results 10
4 Interpretations and Conclusions 10
5 Report 10
Total 50

Date: Signature of the Faculty

COURSE OUTCOME (COs) ATTAINMENT

➢ Expected Course Outcomes (COs):

(Refer to COs Statement in the Syllabus)

____________________________________________________________________________
____
____________________________________________________________________________
____

____________________________________________________________________________
____
____________________________________________________________________________
____
➢ Course Outcome Attained:
How would you rate your learning of the subject based on the specified COs?

1 2 3 4 5 6 7 8 9 10
LOW HIGH
➢ Learning Gap (if any):
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________
___________________________________________________________________________

➢ Books / Manuals Referred:

____________________________________________________________________________
____
____________________________________________________________________________
____

____________________________________________________________________________
____
____________________________________________________________________________
____

Date: Signature of the Student

➢ Suggestions / Recommendations:
(By the Course Faculty)
____________________________________________________________________________
____
____________________________________________________________________________
____

____________________________________________________________________________
____
____________________________________________________________________________
____

Date: Signature of the Faculty