Graph adjacency list implementation in C++
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.