File Exchange

image thumbnail

Prims Algorithm

version 1.0.0.0 (1.59 KB) by Vikramaditya Kundur
Minimal spanning tree.

1 Download

Updated 30 Sep 2005

View License

In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree which includes every vertex of that graph. More generally, a spanning forest of an arbitrary undirected graph is a forest which includes every vertex of the graph. Spanning forests always exist, and can always be constructed so as to have exactly one tree for each connected component. In certain fields of graph theory, involving weighted graphs, it is often useful to find a minimal spanning tree.

Prim's algorithm builds a tree while having the graph connected at all times.

Prim's algorithm maintains two lists, EV which is the vertices already in the tree, and E, the list of edges that makes up the spanning tree. In determining current edges for the tree, we look for a node that's in EV, and on that isn't, such that its path is minimum.
EV = { 0 }

E = { }

while( E has < n-1 edges ) {

find (u,v) with least cost, such that
u is in EV and v isn't in EV

if no such edge exists, break

add v to EV

add (u,v) to E
}
On termination, if the graph is connected, EV will contain all the nodes in the graph, and E will contain the set edges comprising the minimum spanning tree.

Comments and Ratings (12)

Error using fscanf
Invalid file identifier. Use fopen to generate a valid file identifier.

Error in prim (line 12)
l = fscanf(fid, '%g %g', [1 1]) % Input matrix size from line 1

i have this error.please help me

Ricardo Leal

Fabrício Oliveira

I haven't seen the code yet, but looks like that will only get the optimum if you allow the algorithm gets also the edges where neither u or v are in EV...

Nicholas Thompson

Interesting read. I've implemented basically this algorithm in Dark Basic Pro. This code snippet creates a random set of "nodes" (or cities in this case) with non-overlapping eges (Connections in this case)...

<a href="http://codebase.dbp-site.com/code/prims-algorithm-grid-map-generator-24">Prims Algorithm in Dark Basic Pro</a>

John Smith

Easy to use.

xueli an

Zack Voulgaris

A bit amateurish. Otherwise, okay.

Nick Cheilakos

Veronika Schöpf

Updates

1.0.0.0

Found an error. Need to update with a new file.

MATLAB Release Compatibility
Created with R12.1
Compatible with any release
Platform Compatibility
Windows macOS Linux
Acknowledgements

Inspired: twelve pulse rectifier AC/DC