---

Kruskal< EdgeType > Class Template Reference

Represents Kruskal's algorithm for determining a Minimum Spanning Tree of a weighted graph and the required union/find data structure. More...

#include <kruskal.h>

List of all members.

Public Methods
	Kruskal (EdgeVector< EdgeType > &graph, MST &result)
	Computes a MST of a graph.
	~Kruskal ()
	The destructor.
Private Methods
void	computeMST ()
	Computes a MST of the graph.
void	initUnionFind ()
	Initializes the union/find data structure.
NodeID	find (NodeID node)
	Performs a find operation.
bool	unite (NodeID node1, NodeID node2)
	Performs a union operation.
Private Attributes
EdgeVector< EdgeType > &	_graph
	Reference to the given graph.
MST &	_result
	Reference to a MST object which stores the result.
std::vector< NodeID >	_parent
	A vector which contains for each node the identifier of the parent node.
std::vector< char >	_height
	A vector which contains for each node the height of the belonging tree.
EdgeCount	edgesAddedToResult
	Counts the number of edges which have been added to the resulting MST.

---

Detailed Description

template<typename EdgeType = Edge>
class Kruskal< EdgeType >

Represents Kruskal's algorithm for determining a Minimum Spanning Tree of a weighted graph and the required union/find data structure.

Definition at line 24 of file kruskal.h.

---

Constructor & Destructor Documentation

template<typename EdgeType = Edge> Kruskal< EdgeType >::Kruskal (  EdgeVector< EdgeType > &    graph, MST &    result )  [inline]

Computes a MST of a graph. Parameters: graph  a reference to an EdgeVector which represents the graph result  a reference to a MST object which stores the result Definition at line 32 of file kruskal.h. References Kruskal< EdgeType >::_graph, Kruskal< EdgeType >::_result, and Kruskal< EdgeType >::computeMST().

template<typename EdgeType = Edge> Kruskal< EdgeType >::~Kruskal (    )  [inline]

The destructor. The given graph is deleted. Definition at line 42 of file kruskal.h. References Kruskal< EdgeType >::_graph.

---

Member Function Documentation

template<typename EdgeType> NodeID Kruskal< EdgeType >::find (  NodeID    node )  [inline, private]

Performs a find operation. Path compression is applied. Parameters: node  the identifier of the node whose set should be determined Returns : the identifier of the canonical node which represents the set which "node" belongs to Definition at line 100 of file kruskal.h. References Kruskal< EdgeType >::_parent. Referenced by Kruskal< EdgeType >::unite().

template<typename EdgeType> bool Kruskal< EdgeType >::unite (  NodeID    node1, NodeID    node2 )  [inline, private]

Performs a union operation. Returns : true iff node1 and node2 have belonged to different sets Definition at line 122 of file kruskal.h. References Kruskal< EdgeType >::_height, Kruskal< EdgeType >::_parent, and Kruskal< EdgeType >::find(). Referenced by Kruskal< EdgeType >::computeMST().

---

Member Data Documentation

template<typename EdgeType = Edge> std::vector<char> Kruskal< EdgeType >::_height [private]

A vector which contains for each node the height of the belonging tree. Only the values of canonical nodes are relevant. Definition at line 84 of file kruskal.h. Referenced by Kruskal< EdgeType >::initUnionFind(), and Kruskal< EdgeType >::unite().

template<typename EdgeType = Edge> std::vector<NodeID> Kruskal< EdgeType >::_parent [private]

A vector which contains for each node the identifier of the parent node. The canonical node of a set (= the root of a tree) points to itself. Definition at line 78 of file kruskal.h. Referenced by Kruskal< EdgeType >::find(), Kruskal< EdgeType >::initUnionFind(), and Kruskal< EdgeType >::unite().

---

The documentation for this class was generated from the following files:

• kruskal.h
• kruskal.cpp

---