Depth-First Search Traversal of the Map

General
1

Depth-First Search Traversal of the Map

Depth-first search, or DFS for short, is a type of traversal that involves exploring a graph or map in a deep and systematic manner. Imagine navigating through a maze, where each intersection point has a lamp that lights up the path forward. The goal is to turn off all the lights, and DFS accomplishes this by following a specific approach:

  1. Your current location is at an intersection point where the light is still on.
  2. Optionally, you can proceed along the forward path (deep) until the light goes out, and then turn back to an adjacent intersection point.
  3. Repeat step 2 until all the lights are off.
  4. Backtrack to an intersection point where the light is still on, and repeat the process.

Abstracted DFS Algorithm

The DFS algorithm can be described in C pseudo-code as follows:

// Boolean array Visited[] initialized to false
void DFS(Vertex v) {
    Visited[v] = true;
    for each w adjacent to v
        if (!Visited[w])
            DFS(w);
}

As can be seen from the pseudo-code, DFS is a recursive algorithm. However, it can be converted to an iterative algorithm using a stack, as shown below:

// Boolean array Visited[] initialized to false
void DFS(Vertex v) {
    Visited[v] = true;
    Stack sta = MakeStack(MAX_SIZE);
    Push(sta, v);
    while (!Empty(sta)) {
        Vertex w = Pop(sta);
        for each u adjacent to w
            if (!Visited[u]) {
                Push(sta, u);
                Visited[u] = true;
            }
    }
}

Lemma:

If G is a connected graph, then all vertices of G can be labeled during a depth-first search, and during the execution of the algorithm, at least one side of each edge will be visited once.

Proof:

Suppose that the conclusion does not hold. Let U denote the set of vertices that are not labeled. Since G is connected, there must be at least one vertex in U that is connected to a labeled vertex. However, this situation cannot occur because once a vertex has been visited, all vertices attached to it will be accessed (and thus also marked). Therefore, all vertices will be visited and marked, and a vertex is visited once, and at least one side of each edge will be connected to it, so that each edge will be visited.

However, if a graph G is not connected, then all vertices need minor modifications to DFS. If the first attempt at all vertices have been marked, the graph is connected. Otherwise, from any of an unlabeled vertex, start, and execute DFS again.

Determine Graph Connectivity

We can use DFS to determine whether a graph is connected. The C pseudo-code describing the above algorithm is as follows:

/* Returns the number of connected components */
int ConnectedComponents(Graph G) {
    int componentNum = 0;
    for (each v in G)
        if (!visited[v]) {
            DFS(v);
            componentNum += 1;
        }
    return componentNum;
}

Complexity of the Algorithm

If N vertices and E edges are present in the graph, the time complexity is O(N + E) with the adjacency table storage graph. With the adjacency matrix memory map, there are O(N^2) operations.

Depth-First Search of Related Exercises

  • POJ-1979 Red and Black
  • POJ-2386 Lake Counting
  • Set List communication06- Figure 2 Saving James Bond - Easy Version
  • POJ-2488 A Knight’s Journey

Further Reading

  • Depth-First Spanning Tree and its application
  • Data structure and algorithm described in language analysis - C
  • Introduction to Algorithms