Shortest path by breadth-first search

Given an undirected unweighted graph that has no loop, we can use a basic breadth-first search algorithm to determine the shortest path from a specified vertex to any (other) one in the graph.

In the previous post I showed a way to store a graph in a C++11 STL container (a vector of forward list of unsigned int). This is the Graph class you are going to see in the code below. Besides, Vertex is a typedef for unsigned int, meaning that we identify a vertex simply by an unsigned number, starting from zero.

This is the class I want to develop:

class BreadthFirstSearch
{
private:
    std::vector<Vertex> parents_; // 1
    Vertex start_; // 2
public:
    BreadthFirstSearch(const Graph& graph, Vertex start); // 3
    std::vector<Vertex> path(Vertex end); // 4
    std::vector<Vertex> backpath(Vertex end); // 5
    void printPath(Vertex end); // 6
};

1. As a result of the breadth-first search algorithm I want to put in this vector the closest ancestor to the start one of any vertex in the associated graph.
2. This is the vertex that I want to use as starting point for BFS algorithm.
3. The ctor gets in input a Graph and one of its vertex and fills the parents_ vector as expected.
4. This method returns the path from the start vertex, as specified by the ctor, to the passed end one.
5. Not strictly a necessity, it could be a private method. Provides the shortest path in reversed order, from end to start.
6. Utility method, dump to standard output a shortest path.

The BreadthFirstSearch constructor implements the BFS algorithm in this way:

BreadthFirstSearch::BreadthFirstSearch(const Graph& graph, Vertex start) :
        parents_(graph.vertices_.size(), std::numeric_limits<Vertex>::max()), start_(start) // 1
{
    if (start >= graph.vertices_.size()) // 2
        return;

    std::vector<bool> seen(graph.vertices_.size()); // 3
    std::queue<Vertex> queue; // 4

    queue.push(start); // 5
    seen[start] = true;
    while (!queue.empty()) // 6
    {
        Vertex vertex = queue.front();
        queue.pop();

        for (auto it = graph.vertices_[vertex].begin(); it != graph.vertices_[vertex].end(); ++it) // 7
        {
            Vertex next = *it;
            if (!seen[next]) // 8
            {
                queue.push(next);
                seen[next] = true;
                parents_[next] = vertex;
            }
        }
    }
}

1. Initially, the parents_ vector contains just "no parent" elements. I used the largest value available for a Vertex to represent such state.
2. Event though this code is not production ready, I couldn't help to put at least a minimal error handling in it. The vertex passed as starting point should be an actual Graph element.
3. This vector keep track of all the vertices that have been already checked in a previous step of the algorithm. Initially no one is, so we could rely on the default behavior for the vector ctor that sets to false all its elements.
4. On this queue I'll put all the vertices that are connected to the one is currently checked.
5. Let's put the control variables in the initial condition. The start vertex is enqueued, and it is marked as seen.
6. Loop until all the elements in the queue are processed.
7. Loop on all the vertices connected to the current one.
8. If this vertex has not already processed, push it in queue, mark it as seen, set as its next the current vertex.

The BreadthFirstSearch ctor has filled the parents_ vector, now we can use it to create the shortest path from the start vertex to a specific one:

std::vector<Vertex> BreadthFirstSearch::path(Vertex end)
{
    std::vector<Vertex> backtrace = backpath(end); // 1
    return std::vector<Vertex>(backtrace.rbegin(), backtrace.rend()); // 2
}

1. Actually, the real job is delegated to backpath().
2. Since backpath() returns a reversed path, the only real task of this method is reverting the vector to return a "stright" one.

If you want the path to be stored in a vector, you will find that it is in the nature of the problem to generate a reversed solution. Or maybe you could use a deque, filling it from the front. Anyway, this is my solution:

std::vector<Vertex> BreadthFirstSearch::backpath(Vertex end)
{
    std::vector<Vertex> backtrace; // 1
    if (end >= parents_.size()) // 2
        return backtrace;

    for (Vertex cur = end; cur != std::numeric_limits<Vertex>::max(); cur = parents_[cur])
        backtrace.push_back(cur); // 3
    return backtrace;
}

1. I am going to backtracing from the passed graph vertex up to the starting one, pushing each parent in this vector.
2. Better to ensure the caller won't pass a nonexistent vertex.
3. Each ancestor is pushed back in the vector, until the "no parent" element is found.

The utility method that dumps the path to standard shows how to use backpath():

void BreadthFirstSearch::printPath(Vertex end)
{
    std::vector<Vertex> vxs = backpath(end);
    std::copy(vxs.rbegin(), vxs.rend(), std::ostream_iterator<Vertex>(std::cout, " "));
    std::cout << std::endl;
}

Here is a piece of code that uses my BreadthFirstSearch class:

BreadthFirstSearch bfs(graph, 0); // 1
bfs.printPath(3); // 2

1. I pass to bfs the graph object as created in the previous post example, and I specify zero as the starting vertex.
2. Ask to print the shortest path from zero to three.

The expected result is:

0 4 3 

Go to the full post

Graph by adjacency list

If you need to work with graphs in your C++11 code, you'd usually rely on someone else's job, like the Boost Graph Library, friendly known as BGL. Sometimes it happens you simply can't, and you have to work it out by yourself. Here I am writing a trivial Graph class that would let me to store an undirected unweighted graph in a compact form.

I have a simple graph as the one showed in the picture. Each vertex is represented by an unsigned integer starting from zero, that helps me to keep the code even simpler. Edges have no weight nor direction, so we can move from vertex 0 to vertex 5 and vice versa, and we are not interested in the cost of moving from one vertex to another one. We only want to know if we can actually go from here to there.

The two common ways to represent a graph differ by using a matrix or a list to store the adjacency of each vertex. As often happens, you should know the actual problem you are tackling to decide which data structure would suit you better. Still, list is usually the primary suspect.

In this first implementation, my class Graph provides only a constructor to set it up and a print method to show what it has in its belly. The main focus here is about showing how the data is stored in it.

using Vertex = unsigned int; // 1
using Edge = std::pair<Vertex, Vertex>; // 2
using Edges = std::vector<Edge>; // 3
using Vertices = std::forward_list<Vertex>; // 4

class Graph
{
public:
    std::vector<Vertices> vertices_; // 5

    Graph(int nv, Edges edges) : vertices_(nv) // 6
    {
        std::for_each(edges.begin(), edges.end(), [this](const Edge& edge) // 7
        {
            if(edge.first < vertices_.size() && edge.second < vertices_.size()) // 8
            {
                vertices_[edge.first].push_front(edge.second); // 9
                vertices_[edge.second].push_front(edge.first);
            }
        });
    }

    void print() // 10
    {
        for(Vertex i = 0; i < vertices_.size(); ++i)
        {
            std::cout << i << ": ";
            std::copy(vertices_[i].begin(), vertices_[i].end(), std::ostream_iterator<Vertex>(std::cout, " "));
            std::cout << std::endl;
        }
    }
};

1. Each vertex is represented by an unsigned integer, starting from zero.
2. An edge is defined by the two vertices delimiting it.
3. I want to pass all the edges in my graph to the class constructor. This is the collection I am going to use for this task.
4. Any vertex in the graph has an associated collection of vertices, all the ones to which it is connected. The cheap C++11 forward_list suffices for this job.
5. A graph is a collection of Vertices. Each element in the vector is an actual vertex of the graph and the associated Vertices keeps track of all the connected vertices.
6. The Graph constructor requires as input the number of vertices in the graph, and all the edges on it. The data member vertices_ is initialized as a collection of empty Vertices.
7. Loop on all the passed edges to associate each vertex in the graph to its connections.
8. A real piece of code should have more effective error handling than this. Here I just discard any wrong edge. It would make sense let the user know that something went wrong.
9. Being the graph undirected, any edge creates two relations.
10. Utility method, just to show that anything worked as expected (hopefully).

Here is how my Graph class is used:

Edges edges { { 0, 1 }, { 0, 4 }, { 0, 5 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } };
Graph graph(6, edges);
graph.print();

The expected output:

0: 5 4 1 
1: 4 2 0 
2: 3 1 
3: 4 2 
4: 3 1 0 
5: 0 

Go to the full post