Graph adjacency list implementation in C++ I have been playing around with an adjacency list implementation of a graph class, on which I'd like to be able to run a build and test several graph algorithms. The code I have below works and I have been able to implement BFS, DFS, Dijkstra and Prim's algorithms, but I'm not very satisfied with it and would very much appreciate criticism. 

One of the key problems that I can see is that the neighbours of a node are private and therefore to traverse them inside a function (i.e. Dijkstra) I need to make this function a friend of the node class.  I suspect that I should implement smart pointers to solve this but before I do this I'd like to consider other suggestions (maybe custom iterators?).

I also think there is a problem with how the nodes are being initialised, as I would prefer not having to call setKey in the graph::addNode function.

The node class:

class node{
 public:
  node() {}
  node(int k) : key(k){}
  void addNeighbour(int k, int weight = 1){    
    if (this-&gt;key == k) return;
    neighbours.push_back(std::make_pair(k,weight));
  }
  inline int getKey() const {return key;}
  inline void setKey(const int k){key = k;}

  void display() const{    
    for (std::list&lt;std::pair&lt;int,int&gt; &gt;::const_iterator it = neighbours.begin(); it != neighbours.end(); ++it){
      std::pair&lt;int,int&gt; entry = *it;
      std::cout &lt;&lt; entry.first &lt;&lt; " ";
    }
    std::cout &lt;&lt; std::endl;
  }

  friend void bfs(graph &amp;g, int src);
  friend graph prim(graph &amp;g);
  friend void dijkstra(graph &amp;lg, int src);
 private:
  std::list&lt;std::pair&lt;int, int&gt; &gt; neighbours;  //first element in pair corresponds to vertex key, second to the edge weight between them
  int key;
};


The graph class:

class graph{
 public:
  graph(const int sz) : size(sz), 
                        nodes(sz, node()),
                        directed(false) {}
  void addNode(int key, const std::vector&lt;std::pair&lt;int,int&gt; &gt; &amp;input);
  void display() const;
  node &amp;operator[](const int i){return nodes[i];}
  inline int getSize() const {return size;}
 private:
  std::vector&lt;node&gt; nodes;
  int size;
  bool directed;
};

void graph::addNode(const int key, const std::vector&lt;std::pair&lt;int,int&gt; &gt; &amp;input){

  nodes[key].setKey(key);
  for (std::vector&lt;std::pair&lt;int,int&gt; &gt;::const_iterator it = input.begin(); it != input.end(); ++it){
    std::pair&lt;int,int&gt; entry = *it;
    nodes[key].addNeighbour(entry.first, entry.second);
    if (!directed){
      nodes[entry.first].addNeighbour(key, entry.second);
    }
  }
}
Overall, it seems good. One problem that I find here though is the lack of vertical spacing at some places. This is very subjective, I agree, but adding a blank line to separate unrelated things can improved readability. I once read somewhere that code should be split into "paragraphs". That's an interesting thought to keep in mind. Giving an example, this is one possible way I would space the method graph::addNode():

void graph::addNode(const int key, const std::vector&lt;std::pair&lt;int,int&gt; &gt; &amp;input) {

    nodes[key].setKey(key);

    for (std::vector&lt;std::pair&lt;int,int&gt; &gt;::const_iterator it = input.begin(); it != input.end(); ++it) {

        std::pair&lt;int,int&gt; entry = *it;
        nodes[key].addNeighbour(entry.first, entry.second);

        if (!directed) {
            nodes[entry.first].addNeighbour(key, entry.second);
        }
    }
}




Another minor point, but you don't need to add inline to a method when it is already defined directly inside the class body. In such case, adding the keyword is just unnecessary verbosity.



Huge lines like in those for loops:


for (std::list&lt;std::pair&lt;int,int&gt; &gt;::const_iterator it = neighbours.begin(); it != neighbours.end(); ++it)



Can be greatly simplified using auto or range-based for, if you have access to C++11. Failing that, I'd suggest that you typedef your list type to avoid having to replicate std::list&lt;std::pair&lt;int,int&gt; &gt; so many times (remember the DRY principle).

typedef std::list&lt;std::pair&lt;int, int&gt; &gt; ListType;




And as for the search algorithms, you didn't provide any implementation for them, but I don't see a reason why they shouldn't be members of graph. Personally, I don't see much purpose for a node to exist on its own without a graph, so I would make node a private inner class of graph and make all of its members public. Node seems like an implementation detail to me. Your interface apparently deals in terms of ints only.