minimum spanning trees suppose that you've designed printed circuit board like the one shown in figure and you want to be sure you've used the minimum number of traces that isyou don' want any extra connections between pinssuch extra connections would take up extra room and make other circuits more difficult to lay out it would be nice to have an algorithm thatfor any connected set of pins and traces (vertices and edgesin graph terminology)would remove any extra traces the result would be graph with the minimum number of edges necessary to connect the vertices for examplefigure shows five vertices with an excessive number of edgeswhile figure shows the same vertices with the minimum number of edges necessary to connect them this constitutes minimum spanning tree (msta aextra edges figure bminimum number of edges minimum spanning tree there are many possible minimum spanning trees for given set of vertices figure shows edges abbccdand debut edges acceedand db would do just as well the arithmetically inclined will note that the number of edges in minimum spanning tree is always one less than the number of vertices ve= - remember that we're not worried here about the length of the edges we're not trying to find minimum physical lengthjust the minimum number of edges (this will change when we talk about weighted graphs in the next the algorithm for creating the minimum spanning tree is almost identical to that used for searching it can be based on either the depth-first search or the breadthfirst search in our example we'll use the depth-first search perhaps surprisinglyby executing the depth-first search and recording the edges you've traveled to make the searchyou automatically create minimum spanning tree the only difference between the minimum spanning tree method mst()which we'll see in momentand the depth-first search method dfs()which we saw earlieris that mst(must somehow record the edges traveled