Graph traversals

Introduction#

All the algorithms related to Graph traversals. Their complexities, both runtime and space

Depth First Search

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 the steps for graph traversal using DFS:

Algorithm DFS(v);

Input: A vertex v in a graph

Output: A labeling of the edges as “discovery” edges and “backedges”

for each edge e incident on v do

    if edge e is unexplored then

    let w be the other endpoint of e
    if vertex w is unexplored then
        label e as a discovery edge
        recursively call DFS(w)
    else
    label e as a backedge

Breadth First Search

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
            BFS(G, v)