Tutorial by Examples

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. Below algorithm presents th...

Algorithm BFS(G) Input graph G Output labeling of the edges and partition of the vertices of G for all u ∈ G.vertices() setLabel(u, UNEXPLORED) for all e ∈ G.edges() setLabel (e, UNEXPLORED) for all v ∈ G.vertices() if getLabel(v) = UNEXPLORED ...