C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Graph Cycle Detection using DFS (Depth-First Search)

Concept Overview

A cycle in a graph exists if you can start from a vertex and follow edges such that you return to the same vertex without reusing any edge.

We’ll detect cycles in two scenarios:

  1. Undirected Graph
  2. Directed Graph

Let’s start with Undirected Graph, since it’s simpler and foundational.

Cycle Detection in Undirected Graph

Key Idea

When performing DFS:

  • If we reach an already visited vertex that is not the parent of the current vertex →  Cycle detected.

Otherwise → No cycle.

 Example

0 — 1 — 2

|       |

+-------+

  • Start DFS from 0.
  • Visit 1 → Visit 2 → from 2 you find edge back to 0 (visited and not parent).
     Cycle detected

 

C Program: Cycle Detection in Undirected Graph (DFS)

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for adjacency list node


struct Node {


    int vertex;


    struct Node* next;


};


 


// Structure for the graph


struct Graph {


    int vertices;


    struct Node** adjLists;


    int* visited;


};


 


// Create new node


struct Node* createNode(int v) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->vertex = v;


    newNode->next = NULL;


    return newNode;


}


 


// Create graph


struct Graph* createGraph(int vertices) {


    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));


    graph->vertices = vertices;


    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));


    graph->visited = (int*)malloc(vertices * sizeof(int));


 


    for (int i = 0; i < vertices; i++) {


        graph->adjLists[i] = NULL;


        graph->visited[i] = 0;


    }


    return graph;


}


 


// Add edge (undirected)


void addEdge(struct Graph* graph, int src, int dest) {


    struct Node* newNode = createNode(dest);


    newNode->next = graph->adjLists[src];


    graph->adjLists[src] = newNode;


 


    newNode = createNode(src);


    newNode->next = graph->adjLists[dest];


    graph->adjLists[dest] = newNode;


}


 


// DFS to detect cycle


int isCyclicUtil(struct Graph* graph, int vertex, int parent) {


    graph->visited[vertex] = 1;


 


    struct Node* temp = graph->adjLists[vertex];


    while (temp) {


        int adjVertex = temp->vertex;


 


        if (!graph->visited[adjVertex]) {


            if (isCyclicUtil(graph, adjVertex, vertex))


                return 1;


        }


        else if (adjVertex != parent) {


            // Found a back edge


            return 1;


        }


 


        temp = temp->next;


    }


    return 0;


}


 


// Wrapper function


int isCyclic(struct Graph* graph) {


    for (int i = 0; i < graph->vertices; i++)


        if (!graph->visited[i])


            if (isCyclicUtil(graph, i, -1))


                return 1;


    return 0;


}


 


int main() {


    int vertices, edges;


    printf("Enter number of vertices: ");


    scanf("%d", &vertices);


 


    struct Graph* graph = createGraph(vertices);


 


    printf("Enter number of edges: ");


    scanf("%d", &edges);


 


    printf("Enter edges (u v):\n");


    for (int i = 0; i < edges; i++) {


        int u, v;


        scanf("%d %d", &u, &v);


        addEdge(graph, u, v);


    }


 


    if (isCyclic(graph))


        printf("Cycle detected in the graph.\n");


    else


        printf("No cycle found in the graph.\n");


 


    return 0;


}

Output

 
INPUT :
Enter number of vertices: 4
Enter number of edges: 4
Enter edges (u v):
0 1
1 2
2 3
3 0

OUTPUT :
Cycle detected in the graph.


INPUT (NO CYCLE) :
Enter number of vertices: 4
Enter number of edges: 3
Enter edges (u v):
0 1
1 2
2 3

OUTPUT :
No cycle found in the graph.

Complexity Analysis

Operation

Time Complexity

Space Complexity

Cycle Detection (DFS)

O(V + E)

O(V)
  • Each vertex and edge is visited once.
  • Recursion stack depth = O(V).

Key Takeaways

  • DFS helps detect back edges — a hallmark of cycles.
  • Works for undirected graphs using the parent check.
  • Can easily be extended to directed graphs.
  • Important for topological sorting, network loop detection, and dependency analysis.

 

Previous
Next