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. Edges can not be clicked. Clicking other nodes is not permitted after selecting a node. A button called "Next" can be clicked to execute next step of BFS.

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

1. 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.

1. You can now click on "Next" button and the algorithm will select any of the candidate edges randomly, to add that edge to the spanning tree.
2. The simulator will loop through the steps of BFS, printing instructions at every step.
3. Once 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 be able to click "NEXT" any more.