In this chapter, we study the behavior of stochastic search algorithms on an important graph problem. We consider the well-known problem of computing a minimum spanning tree in a given undirected connected graph with n vertices and m edges. The problem has many applications in the area of network design. Assume that we have n computers that should be connected with minimum cost, where costs of a certain amount occur when one computer is connected to another one. The cost for a connection can, for example, be the distance between two considered computers. One needs to make n−1 connections between these computers such that all computers are able to communicate with each other. Considering a graph as a model for a possible computer network, it has n vertices and one searches for the set of edges with minimal cost that makes the graph connected.