# Graph cycle detection in C

A cycle in a graph is simply a path whereby one can get from a vertex back to itself. For example, in the graph below there is a cycle (0, 1, 2, 3, 0). A graph containing at least one cycle is called a cyclic graph, and a graph without cycles is called an acyclic graph.

Detecting whether a graph is cyclic or acyclic can be easily performed using a Depth First Search (DFS). We simply start at an arbitrary vertex, visit each of its neighbours, then each of the neighbour’s neighbours, and so on. If at any point we find a neighbour that we have visited already, and we haven’t just come from there, then we have detected a cycle.

Here is an implementation in C. Notice that, because it is a DFS, it is very similar to the connected components algorithm I described earlier, which also does a DFS.

#include <stdlib.h>

typedef struct {
unsigned int first;
unsigned int second;
} edge;

static unsigned int cyclic_recursive(const edge *edges, unsigned int n, unsigned int *visited,
unsigned int order, unsigned int vertex, unsigned int predecessor)
{
unsigned int i;
unsigned int cycle_found = 0;
visited[vertex] = 1;
for (i = 0; i < n && !cycle_found; i++) {
if (edges[i].first == vertex || edges[i].second == vertex) {
const unsigned int neighbour = edges[i].first == vertex ?
edges[i].second : edges[i].first;
if (visited[neighbour] == 0) {
/* Not yet visited */
cycle_found = cyclic_recursive(edges, n, visited, order, neighbour, vertex);
}
else if (neighbour != predecessor) {
/* Found a cycle */
cycle_found = 1;
}
}
}
return cycle_found;
}

unsigned int cyclic(const edge *edges, unsigned int n, unsigned int order)
{
unsigned int *visited = calloc(order, sizeof(unsigned int));
unsigned int cycle_found;
if (visited == NULL) {
return 0;
}
cycle_found  = cyclic_recursive(edges, n, visited, order, 0, 0);
free(visited);
return cycle_found;
}


An example program to find out if the graph shown at the top is cyclic or acyclic:

#include <stdio.h>

int main(void)
{
const unsigned int order = 6; /* Vertices */
const unsigned int n = 6; /* Edges */
edge *edges;
unsigned int c;

edges = malloc(n * sizeof(edge));
if (edges == NULL) {
return 1;
}

edges.first = 0;
edges.second = 1;
edges.first = 1;
edges.second = 2;
edges.first = 2;
edges.second = 3;
edges.first = 3;
edges.second = 0;
edges.first = 3;
edges.second = 4;
edges.first = 3;
edges.second = 5;

c = cyclic(edges, n, order);
printf("Graph is %s.\n", c ? "cyclic" : "acyclic");
free(edges);

return 0;
}


The output:

Graph is cyclic.