THE TWO MAJOR SEARCH METHODS IN GRAPH THEORY

Sometimes it is important to visit all reachable nodes in a graph, either directed or undirected, starting from a given node. Instead of search it might be called an "all nodes visitor."  In most situations discussed in this volume all nodes are reachable from the given node, which makes the graph connected. Nodes will be given labels, 0 if not visited yet, and 1 if it has been visited.  No node will be given the label 1 more than once. Without any restrictions on the links of the graph, the search will eventually assign a label 1 to every node in the graph.

The given node has several names depending on how the graph will be processed.  It is called a "root", "source" and "entry node". In many labeled graphs in this volume it is assigned the integer-label 1. In this discussion it is called the "start node" or simply "start.' 





Breath-First-Search (BFS)