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. Candidate Edges can be clicked, to add those edge to the sub-graph. Clicking other nodes is not permitted after selecting a node. A button called "Backtrack" can be clicked to perform a backtrack operation.

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

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

You can select any of the candidate edges to, to visit the unexplored adjacent node, and add that edge to the spanning tree. The newly visited node will be pushed into the stack, and will now become the active node.
If you see, there are no candidate edges from the active node leading to an unvisited node, then you can click "Backtrack", to move back to the previous active node. Clicking "Backtrack" will remove the active node from the top of stack.
You need to remove all the elements from stack by Bactracking to the root.
If all the nodes are added to the tree and the stack becomes empty, DFS is finished and the spanning tree is complete and you will not see any candidate edges any more. Otherwise repeat step 1,2,3.