Objective

Given a connected graph, the objective of this system is to build a minimum spanning tree of the graph by selecting a subset of its edges.

Graph Color Codes

The table below, lists all the colors used in the graph, along with their interpretations.

Node/Edge Color	Type
	Unselected Node
	Selected Node
	Unselected Edge
	Selected Edge
	Cycle Forming Edge

Experiment Setup

In this system, you are provided with a connected graph. You can click on any edge to add the edge (and connecting nodes) to the sub-graph.

At any point while building the sub-graph, you can click on any edge to remove it from the tree.

Minimum Spanning Tree

A minimum spanning tree is a spanning tree of a graph, which has the minimum possible total edge weight.

Note :

You can reposition edges and nodes by dragging nodes if the labels are not visible due to overlapping.

Procedure

1. Pick a non-cycleforming edge, to add it to the sub-graph.
2. Check if all nodes have been added to the sub-graph and the weight of subgraph is least. If not, then either replace a higher weighted edge with a lesser one or repeat step 1. Otherwise Minimum Spanning Tree is completed.