Program Overview

This C program detects whether a cycle exists in a directed graph using Depth First Search (DFS). It utilizes a recursive approach, maintaining a visited array and a recursion stack to track the nodes in the current path.

Program Structure

1. Graph Representation: The graph is represented using an adjacency list. Each vertex has a list of adjacent vertices.
2. DFS Function: A recursive function checks for cycles by exploring each vertex’s neighbors.
3. Main Function: It initializes the graph and invokes the DFS cycle detection.

Code

#include 
#include 

#define MAX_VERTICES 100

// Structure to represent a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent a graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// Function to create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(struct Node*));

    for (int i = 0; i < vertices; i++) { graph->adjLists[i] = NULL;
    }
    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// Function to perform DFS and detect cycles
int dfs(struct Graph* graph, int vertex, int* visited, int* recStack) {
    visited[vertex] = 1; // Mark the current node as visited
    recStack[vertex] = 1; // Mark the node in the recursion stack

    struct Node* temp = graph->adjLists[vertex];
    while (temp != NULL) {
        int adjVertex = temp->vertex;

        // If the adjacent vertex is not visited, recursively visit it
        if (!visited[adjVertex]) {
            if (dfs(graph, adjVertex, visited, recStack)) {
                return 1; // Cycle detected
            }
        }
        // If the adjacent vertex is in the recursion stack, a cycle is found
        else if (recStack[adjVertex]) {
            return 1; // Cycle detected
        }
        temp = temp->next;
    }
    recStack[vertex] = 0; // Remove the vertex from the recursion stack
    return 0; // No cycle found
}

// Function to detect cycles in the graph
int hasCycle(struct Graph* graph) {
    int visited[MAX_VERTICES] = {0};
    int recStack[MAX_VERTICES] = {0};

    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            if (dfs(graph, i, visited, recStack)) {
                return 1; // Cycle detected
            }
        }
    }
    return 0; // No cycle found
}

// Main function to demonstrate cycle detection
int main() {
    struct Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0); // Adding a cycle
    addEdge(graph, 2, 3);

    if (hasCycle(graph)) {
        printf("Graph contains a cycle.\n");
    } else {
        printf("Graph does not contain a cycle.\n");
    }

    return 0;
}
    

How It Works

The program starts by creating a graph and adding edges. The hasCycle function initializes the visited and recursion stack arrays, then calls the dfs function for each vertex. If a cycle is detected, the function returns true.

Compilation and Execution

To compile and run this program, use the following commands in your terminal:

gcc cycle_detection.c -o cycle_detection
./cycle_detection
    

Conclusion

This program efficiently detects cycles in a directed graph using depth-first search. Modifications can be made to handle undirected graphs or to accommodate different data structures based on specific needs.