Objective

Given a connected graph, the objective of this system is to build a spanning tree of the graph via BFS traversal of the graph.

Graph Color Codes

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

Node/Edge Color	Type
	Unselected Node
	Discovered Node
	Selected Node
	Unselected Edge
	Candidate Edge
	Selected Edge

Experiment Setup

In this system, you are provided with a connected graph. Queue is used as an auxillary data structure. Each element of Queue is set of all the unexplored children. You can click on any node to select it. Candidate Edges can be clicked, to add those edge to the sub-graph. Clicking other nodes is not permitted after selecting a node.

Breadth First Traversal

This traversal process traverses graph level by level, by exploring all unvisited edges leaving out from the most recently visited vertex. It explores the children's children only after exploring all the childrens.It discovers the nodes at the next level, and keeps track of them using Queue.

Procedure

Initial: Selecting the first node

Select the first node, to start building the spanning tree.The first node will be the root node for the BFS.

Expanding the Spanning Tree

After selecting the first node, you will see spanning tree beside the graph. At this point the tree has just the one selected node. Now, you will observe that the edges connected to the active node are marked as "candidates" (See the color codes table).

All the unexplored nodes reachable from current level are marked as "discovered"(See Color Code), and are pushed into the Queue.

Select any of the candidate edges to visit that node, and add that edge to the spanning tree. The newly visited node will be removed from the Queue.
Visit all the unexplored nodes at a level to start visiting the discovered nodes at the next level.
If all the nodes are added to the tree and the Queue is empty, the BFS is finished and spanning tree is complete and you will not see any candidate edges any more. Otherwise repeat step 1,2.