Like the traversal of binary trees, graph searches can be either depth-first or breadth-first. These two kinds of searches visit the nodes in different orders. When you watch the animation, notice that the depth-first search always follows the edges of the graph, but the breadth-first search does not.

A depth-first search is most often implemented with a recursive algorithm. When you watch the animation, notice that the arrow moves in the forward direction as the program goes deeper into the recursion and moves backward when it is backing out. A depth-first search follows one path of the graph until it can proceed no further. It then backs up until it finds a path that has not been visited and proceeds down that path until it comes to the end. The process continues until all reachable nodes have been visited.

The breadth-first search algorithm is very different. A breadth-first search visits all nodes that are one node away from the starting node first. It then visits all nodes that are two nodes away from the starting node and so on. Like the depth-first search, it continues until all reachable nodes have been visited.

Unlike binary trees, graphs do not have a root, so the search can begin at any node. Also, because graphs can contain cycles, it is necessary to mark each node as it is visited to prevent an endless loop around the cycle. When you watch this animation, notice that as each node of the graph is visited, it is marked with a black X, so that this node need not be visited again.

Another difference between tree traversals and graph searches is that the order of a graph search is not unique, there are many correct orders, because the order of visiting the adjacent nodes is not specified. Repeat either of the searches on the same set of data and you will notice the outcome is not necessarily the same. We should mention, however, the code provided for your study contains an algorithm which always takes the same path.