:

## Kruskal's Algorithm for finding a Minimum Spanning Tree

One thing I enjoy is implementing algorithms in Maple. The latest thing I worked on was Kruskal's Algorithm for finding a minimum spanning tree in a connected and weighted graph. It was something we covered in my summer math class which covered topics in discrete math. Here is a link to the algorithm in the application center: http://www.maplesoft.com/applications/app_center_view.aspx?AID=2133 I believe I have implemented the cycle-detection correctly; but I think there is likely a more efficient way. I may update it later if I come up with a better way. Basically, if there are k vertices in the graph ... I keep a table with k elements to keep track of the "tree" that any particular vertex belongs to. Initially each vertex belongs to a tree containing only itself. When an edge is added to the spanning tree; I modify the table. For example; if I add an edge which connects vertex 1 and 2. I pick vertex 2; and change its tree to be that of vertex 1. I also change any other element which was previously considered to be in the same tree as vertex 2; to also now be considered in the tree of vertex 1. So, once the algorithm is done ... all vertexes belong to the same tree. I think perhaps there is a way to avoid the scan of the table each time an edge is added to the spanning tree.

﻿