Prim.H File Reference

Prim's algorithm for minimum spanning trees. More...

#include <tpl_agraph.H>
#include <tpl_graph_utils.H>
#include <archeap.H>
#include <ah-errors.H>
#include <cookie_guard.H>

Include dependency graph for Prim.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Prim_Info< GT >
struct	Aleph::Prim_Heap_Info< GT, Distance >
struct	Aleph::Simple_Prim_Heap< GT, Distance >
struct	Aleph::Init_Prim_Info< GT >
struct	Aleph::Uninit_Prim_Info< GT >
class	Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >
	Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Prim. More...

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

Macros
#define	PRIMINFO(p)   static_cast<Prim_Info<GT>*>(NODE_COOKIE(p))
#define	TREENODE(p)   (PRIMINFO(p)->tree_node)
#define	HEAPNODE(p)   (PRIMINFO(p)->heap_node)

Detailed Description

Prim's algorithm for minimum spanning trees.

This file implements Prim's algorithm for finding the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. The algorithm grows the MST one vertex at a time, always adding the minimum-weight edge that connects a vertex in the tree to a vertex outside.

Algorithm Overview

1. Start with an arbitrary vertex
2. Maintain a priority queue of edges crossing the cut
3. Extract minimum-weight edge, add its endpoint to the tree
4. Add new crossing edges to the queue
5. Repeat until all vertices are in the tree

Key Features

• Finds minimum spanning tree for connected graphs
• Uses binary heap for efficient edge selection
• Supports custom distance/weight functions
• Works with both List_Graph and Array_Graph

Complexity

Implementation	Time	Space
Binary Heap	O(E log V)	O(V)

Comparison with Kruskal

Aspect	Prim	Kruskal
Best for	Dense graphs	Sparse graphs
Data structure	Priority queue	Union-Find
Edge processing	One at a time	All sorted first

Usage Example

List_Graph<Node, Arc> g;
// ... build connected graph ...
 
List_Graph<Node, Arc> mst;
Prim_Min_Spanning_Tree<decltype(g)> prim;
prim(g, mst);
 
// mst now contains the minimum spanning tree

See also

Kruskal.H Alternative MST algorithm (better for sparse graphs)

tpl_graph_utils.H For graph traversal utilities

Author

Leandro Rabindranath León

Definition in file Prim.H.

Macro Definition Documentation

HEAPNODE

#define HEAPNODE

(

p

)

(PRIMINFO(p)->heap_node)

Definition at line 116 of file Prim.H.

PRIMINFO

#define PRIMINFO

(

p

)

static_cast<Prim_Info<GT>*>(NODE_COOKIE(p))

Definition at line 114 of file Prim.H.

TREENODE

#define TREENODE

(

p

)

(PRIMINFO(p)->tree_node)

Definition at line 115 of file Prim.H.