Directed Graph Traversal and Cycle Detection

algorithm cheat sheet

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. That is, 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.
// A graph is represented by a list of edges which is saved in "pairs".
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. Cycle detection–from any vertex, if the traversal ends up with that same vertex, we know cycles exist.
  2. Repeated traversal avoidance–a traversal may visit a vertex that was visited during other traversal paths.

A typical implementation of 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 cycle detection.
  3. Indicator of the vertex visit status maintained permanently to avoid a repeated graph traversal.
  4. Status of the vertex according to the specific problem.
// A graph is represented by a list of edges which is saved in "pairs".
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