Kruskal.H File Reference

Kruskal's minimum spanning tree algorithm. More...

#include <ahFunction.H>
#include <tpl_agraph.H>
#include <tpl_graph_utils.H>
#include <tpl_test_acyclique.H>
#include <tpl_union.H>
#include <ah-errors.H>

Include dependency graph for Kruskal.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >
	Computes the minimum spanning tree of a graph using Kruskal's algorithm. More...
struct	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Init_Node
	Helper struct for initializing node counters during DFS. More...
struct	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Paint_Filt< G, GT_SA >
	Filter for arcs painted by Kruskal's algorithm. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Kruskal's minimum spanning tree algorithm.

Implements Kruskal's algorithm for finding minimum spanning trees using union-find data structure. Sorts edges by weight and greedily adds edges that don't create cycles. O(E log E) complexity.

Author

Leandro Rabindranath León

Definition in file Kruskal.H.