{"id":742,"date":"2024-10-14T14:15:01","date_gmt":"2024-10-14T08:45:01","guid":{"rendered":"https:\/\/codexplained.in\/?p=742"},"modified":"2025-11-24T15:48:02","modified_gmt":"2025-11-24T10:18:02","slug":"detection-of-cycle-in-graph","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=742","title":{"rendered":"Detection of Cycle in Graph"},"content":{"rendered":"\n

Understanding Cycle Detection<\/h3>\n\n\n\n
    \n
  1. In Undirected Graphs<\/strong>: A cycle exists if we can return to a previously visited vertex without using the same edge.<\/li>\n\n\n\n
  2. In Directed Graphs<\/strong>: A cycle exists if we can return to a previously visited vertex by following the directed edges.<\/li>\n<\/ol>\n\n\n\n

    For this example, we will focus on detecting cycles in an undirected graph<\/strong> using Depth First Search (DFS).<\/p>\n\n\n\n

    DFS Approach for Cycle Detection<\/h3>\n\n\n\n
      \n
    1. Start from any unvisited node and perform DFS.<\/li>\n\n\n\n
    2. Keep track of visited nodes.<\/li>\n\n\n\n
    3. If you encounter a node that has already been visited and is not the parent of the current node, then a cycle exists.<\/li>\n<\/ol>\n\n\n\n

      C Program to Detect Cycle in an Undirected Graph<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 100\n\n\/\/ Structure for the adjacency list node\nstruct Node {\n    int vertex;\n    struct Node* next;\n};\n\n\/\/ Structure for the graph\nstruct Graph {\n    int numVertices;\n    struct Node* adjList[MAX];\n};\n\n\/\/ Function to create a new adjacency list node\nstruct Node* createNode(int vertex) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->vertex = vertex;\n    newNode->next = NULL;\n    return newNode;\n}\n\n\/\/ Function to create a graph with a given number of vertices\nstruct Graph* createGraph(int vertices) {\n    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));\n    graph->numVertices = vertices;\n\n    for (int i = 0; i < vertices; i++) {\n        graph->adjList[i] = NULL; \/\/ Initialize adjacency list\n    }\n    return graph;\n}\n\n\/\/ Function to add an edge to the graph\nvoid addEdge(struct Graph* graph, int src, int dest) {\n    struct Node* newNode = createNode(dest);\n    newNode->next = graph->adjList[src];\n    graph->adjList[src] = newNode;\n\n    \/\/ Add edge from dest to src (undirected graph)\n    newNode = createNode(src);\n    newNode->next = graph->adjList[dest];\n    graph->adjList[dest] = newNode;\n}\n\n\/\/ DFS function to detect a cycle\nint isCyclicUtil(struct Graph* graph, int vertex, int visited[], int parent) {\n    visited[vertex] = 1; \/\/ Mark the current node as visited\n\n    struct Node* temp = graph->adjList[vertex];\n    while (temp) {\n        int adjVertex = temp->vertex;\n\n        \/\/ If the adjacent vertex is not visited, recurse on it\n        if (!visited[adjVertex]) {\n            if (isCyclicUtil(graph, adjVertex, visited, vertex)) {\n                return 1; \/\/ Cycle detected\n            }\n        }\n        \/\/ If the adjacent vertex is visited and is not the parent, a cycle exists\n        else if (adjVertex != parent) {\n            return 1; \/\/ Cycle detected\n        }\n        temp = temp->next; \/\/ Move to the next adjacent vertex\n    }\n    return 0; \/\/ No cycle found\n}\n\n\/\/ Function to detect cycle in the graph\nint isCyclic(struct Graph* graph) {\n    int visited[MAX] = {0}; \/\/ Array to track visited nodes\n\n    \/\/ Call the utility function for each component\n    for (int i = 0; i < graph->numVertices; i++) {\n        if (!visited[i]) {\n            if (isCyclicUtil(graph, i, visited, -1)) {\n                return 1; \/\/ Cycle found\n            }\n        }\n    }\n    return 0; \/\/ No cycle found\n}\n\n\/\/ Main function\nint main() {\n    struct Graph* graph = createGraph(5); \/\/ Create a graph with 5 vertices\n\n    \/\/ Adding edges\n    addEdge(graph, 0, 1);\n    addEdge(graph, 1, 2);\n    addEdge(graph, 2, 0); \/\/ This creates a cycle\n    addEdge(graph, 1, 3);\n    addEdge(graph, 3, 4);\n\n    \/\/ Check for cycles\n    if (isCyclic(graph)) {\n        printf("Cycle detected in the graph.\\n");\n    } else {\n        printf("No cycle detected in the graph.\\n");\n    }\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Graph Representation<\/strong>:\n
          \n
        • We represent the graph using an adjacency list where each vertex points to a list of its neighbors. Each node in the adjacency list is defined by the Node<\/code> structure.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • Graph Functions<\/strong>:\n
            \n
          • createNode<\/strong>: Creates a new node for the adjacency list.<\/li>\n\n\n\n
          • createGraph<\/strong>: Initializes a graph with the specified number of vertices.<\/li>\n\n\n\n
          • addEdge<\/strong>: Adds an edge between two vertices, ensuring the graph remains undirected by adding edges in both directions.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
          • Cycle Detection Using DFS<\/strong>:\n
              \n
            • The isCyclicUtil<\/code> function performs a DFS on the graph.<\/li>\n\n\n\n
            • It checks if the current node has been visited and whether it is the parent of the adjacent node. If it is visited and not the parent, a cycle is detected.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • Main Function<\/strong>:\n
                \n
              • In the main<\/code> function, we create a graph and add edges. We also check for cycles and print the result.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
                Input and Output<\/h3>\n\n\n\n
                Input (Edges of the graph):<\/h4>\n\n\n\n
                  \n
                • The edges added to the graph are:<\/li>\n<\/ul>\n\n\n\n
                  The edges added to the graph are:
                  0 \u2192 1
                  1 \u2192 2
                  2 \u2192 0 (creates a cycle)
                  1 \u2192 3
                  3 \u2192 4<\/pre>\n\n\n\n
                  Output<\/h4>\n\n\n\n
                  When you run the program, you will see the following output:<\/p>\n\n\n\n
                  sqlCopy codeCycle detected in the graph.\n<\/code><\/pre>\n\n\n\n
                  Conclusion<\/h3>\n\n\n\n
                  This program effectively detects cycles in an undirected graph using DFS. You can modify the edges to test different graphs. The approach is efficient and straightforward, making it suitable for intermediate-level understanding of graph algorithms.<\/p>\n