Scott Hurring » Code » Python » Minimum Spanning Tree (Prim's Algo) » v0.1

Download Code

mst_prim_v0.1.tgz
v0.1 alpha · Dec 09, 2004
(browse code)

Description

For homework in one of my CIS classes, it said to write out an algorithm using the Prim Minimum Spanning Tree.

I decided to take a crack at it with Python rather than pseudo-code, becuase i feel more comfortable reading something like PHP or Python than the quasi-pascal pseudo-code in the textbook.

I make absolutely no guarantee that this code is accurate or does justice to the algorithm... i've only tested it on one adjacency matrix (one that was printed in the textbook for the homework problem) and the algorithm gave me the correct answer for this particular adjacency matrix.

If you find bugs or feel like making improvements, please send the code back to me. Thanks.

Design

MST_Prim.py

TODO

Example

Given the adjacency matrix:

A = [ [0, 4, 0, 0, 0, 0, 0, 8, 0], \
      [4, 0, 8, 0, 0, 0, 0, 11,0], \
      [0, 8, 0, 7, 0, 4, 0, 0, 2], \
      [0, 0, 7, 0, 9, 14,0, 0, 0], \
      [0, 0, 0, 9, 0, 10,0, 0, 0], \
      [0, 0, 4, 14,10,0, 2, 0, 0], \
      [0, 0, 0, 0, 0, 2, 0, 1, 6], \
      [8, 11,0, 0, 0, 0, 1, 0, 7], \
      [0, 0, 2, 0, 0, 0, 6, 7, 0], \

Vertices:
a -> b
a -> h
h -> g
g -> f
f -> c
c -> i
c -> d
d -> e

Notes

Changelog2/ History

v0.1 - Initial release: Dec 09, 2004

Projects and Contributions