kruskal.h File Reference

Implements Kruskal's algorithm to compute the Minimum Spanning Tree (MST) of a weighted undirected graph. More...

#include <algorithm>
#include <functional>
#include <map>
#include "GraphLib/internal/concepts.h"

Go to the source code of this file.

Functions
template<Internal::valid_weighted_undirected_graph_type G>
G	GraphLib::kruskal (const G &graph)
	Computes the Minimum Spanning Tree of a weighted undirected graph using Kruskal's algorithm.

Detailed Description

Implements Kruskal's algorithm to compute the Minimum Spanning Tree (MST) of a weighted undirected graph.

Provides a templated function that uses the union-find data structure to efficiently find the MST.

Definition in file kruskal.h.