Graph Searching

Back to Tutorials.

Tutorial Three: Solving a Graph

This tutorial will use the Simple Tree Graph to demonstrate the basics of solving graphs.
This tutorial will cover the rudimentary elements - After you load a pre-existing graph you can change the mode to the 'Solve' mode, in which you can solve the graph.
Your graph should now look like this:


When you change to Solve mode, a new panel at the bottom of the screen appears which contains the text stating which algorithm is selected and an area which contains the current path of the graph.

If you would like to modify the graph, click on the tab marked 'Create' to return to create mode.

The idea of searching is to find the path along the edges from a start node to a goal node. There are four ways to run a search algorithm.

1. Step : Each time the 'Step' button is clicked, the search advances to visit one node, which is the current node (selected from the first node on the frontier). The nodes on the frontier at the time and the neighbouring nodes of the current node are displayed on the graph.

2. Fine Step : One click on the 'Fine Step' button selects the first node on the current frontier to make it the current node. A second click displays all the neighbours of the current node. A third click adds the neighbours to the frontier and displays the updated frontier. Note that one click on the 'Step' button is equivalent to three clicks on 'Fine Step'.

3. Auto Search : Runs using the search algorithm selected and displays on the graph the order of each node being visited.

4. Quiz : This mode quizzes you on the search algorithm selected. You must click on the correct node that would be selected by the search algorithm on the graph. If the correct node is selected, the node is displayed as the current node, and its neighbours are added to the frontier. The process is repeated until there is no more node on the frontier or the 'Reset Search' button is clicked.

When you are stepping through a graph, the nodes on the graph change colors corresponding to the type of nodes they are. In the 'Help' menu you can click on 'Legend for Nodes/Edges' to make the legend below appear.


When you have found a goal node, a dialog box appears showing you the path to the goal node. The graph will look similar to this:


There are many different algorithms used to solve a graph and they differ in the way they choose the next node on the frontier.

To learn more about different searching algorithms, see Tutorial 4 on search options.

Explore the different search algorithms and see which algorithm will find the shortest path from the start node to the goal node. You can reset the graph after a goal node has been reached by clicking on the 'Reset Search' button.

For graphs with cycles in them you can change the path pruning options to either loop detection, multiple-path pruning or none. You can do this in the 'Search Options' menu.

To learn more about different pruning options, see Tutorial 4 on search options.

Valid HTML 4.0 Transitional