TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
kruskals_minimum_spanning_tree.cpp File Reference

Kruskals Minimum Spanning Tree implementation More...

#include <array>
#include <iostream>
#include <limits>
#include <cstdint>
Include dependency graph for kruskals_minimum_spanning_tree.cpp:

Go to the source code of this file.

Namespaces

namespace  greedy_algorithms
 for string class

Functions

template<typename T, std::size_t N, std::size_t M>
void greedy_algorithms::findMinimumEdge (const T &infinity, const std::array< std::array< T, N >, M > &graph)
 Finds the minimum edge of the given graph.
static void test ()
 Self-test implementations.
int main ()
 Main function.

Detailed Description

Kruskals Minimum Spanning Tree implementation

Quoted from Simplilearn.

Kruskal’s algorithm is the concept that is introduced in the graph theory of discrete mathematics. It is used to discover the shortest path between two points in a connected weighted graph. This algorithm converts a given graph into the forest, considering each node as a separate tree. These trees can only link to each other if the edge connecting them has a low value and doesn’t generate a cycle in MST structure.

Author
coleman2246

Definition in file kruskals_minimum_spanning_tree.cpp.

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit

Definition at line 184 of file kruskals_minimum_spanning_tree.cpp.

184 {
185 test(); // run Self-test implementation
186 return 0;
187}
test
static void test()
Self-test implementations.
Definition kruskals_minimum_spanning_tree.cpp:64

◆ test()

void test ( )
static

Self-test implementations.

Returns
void

define a large value for int define a large value for float define a large value for double define a large value for uint32_t

Definition at line 64 of file kruskals_minimum_spanning_tree.cpp.

64 {
71 constexpr int INFINITY_INT = std::numeric_limits<int>::max();
72 constexpr float INFINITY_FLOAT = std::numeric_limits<float>::max();
73 constexpr double INFINITY_DOUBLE = std::numeric_limits<double>::max();
74 constexpr uint32_t INFINITY_UINT32 = UINT32_MAX;
75
76 // Test case with integer values
77 std::cout << "\nTest Case 1 :\n";
78 std::array<std::array<int, 6>, 6> graph1{
79 0, 4, 1, 4, INFINITY_INT, INFINITY_INT,
80 4, 0, 3, 8, 3, INFINITY_INT,
81 1, 3, 0, INFINITY_INT, 1, INFINITY_INT,
82 4, 8, INFINITY_INT, 0, 5, 7,
83 INFINITY_INT, 3, 1, 5, 0, INFINITY_INT,
84 INFINITY_INT, INFINITY_INT, INFINITY_INT, 7, INFINITY_INT, 0};
85 greedy_algorithms::findMinimumEdge(INFINITY_INT, graph1);
86
87 // Test case with floating values
88 std::cout << "\nTest Case 2 :\n";
89 std::array<std::array<float, 3>, 3> graph2{
90 0.0f, 2.5f, INFINITY_FLOAT,
91 2.5f, 0.0f, 3.2f,
92 INFINITY_FLOAT, 3.2f, 0.0f};
93 greedy_algorithms::findMinimumEdge(INFINITY_FLOAT, graph2);
94
95 // Test case with double values
96 std::cout << "\nTest Case 3 :\n";
97 std::array<std::array<double, 5>, 5> graph3{
98 0.0, 10.5, INFINITY_DOUBLE, 6.7, 3.3,
99 10.5, 0.0, 8.1, 15.4, INFINITY_DOUBLE,
100 INFINITY_DOUBLE, 8.1, 0.0, INFINITY_DOUBLE, 7.8,
101 6.7, 15.4, INFINITY_DOUBLE, 0.0, 9.9,
102 3.3, INFINITY_DOUBLE, 7.8, 9.9, 0.0};
103 greedy_algorithms::findMinimumEdge(INFINITY_DOUBLE, graph3);
104
105 // Test Case with negative weights
106 std::cout << "\nTest Case 4 :\n";
107 std::array<std::array<int, 3>, 3> graph_neg{
108 0, -2, 4,
109 -2, 0, 3,
110 4, 3, 0};
111 greedy_algorithms::findMinimumEdge(INFINITY_INT, graph_neg);
112
113 // Test Case with Self-Loops
114 std::cout << "\nTest Case 5 :\n";
115 std::array<std::array<int, 3>, 3> graph_self_loop{
116 2, 1, INFINITY_INT,
117 INFINITY_INT, 0, 4,
118 INFINITY_INT, 4, 0};
119 greedy_algorithms::findMinimumEdge(INFINITY_INT, graph_self_loop);
120
121 // Test Case with no edges
122 std::cout << "\nTest Case 6 :\n";
123 std::array<std::array<int, 4>, 4> no_edges{
124 0, INFINITY_INT, INFINITY_INT, INFINITY_INT,
125 INFINITY_INT, 0, INFINITY_INT, INFINITY_INT,
126 INFINITY_INT, INFINITY_INT, 0, INFINITY_INT,
127 INFINITY_INT, INFINITY_INT, INFINITY_INT, 0};
128 greedy_algorithms::findMinimumEdge(INFINITY_INT, no_edges);
129
130 // Test Case with a non-connected graph
131 std::cout << "\nTest Case 7:\n";
132 std::array<std::array<int, 4>, 4> partial_graph{
133 0, 2, INFINITY_INT, 6,
134 2, 0, 3, INFINITY_INT,
135 INFINITY_INT, 3, 0, 4,
136 6, INFINITY_INT, 4, 0};
137 greedy_algorithms::findMinimumEdge(INFINITY_INT, partial_graph);
138
139 // Test Case with Directed weighted graph. The Krushkal algorithm does not give
140 // optimal answer
141 std::cout << "\nTest Case 8:\n";
142 std::array<std::array<int, 4>, 4> directed_graph{
143 0, 3, 7, INFINITY_INT, // Vertex 0 has edges to Vertex 1 and Vertex 2
144 INFINITY_INT, 0, 2, 5, // Vertex 1 has edges to Vertex 2 and Vertex 3
145 INFINITY_INT, INFINITY_INT, 0, 1, // Vertex 2 has an edge to Vertex 3
146 INFINITY_INT, INFINITY_INT, INFINITY_INT, 0}; // Vertex 3 has no outgoing edges
147 greedy_algorithms::findMinimumEdge(INFINITY_INT, directed_graph);
148
149 // Test case with wrong input passed
150 std::cout << "\nTest Case 9:\n";
151 std::array<std::array<int, 4>, 3> graph9{
152 0, 5, 5, 5,
153 5, 0, 5, 5,
154 5, 5, 5, 5};
155 greedy_algorithms::findMinimumEdge(INFINITY_INT, graph9);
156
157 // Test case with all the same values between every edge
158 std::cout << "\nTest Case 10:\n";
159 std::array<std::array<int, 5>, 5> graph10{
160 0, 5, 5, 5, 5,
161 5, 0, 5, 5, 5,
162 5, 5, 0, 5, 5,
163 5, 5, 5, 0, 5,
164 5, 5, 5, 5, 0};
165 greedy_algorithms::findMinimumEdge(INFINITY_INT, graph10);
166
167 // Test Case with uint32_t values
168 std::cout << "\nTest Case 11 :\n";
169 std::array<std::array<uint32_t, 4>, 4> graph_uint32{
170 0, 5, INFINITY_UINT32, 9,
171 5, 0, 2, INFINITY_UINT32,
172 INFINITY_UINT32, 2, 0, 6,
173 9, INFINITY_UINT32, 6, 0};
174 greedy_algorithms::findMinimumEdge(INFINITY_UINT32, graph_uint32);
175
176 std::cout << "\nAll tests have successfully passed!\n";
177}
greedy_algorithms::findMinimumEdge
void findMinimumEdge(const T &infinity, const std::array< std::array< T, N >, M > &graph)
Finds the minimum edge of the given graph.
Definition kruskals_minimum_spanning_tree.cpp:38