I'm trying to code a function that checks if there is an edge between two nodes in directed graph. I found the code for this function in C++ on the internet and rewrote it into C, but i get error, can someone please help me!
the code in C++
link to the code : Find the path between given vertices in a directed graph – Techie Delight
Code:
The code that I wrote in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 40
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
struct AdjList
{
struct AdjListNode *head;
}*Head;
struct Graph
{
int V;
struct AdjList* array;
int * visited;
};
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
struct Graph* graph =
(struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// Create an array of adjacency lists. Size of
// array will be V
graph->array =
(struct AdjList*) malloc(V * sizeof(struct AdjList));
// Initialize each adjacency list as empty by
// making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
int countVertices(struct Graph * graph){
return graph->V;
}
int countEdges(struct Graph* graph){
int v = countVertices(graph);
struct AdjListNode* node = NULL;
int sum = 0;
for(int i = 0; i < v; i++){
node = graph->array[i].head;
while(node != NULL){
node = node->next;
sum++;
}
}
return sum/2;
}
void addEdge(struct Graph* graph, int src, int dest)
{
// Add an edge from src to dest. A new node is
// added to the adjacency list of src. The node
// is added at the beginning
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
struct queue {
int items[SIZE];
int front;
int rear;
};
// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
// Check if the queue is empty
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// Removing elements from queue
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
bool isConnected(struct Graph* graph, int startVertex, int destVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
if(currentVertex == destVertex)
return 1;
struct AdjListNode* temp = graph->array[currentVertex].head;
while(temp){
int adjVertex = temp->dest;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
return 1;
}
int main()
{
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 0, 3);
addEdge(graph, 1, 2);
int src = 1, dest = 2;
if(isConnected(graph, src, dest)){
printf("path exists");
}
else
printf("No path");
return 0;
}