Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with raw pointers.Graphs.hnamespace DS {    struct Vertex;    typedef std::list<Vertex*> VerticesList;    typedef std::map<int, VerticesList::const_iterator> DataVertexMap;    class Graph {        VerticesList _verticesList;        DataVertexMap _dataVertexMap;        //TODO: Need some design to have this function internal only and not exposed to client        Vertex* addAndGetVertex(int data);    public:        Graph();        ~Graph();        bool isEmpty();        //We don't check for duplicate vertex        void addVertex(int data);        void addEdge(int srcData, int dstData, int cost);        int getCostForEdge(int srcData, int dstData);        void displayGraph();        void dfsTraversal();    };} //End namespace DSGraphs.cpp#include Graphs.h#include <stack>namespace DS {    struct Vertex;    typedef struct Edge {        int cost;        struct Vertex* srcVertex;        struct Vertex* dstVertex;    }Edge;    typedef std::list<Edge*> EdgeList;    class Vertex {    public:        Vertex() {            bVisited = false;        }        int data;        EdgeList edgeList;        bool bVisited;    };    Graph::Graph() {    }    Graph::~Graph() {        for (std::list<Vertex*>::const_iterator iter = _verticesList.begin(); iter != _verticesList.end(); ++iter) {            Vertex * vertex = *iter;            std::list<Edge*> edgeList = vertex->edgeList;            for (std::list<Edge*>::const_iterator edgeIter = edgeList.begin(); edgeIter != edgeList.end(); ++edgeIter) {                delete *edgeIter;            }            delete vertex;        }    }    bool Graph::isEmpty() {        return _verticesList.empty();    }    void Graph::addVertex(int data) {        Vertex* node = new Vertex();        node->data = data;        node->edgeList.clear();        VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);        _dataVertexMap.insert(std::make_pair(data, iter));    }    Vertex* Graph::addAndGetVertex(int data) {        Vertex* node = new Vertex();        node->data = data;        node->edgeList.clear();        VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);        //TODO: Evaluate if this is right approach to insert in map i.e iterator        _dataVertexMap.insert(std::make_pair(data, iter));        return node;    }    void Graph::addEdge(int srcData, int dstData, int cost) {        DataVertexMap::const_iterator srcIter = _dataVertexMap.find(srcData);        DataVertexMap::const_iterator dstIter = _dataVertexMap.find(dstData);        Vertex* srcVertex = NULL;        Vertex* dstVertex = NULL;        if(srcIter == _dataVertexMap.end())            srcVertex = addAndGetVertex(srcData);        else            srcVertex = *(srcIter->second);        if(dstIter == _dataVertexMap.end())            dstVertex = addAndGetVertex(dstData);        else            dstVertex = *(dstIter->second);        Edge* newEdge = new Edge();        newEdge->cost = cost;        newEdge->srcVertex = srcVertex;        newEdge->dstVertex = dstVertex;        srcVertex->edgeList.push_back(newEdge);    }    int Graph::getCostForEdge(int srcData, int dstData) {        DataVertexMap::const_iterator srcIter = _dataVertexMap.find(srcData);        DataVertexMap::const_iterator dstIter = _dataVertexMap.find(dstData);        if(srcIter == _dataVertexMap.end() || dstIter == _dataVertexMap.end())            return -1;        EdgeList edgeList = (*(srcIter->second))->edgeList;        for (EdgeList::const_iterator iter = edgeList.begin(); iter != edgeList.end(); ++iter) {            Edge* edge  = *iter;            if(edge->dstVertex == *(dstIter->second))                return edge->cost;        }        return -1;    }    void Graph::displayGraph() {    }    void Graph::dfsTraversal() {        std::stack<Vertex*> vertexStack;        vertexStack.push(_verticesList.front());        while(!vertexStack.empty())        {            Vertex *vertex = vertexStack.top();            vertexStack.pop();            vertex->bVisited = true;            printf(%d\n, vertex->data);            const EdgeList edgeList = vertex->edgeList;            for (EdgeList::const_iterator iter = edgeList.begin(); iter != edgeList.end(); ++iter) {                Edge *edge = *iter;                Vertex *dstVertex = edge->dstVertex;                if(!dstVertex->bVisited)                    vertexStack.push(dstVertex);            }        }       //TODO: mark visited back to false for each node.    }}
Constructing a graph and performing a depth-first traversal
c++;c++11;graph;pointers;depth first search
I won't go into detail about memory management now, but it seems to be correct. You are deleting the edges and vertexes in the destructors, so you should't have any leaks.Things you could improve in the code:No need to define an empty constructor. Don't provide one if you have no manual initialization to perform.You don't have to typedef struct in C++, like you would in C. Just struct Edge { }; is enough.Beginning with C++11, you can now directly initialize member variables on declaration. So you could init Vertex::bVisited directly. E.g.: bool bVisited = false;. I also recommend initializing Vertex::data to zero or some other default value.The for loops in Graph's destructor are quite verbose and long. You could make them a lot more concise by using range based for loops.Methods that don't mutate state of an object should be const. isEmpty() is an example: bool isEmpty() const; This is Const Correctness.Several declaration are using the long winded iterator and const_iterator names. You could simplify all of them by using auto and letting the compiler do the type inference for you.Don't use NULL in C++. This is very outdated. Start using nullptr.Names starting with an _ are arguable. _verticesList and _dataVertexMap are not wrong though, but this practice might still be disapproved by some, as it might lead to eventually slipping such a name into the global namespace. Consider other options such as an underscore at the end, likeThis_ or the also popular m_ prefix, m_likeThis. Or no prefix/suffix at all.printf is cool, I like it ;). But this is C++ land, so you should give std::cout the preference. If you do use printf though, #include <cstdio> and call it using the std:: namespace: std::printf(Hello);.There are probably more aspect and points to note. Hopefully other reviewers will expand on this list.