Navigating the Web of Nodes: DFS and BFS Graph Traversal in C++

Navigating the Web of Nodes: DFS and BFS Graph Traversal in C++

Graphs are versatile data structures that model a wide range of relationships. Traversal, the process of systematically visiting each node in a graph, is fundamental to understanding and analyzing its structure. In this blog post, we’ll explore two essential graph traversal algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS), implemented in the C++ programming language.

Graphs and Their Representations

Before delving into traversal algorithms, let’s briefly discuss graphs. A graph consists of nodes (vertices) and edges connecting these nodes. Graphs can be directed or undirected, and they may have weights assigned to edges.

// Example representation of a graph using an adjacency list
#include <iostream>
#include <vector>

class Graph {
public:
    int vertices;
    std::vector<std::vector<int>> adjacencyList;

    Graph(int v) : vertices(v), adjacencyList(v) {}

    void addEdge(int v, int w) {
        adjacencyList[v].push_back(w);
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    // Graph creation complete
    return 0;
}

In this example, we’ve represented a directed graph with four vertices using an adjacency list.

Depth-First Search (DFS)

Depth-First Search explores as far as possible along each branch before backtracking. It is often implemented using recursion or a stack.

// Depth-First Search implementation
#include <iostream>
#include <vector>
#include <stack>

void DFSUtil(int v, std::vector<bool>& visited, const Graph& graph) {
    visited[v] = true;
    std::cout << v << " ";

    for (const auto& neighbor : graph.adjacencyList[v]) {
        if (!visited[neighbor]) {
            DFSUtil(neighbor, visited, graph);
        }
    }
}

void DFS(const Graph& graph, int startVertex) {
    std::vector<bool> visited(graph.vertices, false);
    DFSUtil(startVertex, visited, graph);
}

int main() {
    // Assuming the graph from the previous example
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "Depth-First Traversal starting from vertex 2:\n";
    DFS(g, 2);

    return 0;
}

Breadth-First Search (BFS)

Breadth-First Search explores the neighbor nodes at the present depth before moving on to nodes at the next depth level. It is implemented using a queue.

// Breadth-First Search implementation
#include <iostream>
#include <vector>
#include <queue>

void BFS(const Graph& graph, int startVertex) {
    std::vector<bool> visited(graph.vertices, false);
    std::queue<int> q;

    visited[startVertex] = true;
    q.push(startVertex);

    while (!q.empty()) {
        int currentVertex = q.front();
        q.pop();

        std::cout << currentVertex << " ";

        for (const auto& neighbor : graph.adjacencyList[currentVertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // Assuming the graph from the previous example
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);

    std::cout << "Breadth-First Traversal starting from vertex 2:\n";
    BFS(g, 2);

    return 0;
}

Conclusion

Graph traversal algorithms are vital tools in a programmer’s toolkit for understanding the relationships within a graph. Depth-First Search and Breadth-First Search, though simple in concept, form the foundation for more advanced graph algorithms. In C++, these algorithms can be implemented efficiently using standard data structures. Whether you’re exploring social networks, analyzing network connections, or solving complex problems in various domains, a solid understanding of graph traversal is essential. Happy exploring!