# 1146. Data Structure - Minimum Spanning Tree - DraftMST

Implement minimum spanning tree.

## 1. Spanning Tree

Spanning tree can be defined as a sub-graph of connected, undirected graph G that is a tree produced by removing the desired number of edges from a graph. In other words, Spanning tree is a non-cyclic sub-graph of a connected and undirected graph G that connects all the vertices together. A graph G can have multiple spanning trees.

## 2. Minimum Spanning Tree

There can be weights assigned to every edge in a weighted graph. However, A minimum spanning tree is a spanning tree which has minimal total weight. In other words, minimum spanning tree is the one which contains the least weight among all other spanning tree of some particular graph.

Shortest path algorithms In this section of the tutorial, we will discuss the algorithms to calculate the shortest path between two nodes in a graph.

## 3. Implementation of Minimum Spanning Trees

A minimum spanning tree (MST) is a graph with the minimum number of edges necessary to connect the vertices.

public class MinimumSpanningTree {
private int MAX_VERTS = 0;
private Vertex[] vertexList; // array of vertices
private int nVerts; // current number of vertices

public MinimumSpanningTree(int maxverts)
{
MAX_VERTS = maxverts; // maximum number of vertices
vertexList = new Vertex[MAX_VERTS];
nVerts = 0;

// initialize matrix
for(int i=0; i<MAX_VERTS; i++) {
for(int j=0; j<MAX_VERTS; j++) {
}
}
}

int index = nVerts++;
vertexList[index] = new Vertex(index, label);
}

public void addEdge(int start, int end) {
}

public Vertex[] getVertices() {
return vertexList;
}

}

public void displayVertex(int index) {
System.out.print(vertexList[index].name);
}

// mst, similar with dfs
private Stack<Vertex> stack = new Stack<Vertex>();
public void mst() {
vertexList[0].visited = true; // different start vertex leads to different mst.
stack.push(vertexList[0]);
while (!stack.isEmpty()) {
int currentVertex = stack.peek().index;
if (index == -1) { // no unvisited neighbor
stack.pop();
} else {
vertexList[index].visited = true;
stack.push(vertexList[index]);
displayVertex(currentVertex);
displayVertex(index);
System.out.print(" ");
}
}

// reset vertices
for (int i=0; i<nVerts; i++) {
vertexList[i].visited = false;
}
}

for (int i=0; i<nVerts; i++) {
if (adjMatrix[index][i] == 1 && vertexList[i].visited == false) {
return i;
}
}
return -1;
}
}


Test Junit.

public void testMST() {
System.out.println("testMST");
/*
Vertex | A | B | C | D | E
-------|---|---|---|---|---
A      | 0 | 1 | 0 | 1 | 0
B      | 1 | 0 | 1 | 0 | 0
C      | 0 | 1 | 0 | 0 | 0
D      | 1 | 0 | 0 | 0 | 1
E      | 0 | 0 | 0 | 1 | 0
*/
MinimumSpanningTree mst = new MinimumSpanningTree(5);