1 Unweighted Graphs
For unweighted Graphs, a minimum spanning tree(MST) means that a graph with minimum number of edges to connect all the vertices.
the number of edges E in a minimum spanning tree is always one less than the number of vertices V: E = V – 1.
The path of the
DFS(depth-first search) through the graph must be a minimum spanning tree.
1.1 Java implement
public void mst() // minimum spanning tree (depth first) { // start at 0 vertexList[0].wasVisited = true; // mark it theStack.push(0); // push it while( !theStack.isEmpty() ) // until stack empty { // get stack top int currentVertex = theStack.peek(); // get next unvisited neighbor int v = getAdjUnvisitedVertex(currentVertex); if(v == -1) // if no more neighbors theStack.pop(); // pop it away else // got a neighbor { vertexList[v].wasVisited = true; // mark it theStack.push(v); // push it // display edge displayVertex(currentVertex); // from currentV displayVertex(v); // to v System.out.print(" "); } } // end while(stack not empty) // stack is empty, so we're done for(int j=0; j<nVerts; j++) // reset flags vertexList[j].wasVisited = false; } // end mst()