Understanding Cycle Detection
- In Undirected Graphs: A cycle exists if we can return to a previously visited vertex without using the same edge.
- In Directed Graphs: A cycle exists if we can return to a previously visited vertex by following the directed edges.
For this example, we will focus on detecting cycles in an undirected graph using Depth First Search (DFS).
DFS Approach for Cycle Detection
- Start from any unvisited node and perform DFS.
- Keep track of visited nodes.
- If you encounter a node that has already been visited and is not the parent of the current node, then a cycle exists.
C Program to Detect Cycle in an Undirected Graph
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Structure for the adjacency list node
struct Node {
int vertex;
struct Node* next;
};
// Structure for the graph
struct Graph {
int numVertices;
struct Node* adjList[MAX];
};
// Function to create a new adjacency list node
struct Node* createNode(int vertex) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
// Function to create a graph with a given number of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
graph->adjList[i] = NULL; // Initialize adjacency list
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjList[src];
graph->adjList[src] = newNode;
// Add edge from dest to src (undirected graph)
newNode = createNode(src);
newNode->next = graph->adjList[dest];
graph->adjList[dest] = newNode;
}
// DFS function to detect a cycle
int isCyclicUtil(struct Graph* graph, int vertex, int visited[], int parent) {
visited[vertex] = 1; // Mark the current node as visited
struct Node* temp = graph->adjList[vertex];
while (temp) {
int adjVertex = temp->vertex;
// If the adjacent vertex is not visited, recurse on it
if (!visited[adjVertex]) {
if (isCyclicUtil(graph, adjVertex, visited, vertex)) {
return 1; // Cycle detected
}
}
// If the adjacent vertex is visited and is not the parent, a cycle exists
else if (adjVertex != parent) {
return 1; // Cycle detected
}
temp = temp->next; // Move to the next adjacent vertex
}
return 0; // No cycle found
}
// Function to detect cycle in the graph
int isCyclic(struct Graph* graph) {
int visited[MAX] = {0}; // Array to track visited nodes
// Call the utility function for each component
for (int i = 0; i < graph->numVertices; i++) {
if (!visited[i]) {
if (isCyclicUtil(graph, i, visited, -1)) {
return 1; // Cycle found
}
}
}
return 0; // No cycle found
}
// Main function
int main() {
struct Graph* graph = createGraph(5); // Create a graph with 5 vertices
// Adding edges
addEdge(graph, 0, 1);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0); // This creates a cycle
addEdge(graph, 1, 3);
addEdge(graph, 3, 4);
// Check for cycles
if (isCyclic(graph)) {
printf("Cycle detected in the graph.\n");
} else {
printf("No cycle detected in the graph.\n");
}
return 0;
}
Explanation of the Code
- Graph Representation:
- 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
Nodestructure.
- 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
- Graph Functions:
- createNode: Creates a new node for the adjacency list.
- createGraph: Initializes a graph with the specified number of vertices.
- addEdge: Adds an edge between two vertices, ensuring the graph remains undirected by adding edges in both directions.
- Cycle Detection Using DFS:
- The
isCyclicUtilfunction performs a DFS on the graph. - 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.
- The
- Main Function:
- In the
mainfunction, we create a graph and add edges. We also check for cycles and print the result.
- In the
Input and Output
Input (Edges of the graph):
- The edges added to the graph are:
The edges added to the graph are:
0 → 1
1 → 2
2 → 0 (creates a cycle)
1 → 3
3 → 4
Output
When you run the program, you will see the following output:
sqlCopy codeCycle detected in the graph.
Conclusion
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.
