Objective

Given a connected graph, the objective of this system is to build a spanning tree of the graph via DFS 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
	Selected Node
	Active Node
	Unselected Edge
	Candidate Edge
	Selected Edge

Experiment Setup

In this system, you are provided with a connected graph. Stack is used as an auxillary data structure. You can click on any node to select it. Clicking on edges is not permitted. Clicking other nodes is not permitted after selecting a node. A button called "Next" can be clicked to execute next step of DFS.

Depth First Traversal

This traversal process traverses deeper into the graph, by exploring unvisited edges leaving out from the most recently visited vertex. When there is no deeper level to go in the graph, the algorithm moves back (backtrack) to the vertex from which current vertex was discovered,.

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

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, which is also the active node. Now, you will observe that the edges connected to the active node are marked as "candidates" (See the color codes table).

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 DFS, printing instructions at every step.
3. Once all the nodes are added to the tree and stack is empty, the DFS is finished and spanning tree is complete and you will not be able to click on "Next" any more.