bfs traversal of graph in c

1// BFS algorithm in C
2
3#include <stdio.h>
4#include <stdlib.h>
5#define SIZE 40
6
7struct queue {
8  int items[SIZE];
9  int front;
10  int rear;
11};
12
13struct queue* createQueue();
14void enqueue(struct queue* q, int);
15int dequeue(struct queue* q);
16void display(struct queue* q);
17int isEmpty(struct queue* q);
18void printQueue(struct queue* q);
19
20struct node {
21  int vertex;
22  struct node* next;
23};
24
25struct node* createNode(int);
26
27struct Graph {
28  int numVertices;
29  struct node** adjLists;
30  int* visited;
31};
32
33// BFS algorithm
34void bfs(struct Graph* graph, int startVertex) {
35  struct queue* q = createQueue();
36
37  graph->visited[startVertex] = 1;
38  enqueue(q, startVertex);
39
40  while (!isEmpty(q)) {
41    printQueue(q);
42    int currentVertex = dequeue(q);
43    printf("Visited %d\n", currentVertex);
44
45    struct node* temp = graph->adjLists[currentVertex];
46
47    while (temp) {
48      int adjVertex = temp->vertex;
49
50      if (graph->visited[adjVertex] == 0) {
51        graph->visited[adjVertex] = 1;
52        enqueue(q, adjVertex);
53      }
54      temp = temp->next;
55    }
56  }
57}
58
59// Creating a node
60struct node* createNode(int v) {
61  struct node* newNode = malloc(sizeof(struct node));
62  newNode->vertex = v;
63  newNode->next = NULL;
64  return newNode;
65}
66
67// Creating a graph
68struct Graph* createGraph(int vertices) {
69  struct Graph* graph = malloc(sizeof(struct Graph));
70  graph->numVertices = vertices;
71
72  graph->adjLists = malloc(vertices * sizeof(struct node*));
73  graph->visited = malloc(vertices * sizeof(int));
74
75  int i;
76  for (i = 0; i < vertices; i++) {
77    graph->adjLists[i] = NULL;
78    graph->visited[i] = 0;
79  }
80
81  return graph;
82}
83
84// Add edge
85void addEdge(struct Graph* graph, int src, int dest) {
86  // Add edge from src to dest
87  struct node* newNode = createNode(dest);
88  newNode->next = graph->adjLists[src];
89  graph->adjLists[src] = newNode;
90
91  // Add edge from dest to src
92  newNode = createNode(src);
93  newNode->next = graph->adjLists[dest];
94  graph->adjLists[dest] = newNode;
95}
96
97// Create a queue
98struct queue* createQueue() {
99  struct queue* q = malloc(sizeof(struct queue));
100  q->front = -1;
101  q->rear = -1;
102  return q;
103}
104
105// Check if the queue is empty
106int isEmpty(struct queue* q) {
107  if (q->rear == -1)
108    return 1;
109  else
110    return 0;
111}
112
113// Adding elements into queue
114void enqueue(struct queue* q, int value) {
115  if (q->rear == SIZE - 1)
116    printf("\nQueue is Full!!");
117  else {
118    if (q->front == -1)
119      q->front = 0;
120    q->rear++;
121    q->items[q->rear] = value;
122  }
123}
124
125// Removing elements from queue
126int dequeue(struct queue* q) {
127  int item;
128  if (isEmpty(q)) {
129    printf("Queue is empty");
130    item = -1;
131  } else {
132    item = q->items[q->front];
133    q->front++;
134    if (q->front > q->rear) {
135      printf("Resetting queue ");
136      q->front = q->rear = -1;
137    }
138  }
139  return item;
140}
141
142// Print the queue
143void printQueue(struct queue* q) {
144  int i = q->front;
145
146  if (isEmpty(q)) {
147    printf("Queue is empty");
148  } else {
149    printf("\nQueue contains \n");
150    for (i = q->front; i < q->rear + 1; i++) {
151      printf("%d ", q->items[i]);
152    }
153  }
154}
155
156int main() {
157  struct Graph* graph = createGraph(6);
158  addEdge(graph, 0, 1);
159  addEdge(graph, 0, 2);
160  addEdge(graph, 1, 2);
161  addEdge(graph, 1, 4);
162  addEdge(graph, 1, 3);
163  addEdge(graph, 2, 4);
164  addEdge(graph, 3, 4);
165
166  bfs(graph, 0);
167
168  return 0;
169}

1ins 20
2ins 10
3ins 30
4ins 60
5ins 8
6ins 11

1#include <bits/stdc++.h>
2using namespace std;
3#define ll  long long int
4#define ull unsigned long long int
5void addedge(vector<int>adj[],int u,int v)
6{
7    adj[u].push_back(v);
8    adj[v].push_back(u);
9}
10void print_list(vector <int> adj[],int n)
11{
12    for(int i=0;i<n;i++)
13    {
14        cout << "adjacency list for node" << i << "is :\n";
15        for(auto ele: adj[i])
16        {
17            cout << "->" << ele << " \n";
18        }
19
20    }
21}
22void BFS(int v,int e,vector<int>adj[])
23{
24    bool visited[e];
25    for(int i=0;i<e;i++)
26    {
27        visited[i]= false;
28    }
29    list<int>queue;
30    visited[v]= true;
31    queue.push_back(v);
32    while (!queue.empty())
33    {
34        v = queue.front();
35        cout << v << " ";
36        queue.pop_front();
37        for(auto ele:adj[v])
38        {
39            if(!visited[ele])
40            {
41                visited[ele]= true;
42                queue.push_back(ele);
43
44            }
45        }
46    }
47}
48
49
50int main()
51{
52    int n,e;
53    cin >> n >> e;
54    vector <int> adj[n];
55    int u,v;
56    for(int i=0;i<e;i++)
57    {
58
59        cin >> u >> v;
60        addedge(adj,u,v);
61
62    }
63    print_list(adj,n);
64    BFS(v,e,adj);
65
66
67    return 0;
68}