prim.h File Reference

The declaration of the functions needed to compute the MST with Prim's algorithm. More...

#include "../data_structures/mst.h"

Go to the source code of this file.

Functions
void	prim (const Graph *graph, MST *mst)
	The Prim algorithm to find the Minimum Spanning Tree O(|E| + |V| log |V|)

Detailed Description

The declaration of the functions needed to compute the MST with Prim's algorithm.

Author

Lorenzo Sciandra

This file contains the declaration of the Prim algorithm to find the Minimum Spanning Tree.

Version

1.0.0 @data 2024-05-1

Copyright

Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file prim.h.

Function Documentation

prim()

void prim	(	const Graph *	graph,
		MST *	mst
	)

The Prim algorithm to find the Minimum Spanning Tree O(|E| + |V| log |V|)

This is the implementation of the Prim algorithm with Fibonacci Heap to find the Minimum Spanning Tree. When the graph is large and complete, it is way faster than Kruskal's algorithm.

Parameters

graph	The Graph from which we want to find the MST.
mst	The Minimum Spanning Tree.

Definition at line 16 of file prim.c.