Question

Create a queue for a breadth first traversal. The queue should contain the names of directories and be implemented in C.

Answer 1

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