[C++] Graph adjacency list shortest path BFS

Here is a simple graph model using adjacency lists. The edges are undirected and we will also track edge weights, but ignore them at this time for the shortest path calculation between two given points (therefore we can use a simple BFS).

The adjacency list representation, is a list of lists, where for each vertex it contains the list of vertices immediately connected to it.
If the graph is not directed, each edge goes both ways, so it appears twice in the list.

For example this graph:

A - B - C
|       |
D - - - E

Would be represented as:

A: B,D
B: A,C
C: B,E
D: A,E
E: D,C

As additional thing, in order to actually print out the shortest path found (if any), we need to track it while we walk around the graph, which means we must store additional information during our BFS walk than then simple queue of vertices.
Specifically, we track for each path we are following, the list of vertices seen so far. Since we are doing a BFS, we will definitely find the shortest path by the time we visited all vertices ONCE (any vertex we revisit is either part of a loop or of a longer path, so we can safely discard it), if the path exists at all.


You can find the data structure and algorithm implementation on my Gist.