BFS
unknown
c_cpp
a year ago
5.2 kB
3
Indexable
// BFS // 薯妮亞Patata #include <stdio.h> #include <stdlib.h> #include <stdbool.h> // Graph Node typedef struct sNode { int vertex; struct sNode* next; } GNode; // Graph typedef struct sGraph { GNode** adjLists; int numVertices; int* visited; } Graph; // Graph operation Graph* CreateGraph(int vertices); void AddEdge(Graph* graph, int src, int dest); void PrintGraph(Graph* graph); // Queue Node typedef struct sNode1 { int data; struct sNode1 *next; } QNode; // Queue typedef struct sQueue { QNode *front, *rear; } Queue; // Queue operation Queue* CreateQueue(void); // constructor void DeleteQueue(Queue* queue); // destrcutor, not automatically triggered like c++ bool IsEmpty(Queue* queue); // return true if stack is empty void Push(Queue* queue, int item); // add an element at the top void Pop(Queue* queue); // delete top element int Front(Queue* queue); // return front element of queue int Rear(Queue* queue); // return rear element of queue int Size(Queue* queue); // return size of queue void PrintQueue(Queue* queue); // print from front to rear // BFS void BFS(Graph* graph, int startVertex); int main(void) { Graph* graph = CreateGraph(8); AddEdge(graph, 0, 1); AddEdge(graph, 1, 0); AddEdge(graph, 0, 2); AddEdge(graph, 2, 0); AddEdge(graph, 1, 3); AddEdge(graph, 3, 1); AddEdge(graph, 1, 4); AddEdge(graph, 4, 1); AddEdge(graph, 2, 5); AddEdge(graph, 5, 2); AddEdge(graph, 2, 6); AddEdge(graph, 6, 2); AddEdge(graph, 3, 7); AddEdge(graph, 7, 3); AddEdge(graph, 4, 7); AddEdge(graph, 7, 4); AddEdge(graph, 5, 7); AddEdge(graph, 7, 5); AddEdge(graph, 6, 7); AddEdge(graph, 7, 6); BFS(graph, 0); return 0; } // BFS void BFS(Graph* graph, int startVertex) { int currentVertex; int adjVertex; Queue *queue = CreateQueue(); GNode *temp; graph->visited[startVertex] = 1; Push(queue, startVertex); while (!IsEmpty(queue)) { printf("Queue: "); PrintQueue(queue); currentVertex = Front(queue); Pop(queue); printf("Visited %d\n", currentVertex); temp = graph->adjLists[currentVertex]; while (temp != NULL) { adjVertex = temp->vertex; if (graph->visited[adjVertex] == 0) { graph->visited[adjVertex] = 1; Push(queue, adjVertex); } temp = temp->next; } } } // Create a node GNode* CreateNode(int v) { GNode* newNode = malloc(sizeof(GNode)); newNode->vertex = v; newNode->next = NULL; return newNode; } // Create graph Graph* CreateGraph(int vertices) { Graph* graph = (Graph*)malloc(sizeof(Graph)); int i; graph->adjLists = (GNode**)calloc(vertices, sizeof(GNode*)); graph->numVertices = vertices; graph->visited = (int*)calloc(vertices, sizeof(int)); return graph; } // Add edge void AddEdge(Graph* graph, int src, int dest) { GNode* newNode = malloc(sizeof(GNode)); // Add edge from src to dest newNode->vertex = dest; newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; } // Print the graph void PrintGraph(Graph* graph) { int v; GNode* temp; for (v = 0; v < graph->numVertices; v++) { temp = graph->adjLists[v]; while (temp != NULL) temp = temp->next; } } // constructor Queue* CreateQueue(void) { Queue* queue = (Queue*)malloc(sizeof(Queue)); queue->front = NULL; queue->rear = NULL; return queue; } // destrcutor void DeleteQueue(Queue* queue) { while (!IsEmpty(queue)) { Pop(queue); } free(queue); } // return true if queue is empty bool IsEmpty(Queue* queue) { return queue->front == NULL; } // add an element at the end of the queue void Push(Queue* queue, int item) { QNode* newNode = (QNode*)malloc(sizeof(QNode)); newNode->data = item; newNode->next = NULL; if (IsEmpty(queue)) { queue->front = newNode; queue->rear = newNode; } else { queue->rear->next = newNode; queue->rear = newNode; } } // delete the front element of the queue void Pop(Queue* queue) { if (!IsEmpty(queue)) { QNode *temp = queue->front; queue->front = queue->front->next; free(temp); } } // return front element of queue int Front(Queue* queue) { return queue->front->data; } // return rear element of queue int Rear(Queue* queue) { return queue->rear->data; } // return size of queue int Size(Queue* queue) { QNode *temp; int count = 0; for (temp = queue->front; temp != NULL; temp = temp->next) { count++; } return count; } // print from front to rear void PrintQueue(Queue* queue) { QNode *current = queue->front; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); }
Editor is loading...
Leave a Comment