Algorithm Cheat Sheet: Graph Traversal

When traversing a graph, one typical question we are interested in is whether the graph contains cycles. For directed graphs, a cycle often indicates the conflict between dependencies. There are two approaches to traverse a graph and identify cycles, the breadth-first and depth-first searches.

Breadth-first search (BFS)

Breadth-first search (BFS) relies on the degrees of a vertex to arrange the traversal. It usually starts from a source vertex (zero in-degree) or sink vertex (zero out-degree). Once we traverse from one vertex to another, we remove the edge between them and the corresponding degree. We then repeat the above process with another source or sink vertex. Cycles exist if we couldn’t find any source or sink vertex while we haven’t traversed all vertices–there is no source or sink vertices in a cycle.

A typical implementation of the BFS graph traversal maintains two hash tables for each vertex:

  1. Neighbor vertices of that vertex.
  2. In-degree (or out-degree) of that vertex.
unordered_map<int,int> indegree;
unordered_map<int,vector<int>> neighbors;

for (auto pair : pairs)
{
    if (indegree.find(pair.first) == indegree.end())
    {
        // Need to initialize every vertex, so we won't
        // overlook the one with zero in-degrees later.
        indegree[pair.first] = 0;
    }
    indegree[pair.second]++;
    neighbors[pair.first].push_back(pair.second)
}

while (!empty(indegree))
{
    // Start from a source vertex.
    unordered_map<int,int>::iterator it;
    for (it = indegree.begin(); it != indegree.end(); ++it)
    {
        if (it->second == 0)
            break;
    }
    if (it == indegree.end())
    {
        // Cycles exist--we couldn't find any source vertex
        // while we haven't traversed all vertices.
        return false;
    }
    int curr = it->first;
    indegree.erase(it);
    for (auto v : neighbors[curr])
    {
        indegree[v]--;
    }
}
return true;

Depth-first search (DFS)

Depth-first search (DFS) can start from any vertex. It then traverses one neighbor of that vertex and keeps doing that recursively. Once a source or sink vertex is reached, it traces back. Therefore, DFS itself would meet the goal of graph traversal. That said, two additional aspects need to be considered:

  1. Cycling detection–from any vertex, if the traversal ends up with that same vertex, we know cycles exist.
  2. Redundant traversal avoidance–a traversal may visit a vertex that was visited during other traversal path.

A typical implementation of the DFS graph traversal maintains the following data structures for each vertex:

  1. Neighbor vertices of that vertex.
  2. Indicator of the vertex visit status maintained temporarily within a traversal path (will be revoked at traceback) for cycling detection.
  3. Indicator of the vertex visit status maintained permanently to avoid redundant traversal.
  4. Status of the vertex according to the specific problem.
unordered_map<int,vector<int>> neighbors;
vector<bool> visitedTemp;
vector<bool> visitedPerm;
vector<bool> status;

for (auto pair : pairs)
{
    neighbors[pair.first].push_back(pair.second)
}
...
bool func(vertex)
{
    if (visitedPerm[vertex])
        return ...status[vertex];
    if (visitedTemp[vertex])
        return false;
    visitedTemp[vertex] = true;
    for (auto v : neighbors[vertex])
    {
        if (!func(v))
        {
            status[vertex] = ...;
            break;
        }
    }
    visitedTemp[vertex] = false;
    visitedPerm[vertex] = true;
    return ...status[vertex];
}

Examples

Contents