BFS is a traversal algorithm for graph or tree data structures. It explores nodes level by level, starting from a specified node (often called the source) and moving outward. BFS is commonly used to find the shortest path in an unweighted graph.<\/p>\n\n\n\n
\n#include <stdio.h>\n#include <stdlib.h>\n\n#define MAX_NODES 100\n\n\/\/ Structure to represent a queue\ntypedef struct {\n int items[MAX_NODES];\n int front, rear;\n} Queue;\n\n\/\/ Function to create a queue\nQueue* createQueue() {\n Queue* q = (Queue*)malloc(sizeof(Queue));\n q->front = -1;\n q->rear = -1;\n return q;\n}\n\n\/\/ Function to check if the queue is empty\nint isEmpty(Queue* q) {\n return q->front == -1;\n}\n\n\/\/ Function to add an element to the queue\nvoid enqueue(Queue* q, int value) {\n if (q->rear == MAX_NODES - 1) {\n printf("Queue is full\\n");\n } else {\n if (q->front == -1) {\n q->front = 0;\n }\n q->rear++;\n q->items[q->rear] = value;\n }\n}\n\n\/\/ Function to remove an element from the queue\nint dequeue(Queue* q) {\n if (isEmpty(q)) {\n printf("Queue is empty\\n");\n return -1;\n } else {\n int item = q->items[q->front];\n if (q->front >= q->rear) {\n q->front = q->rear = -1; \/\/ Reset queue\n } else {\n q->front++;\n }\n return item;\n }\n}\n\n\/\/ Function to perform BFS and search for a specific node\nint bfs(int graph[MAX_NODES][MAX_NODES], int start, int target, int num_nodes) {\n int visited[MAX_NODES] = {0}; \/\/ Array to track visited nodes\n Queue* q = createQueue(); \/\/ Create the queue\n\n \/\/ Start from the initial node\n visited[start] = 1; \/\/ Mark it as visited\n enqueue(q, start); \/\/ Enqueue the starting node\n\n printf("BFS Traversal: ");\n\n while (!isEmpty(q)) {\n int current = dequeue(q); \/\/ Dequeue a vertex\n printf("%d ", current); \/\/ Print it\n\n \/\/ Check if we found the target node\n if (current == target) {\n printf("\\nNode %d found!\\n", target);\n return 1; \/\/ Node found\n }\n\n \/\/ Explore all adjacent nodes\n for (int i = 0; i < num_nodes; i++) {\n if (graph[current][i] == 1 && !visited[i]) { \/\/ If there's an edge and not visited\n visited[i] = 1; \/\/ Mark it as visited\n enqueue(q, i); \/\/ Enqueue the adjacent node\n }\n }\n }\n \n printf("\\nNode %d not found.\\n", target);\n return 0; \/\/ Node not found\n}\n\n\/\/ Main function\nint main() {\n \/\/ Example graph represented as an adjacency matrix\n int graph[MAX_NODES][MAX_NODES] = {0};\n int num_nodes = 7;\n\n \/\/ Adding edges\n graph[0][1] = graph[1][0] = 1; \/\/ Edge between 0 and 1\n graph[0][2] = graph[2][0] = 1; \/\/ Edge between 0 and 2\n graph[1][3] = graph[3][1] = 1; \/\/ Edge between 1 and 3\n graph[1][4] = graph[4][1] = 1; \/\/ Edge between 1 and 4\n graph[2][5] = graph[5][2] = 1; \/\/ Edge between 2 and 5\n graph[2][6] = graph[6][2] = 1; \/\/ Edge between 2 and 6\n\n int target;\n printf("Enter the node to search for: ");\n scanf("%d", &target); \/\/ Input the node to search for\n\n bfs(graph, 0, target, num_nodes); \/\/ Start BFS from node 0\n\n return 0;\n}\n\n\n<\/pre><\/div>\n\n\nExplanation of the Code<\/h3>\n\n\n\n\n- Graph Representation:<\/strong>\n
\n- The graph is represented using an adjacency list, where each vertex points to a list of its neighbors. The
Node<\/code> structure is used for the list.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Queue for BFS:<\/strong>\n
\n- A simple queue structure is implemented to keep track of nodes to be explored. The queue maintains two indices (
front<\/code> and rear<\/code>).<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Graph Functions:<\/strong>\n
\n- createNode<\/strong>: Creates a new node for the adjacency list.<\/li>\n\n\n\n
- createGraph<\/strong>: Initializes a graph with a specified number of vertices.<\/li>\n\n\n\n
- addEdge<\/strong>: Adds an edge between two vertices. Since the graph is undirected, it adds an edge in both directions.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- BFS Implementation:<\/strong>\n
\n- In the
bfs<\/code> function, we start from the specified vertex, marking it as visited and enqueueing it.<\/li>\n\n\n\n- The algorithm enters a loop where it dequeues a vertex, prints it, and enqueues all its unvisited neighbors.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Main Function:<\/strong>\n
\n- The
main<\/code> function creates a graph with 6 vertices, adds edges, and initiates the BFS starting from vertex 0<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\nExample Input and Output<\/h3>\n\n\n\nInput (Edges of the graph):<\/h4>\n\n\n\nThe edges added to the graph are:
0 \u2192 1
0 \u2192 2
1 \u2192 3
1 \u2192 4
2 \u2192 4
3 \u2192 5<\/pre>\n\n\n\n
\n- <\/li>\n<\/ul>\n\n\n\n
Output<\/h4>\n\n\n\n
When you run the program, you will see the following output:<\/p>\n\n\n\n
yamlCopy codeBFS Traversal: 0 1 2 3 4 5 \n<\/code><\/pre>\n\n\n\nConclusion<\/h3>\n\n\n\n
This program demonstrates the implementation of the BFS algorithm in C. It shows how to traverse a graph level by level, which can be useful in various applications such as finding the shortest path in unweighted graphs or exploring connected components. You can modify the graph structure by changing the edges or the starting vertex to observe different traversal behaviors.<\/p>\n