Home /Modules/recursion/cpp_graph_dfs.cpp

cpp_graph_dfs.cpp

recursion/stanchion/cpp_graph_dfs.cpp · 24 line(s) · c

// Applied recursion: graph DFS with visited-state protection against cycles.
// Build: c++ -std=c++17 -Wall -Wextra -Wpedantic cpp_graph_dfs.cpp -o cpp_graph_dfs
#include <iostream>
#include <vector>

void dfs(std::size_t vertex, const std::vector<std::vector<std::size_t>>& graph,
         std::vector<bool>& visited) {
    if (vertex >= graph.size() || visited[vertex]) return;
    visited[vertex] = true;
    std::cout << vertex << ' ';
    for (const std::size_t next : graph[vertex])
        if (next < graph.size()) dfs(next, graph, visited);
}

int main() {
    const std::vector<std::vector<std::size_t>> graph{
        {1, 2}, {0, 3}, {0, 3}, {1, 2, 4}, {3}
    };
    std::vector<bool> visited(graph.size(), false);
    std::cout << "DFS from vertex 0: ";
    dfs(0U, graph, visited);
    std::cout << '\n';
}