Answer to Question #239891 in C for micky

Question

Write a program to Detect Cycle in a Directed Graph. Suppose, you have a directed graph, check

whether the graph contains a cycle or not. Your function should return true if the given graph

contains at least one cycle, else return false

Answer 1

#include <stdio.h>
#include <stdlib.h>


struct AdjListNode
{
	int d;
	struct AdjListNode* nt;
};


struct AdjList
{
	struct AdjListNode *h;
};


struct Graph
{
	int V;
	struct AdjList* arr;
};


struct AdjListNode* newAdjListNode(int d)
{
	struct AdjListNode* newNode =
	(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
	newNode->d = d;
	newNode->nt = NULL;
	return newNode;
}


struct Graph* createGraph(int V)
{
	struct Graph* graph =
		(struct Graph*) malloc(sizeof(struct Graph));
	graph->V = V;


	graph->arr =
	(struct AdjList*) malloc(V * sizeof(struct AdjList));
	int i;
	for (i = 0; i < V; ++i)
		graph->arr[i].h = NULL;


	return graph;
}


void addEdge(struct Graph* graph, int src, int dest)
{
	struct AdjListNode* newNode = newAdjListNode(dest);
	newNode->nt = graph->arr[src].h;
	graph->arr[src].h = newNode;


	newNode = newAdjListNode(src);
	newNode->nt = graph->arr[dest].h;
	graph->arr[dest].h = newNode;
}


void printGraph(struct Graph* graph)
{
	int v;
	for (v = 0; v < graph->V; ++v)
	{
		struct AdjListNode* pCrawl = graph->arr[v].h;
		printf("\n Adjacency list of vertex %d\n head ", v);
		while (pCrawl)
		{
			printf("-> %d", pCrawl->d);
			pCrawl = pCrawl->nt;
		}
		printf("\n");
	}
}


int main()
{
	int V = 5;
	struct Graph* graph = createGraph(V);
	addEdge(graph, 2, 2);
	addEdge(graph, 2, 5);
	addEdge(graph, 3, 3);
	addEdge(graph, 3, 4);
	addEdge(graph, 3, 5);
	addEdge(graph, 4, 4);
	addEdge(graph, 5, 5);


	printGraph(graph);


	return 0;
}