Graph Traversal

A graph traversal is an algorithm to visit every one in a graph once.
Depth-first search (DFS) starts at an arbitrary vertex and searches a graph as “deeply” as possible as early as possible.
Breadth-first search (BFS) starts by visiting an arbitrary vertex, then visits all vertices whose distance from the starting vertex is one, then all vertices whose distance from the starting vertex is two, and so on.
In a graph, unlike a tree, there may be several ways to get from one vertex to another. To prevent visiting vertices twice, each vertex may have a boolean field called “visited” that tells us if we have visited the vertex before.

Depth-First Search

With DFS, we visit a vertex $v$ , and then checks every vertex $w$ that can be reached by some edge $(v, w)$ from $v$ . If $w$ has not yet been visited, DFS visits it recursively.
https://xkcd.com/761/.
Just like with trees, we can distinguish pre-order and post-order DFS. In both cases, we mark a node visited before we visit other nodes. With pre-order DFS, we “visit” (print or do calculations on) a node before we “visit” other nodes. With post-order DFS, we “visit” a node after we “visit” other nodes. Generally, pre-order DFS is more common than post-order and is what we assume if the order is not specified.

Pseudocode for pre-order DSF:

dfs(v):
    v.visited = true
    visit(v)
    for each vertex w such that (v, w) ∈ E:
        if !w.visited:
            dfs(w)

Pseudocode for post-order DFS:

dfs(v):
    v.visited = true
    for each vertex w such that (v, w) ∈ E:
        if !w.visited:
            dfs(w)
    visit(v)

We could also implement depth-first search iteratively with a stack.

DFS is similar to a pre-order and post-order traversal on a tree.
As an example, suppose we do a DFS on this graph, starting at node $0$ .

Pre-order DFS would be $0,1,2,5,4,3,6,7,8$ .

Post-order DFS would be $3,4,7,6,8,5,2,1,0$ .
The running time of depth-first search is $O(|V| + |E|)$ on adjacency lists and $O(|V|^2)$ on adjacency matrix.

Breadth-First Search

Breadth-first search is similar to the level-order traversal, but we use it on a graph instead of a tree.
We select a vertex to start with. Using a queue, we visit all the vertices at distance 1 from the starting vertex, then all the vertices at distance 2, etc.

Pseudocode:

dfs(v):
    // assume all nodes are marked as not visited
    visit(v, nil)
    v.visited = true
    q = Queue()
    q.enqueue(v)
    while q is not empty:
        v = q.dequeue
        for each vertex w such that (v, w) ∈ E:
            if !w.visited:
                visit(w, v)
                w.visited = true
                q.enqueue(w)

The visit function now takes two parameters: the node we are visiting and where we came from. This allows us to do a computation such as finding the distance of the vertex from the starting vertex, or finding the shortest path between them.

visit(w, origin)
    w.parent = origin
    if origin == nil:
        w.depth = 0
    else:
        w.depth = origin.depth + 1

When an edge $(v, w)$ is traversed to visit the vertex $w$ , the depth of $w$ is set to the depth of $v$ plus one, and $v$ is set to become the parent of $w$ .

If the graph is an undirected tree, BFS performs a level-order tree traversal.

As an example, suppose we do a BFS on the same graph as before, starting at node $0$ .

BFS would be $0,1,2,4,5,3,6,8,7$ .

Notice how this gives the shortest route from node $0$ to all other nodes.
After the breadth-first search, we can find the shortest path from any vertex to the starting vertex by following the parent pointers These pointers form a tree rooted at the starting vertex. Note that they point in the direction opposite the search direction that we first followed. The depth of each node tells us the length of those paths.
The running time of breadth-first search is $O(|V| + |E|)$ on adjacency lists and $O(|V|^2)$ on adjacency matrix, just like depth-first search.

Graph Traversal

Graph Traversal

Depth-First Search

Breadth-First Search

results matching ""

No results matching ""