CSC 3102 Chapter : Csc3102GraphTraversal
Document Summary
Many important problems require an examination (visit) of the vertices of a graph. Bread- rst search and depth- rst search are the two most common traversal strategies. The strategy underlying breadth- rst search is to visit all unvisited vertices adjacent to a given vertex before moving on. It is easily implemented by visiting these adjacent vertices and then enqueueing them. A vertex is then dequeued and the process is repeated. The algorithm below may be used to obtain the breadth- rst tree of a connected graph. A l g o r i t h m : bfs (g , v ) Q is a queue mark all v e r t i c e s 0 if g is not empty mark v 1. Q . enqueue ( w ) e n d a l g o r i t h m. A l g o r i t h m : bft ( g )
