A-level Computing/AQA/Paper 1/Fundamentals of algorithms/Graph traversal

Tree traversal Breadth-first traversal Breadth frist search|thumb|center Breadth-first search is an algorithm that visits graph vertices by exploring nodes at successively further away levels. You could think of it as a wave that radiates outwards from the starting node. A typical application of BFS is finding the shortest path for an unweighted graph. Enqueue the source node or nodes that make up the set of starting nodes. Dequeue a node and examine it. If the element sought is found in this node, quit the search and return a result. Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered. If the queue is empty, every node on the reachable sub-graph has been examined – quit the search and return "not found". If the queue is not empty, repeat from Step 2. Depth first traversal thumb|Depth first search|center Using a stack instead of a queue would turn this algorithm into a depth-first search. DFS travels down branches as far as possible, backtracking when it hits a dead end. A typical application of DFS is navigating a maze. The above method described is non-recursive, so in order to do post-order traversal, which is an important variation, instead of working on the current vertex after inserting all its children in the stack, insert it into a second stack. Then pop off the vertices in the second stack and operate on them in that order. If the graph and parent-child relationships represents a dependency relationship, e.g. a construction schedule for various trades, a curriculum of related units of study, then the order created by emptying the second stack creates a viable schedule.