Disagreement
I have to disagree with @ALX23z blanket statement that using std::map is bad idea. There is a lot more to it than that (if the graph was sparse the map is great). But you don't give enough contect to evaluate the graph implementation. All I can say it is an acceptable "basic" implementation.
Overall
Things that are actually bad:
1: The two main structures are public.
class Graph {
void DFSUtil(int v);
public:
std::map<int, bool> visited; // public member variable
std::map<int, std::list<int>> adj; // public member variable.
// The user of this class can
// damage the state of the object.
//
// but more importantly it locks you
// to a specific implementation.
// You can never remove the map without
// fixing all the code that uses the map.
void addEdge(int v, int w);
void DFS();
};
The adj should absolutely be private. The only method that should be public is addEdge(). That way if your usage of map turns out to be bad (after you measure it) then you can easily swap it out for another implementation without affecting any of the code that uses your Graph class.
2: You have a member that tracks some external processes.
std::map<int, bool> visited;
This is not a property of the class this is a property of the traversal itself. Storing it in the class limits how the class can be used you should store this as part of the traversal processes (there is a pattern for this "Visitor Pattern").
Code Review
Be consistent on your formatting:
#include <iostream>
#include<map> // Why no space here
#include<list>
Public members variables!!
public:
std::map<int, bool> visited;
std::map<int, std::list<int>> adj;
Member variables should always be private. If they need to be public you need to be able to articulate in a very detailed way why you are exposing the state and allowing the potability of it being mutated in a non controlled manner and thus potentially allowing the object to become invalid.
Note: const (preferably static) state is ok to be public.
This is a good interface for creating a graph.
void addEdge(int v, int w);
You can use this and the internal state can be nearly anything you want. If you used a PIMPL pattern you could customize the internal state depending on the type of graph.
The problem with your code is that it only does one thing. Print out the key of the node. If you want it to do anything else you need to change the code.
void Graph::DFSUtil(int v)
{
visited[v] = true;
std::cout << v << " ";
std::list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i);
}
void Graph::DFS()
{
for (auto i : adj)
if (visited[i.first] == false)
DFSUtil(i.first);
}
This is where you should inject your functionality (the action you want done). This is a form of "Dependency Injection" you pass the work action (as a function) into DFS() your function then gets called once for each node.
void Graph::DFS(std::function<void(int)>&& action);
void Graph::DFSUtil(std::function<void(int)>&& action, int v);
Now the usage becomes:
graph.DFS([](int n){std::cout << v << " ";}); // Or you can pass any action
// you like.
But your main problem is implementing the visitor pattern:
class GraphVisitor
{
std::map<int, bool> visited;
virtual void doVisit(int n) = 0;
public:
virtual ~GraphVisitor() {}
void visit(int n) {
if (!visited[n]) {
visited[n] = true;
doVisit(n);
}
}
};
class Graph
{
void accept(int i, GraphVisitor& visitor)
{
visitor.visit(i);
for(auto e: edges(i)) { // some way to get edges from i.
accept(e.dst.id, visitor);
}
}
public:
void accept(GraphVisitor& visitor)
{
for(auto i: adj) {
accept(i, visitor);
}
}
};
DFS => DF Search => Depth First Search\$\endgroup\$