Depth First Traversal of a Graph

I am learning how to implement a basic undirected graph and perform a depth first traversal.

Please critique my code for correctness, best practices, security, and any other comments that may be helpful.

Graph.h:

#include 

/************************************************************************
/******************        PUBLIC METHODS        ************************
/************************************************************************
/****  addVertex    -   new vertex with no relationships             ****
/****  addNeighbor  -   builds an edge between vertices              ****
/****  DFT          -   performs a depth first traversal,            ****
                            printing each vertex name when visisted  ****
/************************************************************************
/************************************************************************/

struct Vertex {
    std::string Name;
    std::vector neighbors;        //vector of pointers to Vertices
    bool visited;

    Vertex::Vertex() {visited = false;}
};

class Graph {
public:
    Graph();
    void addVertex(std::string name);
    void addNeighbor(std::string vertex, std::string neighbor);
    void DFT(std::string start);

private:
    int traversalCount;
    std::vector graph;
    int getHashVal(std::string name);
};

Graph.cpp

```
#include "Graph.h"
#include
#include

Graph::Graph() {
graph.resize(53);
traversalCount = 0;
}

//adds a vertex to the graph with no edges
void Graph::addVertex(std::string name) {
int HashVal = getHashVal(name);
if (graph[HashVal].Name.compare(name) != 0)
{
graph[HashVal].Name = name;
std::cout addVertex(neighbor);
this->addNeighbor(vertex, neighbor);
}
else
{
graph[VertexHashVal].neighbors.push_back(&graph[NeighborHashVal]);
graph[NeighborHashVal].neighbors.push_back(&graph[VertexHashVal]);
}
}

//my depth first traversal method - prints a vertex when visited

Couple of major issues.

• You are writing your own hash function.

In addition some big problems.

• You are implementing your own hash based dictionary (badly).

• You need to use the visitor pattern (rather than have a mark in each node).

The hash function:

int Graph::getHashVal(std::string name) {
    int HashVal = 0;
    for (int i = 0; i < name.size(); i++)
    {
        HashVal += name[i];
    }
    HashVal %= graph.size();
    return HashVal;
}

That is a relatively trivial hash function that is known to have a bad distribution. If your keys are the same length you are very likely to get clashes.

TAP
 PAT

For any combination of 3 letter words the distance between any hashes can not be greater than 78. Without doing any analysis I bet the distribution of 3 letter words is actually normal so a whole bunch of words have a hash within 12 places of 234.

Writing hash functions is hard to do well so don't. Pick a well known one and use that.
Building your own dictionary

You use your hash function to build a dictionary like object using a vector. A couple of problems with this. But the main one is that clashes are not correctly resolved. Each entry in hash should be a list (so you can handle clashes correctly). Also 53 is rather a small size (though it is prime which is nice).

But there is already a dictionary like object in the standard library. std::map or std::unordered_map. The first one builds a structure with the same access characteristics as a balanced binary tree. The second one has access characteristics like a hash table. You can choose either and it will work fine.

In your node object you store pointers to the other nodes.

std::vector neighbors

Personally I would store the iterator (but that's just a small personal preference).
Visitor Pattern

You are recording visitation to the nodes in the nodes themselves. This is a simple solution but requires you to reset the whole graph before each traversal. PS you don't reset the visited attribute so you can only call DFT() once then it becomes invalid.

There is a better technique called a visitor pattern. This basically delegates traversal of the graph to the nodes. But Uses the visitor object as a callback to do processing. Thus you can control order from within your code.

Note: I would not think it as normal to describe a traversal as "Depth First" on cycle graphs. The graph may not be fully connected and there is no start point indicating a top.
Visitor pattern:

struct Visitor
{
    virtual ~Visitor() {}
    virtual bool visit(Vertex& node) = 0;  // returns false if we have already
                                           // seen the node, true otherwise
};

struct Vertex {
    std::string Name;
    std::vector neighbors;        //vector of pointers to Vertices

    void accept(Visitor& visitor)
    {
        if (visitor.visit(*this))          // If this is the first time
        {                                  // The do all the linked nodes
            for(auto loop: neighbors)
            {    loop->accept(visitor);
            }
        }
    }
};

Now we can write an application specific visitor.

struct DFTVisitor: public Visitor
{
    std::set   alreadyVisited;
    int                 traversalCount;

    DFTVisitor(): traversalCount(0) {}

    virtual bool visit(Vertex& node)
    {
        // Check if we have been to this node.
        if (alreadyVisited.find(&node) != alreadyVisited.end())
        {    return false;
        }

        alreadyVisited.insert(&node);
        std::cout << traversalCount << ": " << node.Name << std::endl;
        traversalCount++;

        return true;
    }
};

Now the graph DFT becomes:

void Graph::DFT(std::string start) {
     Vertix*  s = getFirstVertex(start);

     if (s != NULL)
     {
          DFTVisitor  visitor;
          s->accept(visitor);
     }
}

StackExchange Code Review Q#49595, answer score: 10