Scribd
Upload
7 views3 pages

ADA Assignment - II

The document presents a C program that detects cycles in a graph using Depth-First Search (DFS). It defines structures for nodes and graphs, includes functions to create graphs, add edges, and check for cycles. The main function demonstrates the cycle detection with a sample graph.

Uploaded by

rakeshrocky14480
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views3 pages

ADA Assignment - II

The document presents a C program that detects cycles in a graph using Depth-First Search (DFS). It defines structures for nodes and graphs, includes functions to create graphs, add edges, and check for cycles. The main function demonstrates the cycle detection with a sample graph.

Uploaded by

rakeshrocky14480
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Detect if the Graph has a Cycle using DFS

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#define MAX_VERTICES 100

typedef struct Node {

int vertex;

struct Node* next;

} Node;

typedef struct Graph {

int numVertices;

Node* adjLists[MAX_VERTICES];

bool visited[MAX_VERTICES];

} Graph;

Node* createNode(int v) {

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

newNode->vertex = v;

newNode->next = NULL;

return newNode;

Graph* createGraph(int vertices) {

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

graph->numVertices = vertices;

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


graph->adjLists[i] = NULL;

graph->visited[i] = false;

return graph;

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

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;

bool hasCycleUtil(Graph* graph, int v, int parent) {

graph->visited[v] = true;

Node* temp = graph->adjLists[v];

while (temp != NULL) {

int neighbor = temp->vertex;

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

if (hasCycleUtil(graph, neighbor, v)) return true;

} else if (neighbor != parent) {

return true;

temp = temp->next;

}
return false;

bool hasCycle(Graph* graph) {

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

graph->visited[i] = false;

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

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

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

return true;

return false;

int main() {

Graph* graph = createGraph(4);

addEdge(graph, 0, 1);

addEdge(graph, 1, 2);

addEdge(graph, 2, 0);

if (hasCycle(graph))

printf("Cycle Detected\n");

else

printf("No Cycle\n");

return 0;

You might also like