# Implementation of DFS algorithm as described by Algorithms - Dasgupta, Papadimitrious, Umesh Vazirani

I just want feedback regarding C++ coding style and if in any way I can optimize my code (e.g. to use a different data structure). I'm only trying to use up to C++ 14 standard code. Any other improvements are greatly appreciated as well.

file: graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <map>
#include <utility>
#include <vector>

struct Edge
{
char src, dest;
};

class Graph
{
public:

// marks which nodes have been visited. True = visited, false = not visited
std::map<char, bool> visited_;

// Graph Constructor
Graph(std::vector<Edge> const &edges);

void DFS(Graph& g);

void explore(Graph& g, char vertex);

void previst(char vertex);

void postvist(char vertex);
};

inline void printGraph(Graph const &graph)
{
std::cout << "Printing out the graph \n";
{
std::cout << "Source node: " << value.first << " \nconnected elements: " << std::endl;

for(const auto& element: value.second)
{
std::cout << element << " ";
}

std::cout <<"\n" << std::endl;
}

}

#endif //GRAPH_H


file: graph.cpp

#include "graph.h"

Graph::Graph(std::vector<Edge> const &edges)
{
// add edges to the directed graph
for (auto &edge: edges)
{
// insert at the end

// establish initial visited values for each node
visited_[edge.src] = false;
}
}

void Graph::DFS(Graph& g)
{
// We check for nodes that have not been visited
for (auto const& x : g.visited_)
{
if (x.second == false)
{
explore(g, x.first);
}
}
}

void Graph::explore(Graph& g, char vertex)
{
g.visited_[vertex] = true;
previst(vertex);

{
if(g.visited_[sourceNode] == false)
{
explore(g, sourceNode);
}
}
postvist(vertex);
}

void Graph::previst(char vertex)
{
std::cout << "Pre visiting vertex: " << vertex << std::endl;
}

void Graph::postvist(char vertex)
{
std::cout << "Post visting vertex: " << vertex << std::endl;
}


file: dfsDriver.cpp

#include "../graph.h"

int main()
{
// undirected edges
std::vector<Edge> edges =
{
{'g', 'd'}, {'g','h'} , {'d', 'h'},
{'d', 'g'}, {'h', 'g'}, {'h', 'd'},
{'d', 'a'}, {'a', 'd'}, {'a', 'b'},
{'b', 'a'}, {'a', 'c'}, {'c', 'a'},
{'c', 'f'}, {'f', 'c'},
{'b', 'f'}, {'f', 'b'}, {'b', 'e'},
{'e', 'b'}, {'e', 'i'}, {'i', 'e'},
{'e', 'j'}, {'j', 'e'},
{'i', 'j'}, {'j', 'i'}, {'k', 'l'},
{'l', 'k'}
};

Graph graph(edges);
//printGraph(graph);

graph.DFS(graph);
}


input graph:

# Optimizing the data structures

You can indeed optimize the way you store the graph a bit. You don't care about the exact order of the vertices, so it is better to use std::unordered_map instead of std::map, as lookups and insertions will then be $$\O(1)\$$ instead of $$\O(\log V)\$$.

For visited_, I see two alternatives. First, instead of adding all vertices to it, only add the vertices that have been visited. The bool is then unnecessary, and in fact you should then use std::unordered_set instead of a map. Alternatively, store all the data related to a node together in a struct, and just have a single container. For example:

struct NodeData {
std::vector<char> neighbors;
bool visited;
};



The approach you have taken is the right one in general. If you have more information about the graph, for example if it has only a few vertices or very many, or whether it is very sparse or very dense, you might be able to get more performance using more specialized data structures. In fact, since you have limited yourself to chars, you could store the graph like so:

constexpr std::size_t N = 1 << CHAR_BIT; // most likely 256 on your machine
std::bitset<N> vertices_;
std::bitset<N> visited_;


A std::bitset of 256 bits only uses 32 bytes. Each bit represents whether a vertex is part of the graph (vertices_), whether it was visited (visited_), or for a given vertex, which vertices are its neighbors (adjList_). Consider that an empty std::vector uses a similar amount of memory, and std::map and friends have to allocate memory for every element they store. The bitsets and the array use a fixed amount of memory, but everything is guaranteed to be stored compactly in memory, and lookups are very fast.

# You can nest structs and classes

It can make sense here to move struct Edge into class Graph. This avoids polluting the global namespace, and has some other benefits you'll see below.

class Graph{
public:
struct Edge
{
char src, dest;
};
…
Graph(std::vector<Edge> const &edges);
…
};
…
int main()
{
std::vector<Graph::Edge> edges = {…};
…
}


# No need to pass an object to its own member functions

Why does Graph::DFS() take a Graph& as a parameter? Since it is a member function of Graph, this is unnecessary. The same goes for Graph::explore(). You can just write:

void Graph::DFS()
{
for (auto const& x : visited_)
{
if (x.second == false)
{
explore(x.first);
}
}
}


# Make the code more generic

You have hardcoded the type of vertex to char. What if you have a graph with more than 256 different vertices? Maybe you want to identify vertices by integers, or maybe even strings. You can make your code more generic by using templates:

template<typename VertexID>
class Graph
{
public:
struct Edge
{
VertexID src, dest;
};
…
void explore(VertexID vertex);
void previst(VertexID vertex);
void postvist(VertexID vertex);
};


You can go further. Consider your constructor: it takes a reference to a std::vector, but does it really matter what type the container is? What if the caller has the edges in a std::array? Converting it to a std::vector would be wasteful. You could make your constructor a template that takes any kind of container:

template<typename Container>
Graph::Graph(Container const& edges)
{
for (auto &edge: edges)
{
…
}
}


If you accidentily call the constructor with something that is not a container of Edges, this will fail to compile, but probably with some cryptic error messages. With C++20 you can use concepts to restrict the type of container:

template<std::ranges::input_range<Edge> Container>
Graph::Graph(Container const& edges)
{
…
}


You also hardcoded previst() and postvist(). You could make DFS() take a function as an argument that it runs on vertices, either using std::function<void(VertexID&)>, or with a template parameter:

template<typename Function>
void Graph::DFS(Function& postvisit) {
for (auto const& x : g.visited_)
{
if (x.second == false)
{
explore(x.first, postvisit);
}
}
}

template<typename Function>
void Graph::explore(VertexID vertex, Function& postvisit)
{
g.visited_[vertex] = true;

{
if(!g.visited_[sourceNode])
{
explore(sourceNode, postvisit);
}
}

std::invoke(postvisit, vertex);
}


And then use it like so:

std::vector<Graph::Edge<char>> edges = {…};
Graph graph(edges);
graph.DFS([](char vertex) {
std::cout << "Post visiting vertex: " << vertex << '\n';
});


# Use '\n' instead of std::endl

Prefer to use '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually unnecessary, and has a negative impact on performance.

# What if you want to call DFS() more than once?

If you call DFS() a second time, nothing will happen since visited_ is true for all vertices. You should clear visited_ at the start of DFS(). Maybe it is even better not to have visited_ as a member variable, but instead make it a local variable in DFS(), and pass a reference to it to explore(). This way, each call to DFS() will have a fresh version, and less space is used for the Graph object itself.

If you really intend this to be used only once, then this shouldn't be a class to begin with. Instead, you could write a free function DFS() that takes a set of edges (and possibly a visitor function) as a parameter, and creates all the state necessary for the depth-first search as local variables.