Minimum spanning tree detection on raster data

Abstract

Various real-life systems including transportation, infrastructure and social networks require the use of a graph data structure. These graphs usually consist of weighted edges, such as the distance between two intersections on a highway or the cost to establish a power line between two electricity distribution centers. Therefore, having correct weights (costs) assigned to the edges of a graph is an important issue. Assigning these weight values manually is a time-consuming task in a real-world application, since graphs may consist of thousands of edges. On the other hand, assuming distance to represent weight would over-simplify the problem, especially when a graph is representing a real-life spatial phenomenon such as modeling of infrastructure lines. Specifically, raster data should be utilized to model such real-life entities. This paper investigates the effectiveness of three different methods to determine the costs of a weighted graph when the purpose is to detect the minimum spanning tree, which is a tree structure that connects all nodes with minimum cost.