Steffen Beyer > Graph-Kruskal-2.0 > Graph::Kruskal

Download:
Graph-Kruskal-2.0.tar.gz

Dependencies

Annotate this POD

Related Modules

Inline::C
more...
By perlmonks.org

CPAN RT

Open  0
Stalled  1
View/Report Bugs
Module Version: 2.0   Source  

NAME ^

Graph::Kruskal - Kruskal's Algorithm for Minimal Spanning Trees in Graphs

Computes the Minimal Spanning Tree of a given graph according to some cost function defined on the edges of the graph.

SYNOPSIS ^

DESCRIPTION ^

This algorithm computes the Minimal Spanning Tree of a given graph according to some cost function defined on the edges of that graph.

Input: A set of vortices which constitute a graph (some cities on a map, for example), a set of edges (i.e., roads) between the vortices of the (non-directed and connected) graph (i.e., the edges can be traveled in either direction, and a path must exist between any two vortices), and the cost of each edge (for instance, the geographical distance).

Output: A set of edges forming a spanning tree (i.e., a set of edges linking all vortices, so that a path exists between any two vortices) which is free of circles (because it's a tree) and which is minimal in terms of the cost function defined on the set of edges.

See Aho, Hopcroft, Ullman, "The Design and Analysis of Computer Algorithms" for more details on the algorithm.

SEE ALSO ^

Math::MatrixBool(3), Math::MatrixReal(3), DFA::Kleene(3), Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3).

VERSION ^

This man page documents "Graph::Kruskal" version 2.0.

AUTHOR ^

Steffen Beyer <sb@sdm.de>.

COPYRIGHT ^

Copyright (c) 1995, 1996, 1997 by Steffen Beyer. All rights reserved.

LICENSE ^

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

syntax highlighting: