Graph Traversal Algorithms

Graph Traversal Algorithms

Graph traversal algorithms are methods used to visit all the nodes (or vertices) in a graph. These algorithms are essential for many applications, such as searching, pathfinding, and analysing graph structures. The two most common traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS). This lesson will cover both algorithms in detail.

Depth-First Search (DFS)

Depth-First Search (DFS) is a traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure to keep track of the vertices to visit next. DFS can be implemented using recursion or an explicit stack.

DFS Algorithm Steps

1. Start at the root node (or any arbitrary node in the graph).
2. Mark the node as visited.
3. For each adjacent node, if it has not been visited, recursively apply DFS.
4. Backtrack when there are no unvisited adjacent nodes.

Example of DFS

Consider the following undirected graph:

  A -- B
  |    |
  C -- D

We will perform a DFS starting from node A.

1. Start at A, mark A as visited.
2. Visit B, mark B as visited.
3. From B, visit D, mark D as visited.
4. From D, visit C, mark C as visited.
5. Backtrack to D, then to B, and finally to A.

The order of visitation is A, B, D, C.

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a traversal algorithm that explores all the neighbour nodes at the present depth before moving on to nodes at the next depth level. BFS uses a queue data structure to keep track of the vertices to visit next.

BFS Algorithm Steps

1. Start at the root node (or any arbitrary node in the graph).
2. Mark the node as visited and enqueue it.
3. While the queue is not empty, dequeue a node.
4. For each adjacent node, if it has not been visited, mark it as visited and enqueue it.

Example of BFS

Using the same graph:

  A -- B
  |    |
  C -- D

We will perform a BFS starting from node A.

1. Start at A, mark A as visited and enqueue A.
2. Dequeue A, visit B and C, mark them as visited and enqueue them.
3. Dequeue B, visit D, mark it as visited and enqueue it.
4. Dequeue C (no unvisited neighbours).
5. Dequeue D (no unvisited neighbours).

The order of visitation is A, B, C, D.

Comparison of DFS and BFS

DFS and BFS have different characteristics and are suitable for different scenarios:

• Space Complexity: DFS requires less memory than BFS since it stores only the nodes along the current path. BFS, however, stores all the nodes at the current level, which can consume more memory.
• Time Complexity: Both DFS and BFS have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
• Finding Shortest Path: BFS is guaranteed to find the shortest path in an unweighted graph, while DFS may not.

Applications of Graph Traversal Algorithms

Graph traversal algorithms are used in various applications, including:

• Pathfinding: Finding the shortest path in navigation systems, such as Google Maps.
• Web Crawling: Search engines use BFS to index web pages.
• Network Broadcasting: BFS can be used to spread information in a network.
• Game Development: Pathfinding algorithms in games often use BFS or DFS.

Implementing DFS and BFS in C++

DFS Implementation

Here is a simple C++ implementation of DFS using recursion:

#include 
#include 
using namespace std;

void DFS(int vertex, vector &visited, const vector> &graph) {
    visited[vertex] = true;
    cout << vertex << " ";

    for (int i : graph[vertex]) {
        if (!visited[i]) {
            DFS(i, visited, graph);
        }
    }
}

int main() {
    vector> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};
    vector visited(graph.size(), false);
    DFS(0, visited, graph);
    return 0;
}

BFS Implementation

Here is a simple C++ implementation of BFS using a queue:

#include 
#include 
#include 
using namespace std;

void BFS(int start, const vector> &graph) {
    vector visited(graph.size(), false);
    queue q;
    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        cout << vertex << " ";

        for (int i : graph[vertex]) {
            if (!visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    vector> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2}};
    BFS(0, graph);
    return 0;
}

Summary

• DFS explores as far as possible along each branch before backtracking.
• BFS explores all neighbour nodes at the present depth before moving on.
• DFS uses a stack, while BFS uses a queue.
• Both algorithms have a time complexity of O(V + E).
• BFS is better for finding the shortest path in unweighted graphs.

Check your understanding

• What is the main difference between DFS and BFS in terms of data structure used?
• How does the space complexity of DFS compare to that of BFS?
• In which scenarios would you prefer to use BFS over DFS?
• Write a brief explanation of how you would implement a DFS algorithm using a stack instead of recursion.