��������

It is often necessary to interconnect several locations, buildings, or nodes to some common network or resource. These locations can be considered vertices in an undirected graph. The connections constitute the edges in the graph. The goal is then to construct a tree connecting all the vertices to span the graph. Each of the edges or connections carries a weight, and it is often too expensive to include all possible edges. Instead, we would like to find the tree that interconnects or “spans” the graph with a minimum total edge-weight. This is the minimum-spanning-tree (MST) of the graph.

We will examine two approaches to finding the minimum-spanning-tree: Kruskal’s algorithm and Prim’s algorithm. The first focuses on connecting disparate sub-trees with minimum-weight edges to build the MST. It considers all edges in the graph and includes those that create connections between disconnected sub-trees, while discarding those that would join already-connected vertices. The second focuses on expanding a tree by adding the next disconnected vertex with the lowest edge weight. It proceeds through the vertices, selecting the next-easiest (with the lowest weight edge) vertex to add to the tree. We will discuss the algorithms, their implementations, and examine how they generate an MST. We will also examine their application in generating mazes.

Dan Biediger is a lecturer in the Department of Computer Science at the University of Houston. He earned his PhD in Computer Science from the University of Houston studying the pursuit evasion problem between swarms of drones and defenders. He was among the first participants in the ATLANTIS program, an exchange between universities in the US and Europe. He earned a master’s degree from the University of Houston as well as a degree in Imagery and Vision from the University of Strasbourg in France. His background is originally in engineering, with bachelor’s degrees in Mechanical and Petroleum engineering from Texas A&M university. He makes frequent trips to National Parks in the US and around the world for night photography.