BFS Algorithm in C
A graph traversal technique called breadth-first search (BFS) investigates every vertex of a graph in breadth-first order, which means it visits every vertex at one level before going to the next level. Once all the vertices have been explored, it returns to the source vertex and investigates its neighboring vertices. It then continues to those neighboring vertices, and so on.
A queue data structure may be used to construct BFS in C and keep track of the vertices that need to be investigated. Finding the shortest path between the source vertex and any other vertex in an unweighted network is one of the critical features of BFS. Due to this characteristic, BFS is a primary method for many applications, including solving the 15-puzzle, establishing the connectedness of a network, and finding the shortest path through a maze.
- The BFS algorithm is used to find or navigate across tree or graph data structures.
- It traverses every vertex of a graph or every node of a tree in breadth-first order, or every vertex at one level is visited before advancing to the next level.
- BFS keeps track of the vertices that need to be visited via a queue data structure.
- Typically, you start with a graph or tree represented using adjacency lists or matrices to build BFS in C.
- The BFS algorithm in C is briefly described as follows:
- To store vertices, construct a queue data structure.
- All vertices should be started as unvisited.
- Mark a beginning vertex as visited after selecting it.
- Enqueue the starting vertex.
- While the queue is not empty:
- Dequeue a vertex from the queue.
- Vertex processing includes printing or carrying out any other desired procedures.
- Enqueue all the adjacent unvisited vertices of the dequeued vertex.
- Enqueue it and mark each neighboring vertex as visited.
- Keep doing this until the queue is cleared.
- You would typically need to develop helper functions to handle actions like building a graph, adding edges, and enqueuing/dequeuing vertices from the queue.
- BFS may be used to determine the shortest path between any two nodes in an unweighted network and ensures that it visits every vertex of a connected graph.
- You should change the algorithm to handle any separate components in the network independently.
- BFS can be applied recursively or iteratively. Due to the nature of the method, the iterative technique of using a queue is more popular.
The Breadth-First Search (BFS) method in C is demonstrated here:
Code:
#include <stdio.h>
#include <stdbool.h>
#define MAX_NODES 100
//queue implementation
struct Queue {
int items[MAX_NODES];
int front;
int rear;
};
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}
bool isEmpty(struct Queue* q) {
return q->rear == -1;
}
void enqueue(struct Queue* q, int value) {
if (q->rear == MAX_NODES - 1) {
printf("Queue is full!\n");
} else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
int dequeue(struct Queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty!\n");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
q->front = q->rear = -1;
}
}
return item;
}
// Graph representation using adjacency matrix
void bfs(int adjMatrix[][MAX_NODES], int nodes, int start node) {
bool visited[MAX_NODES] = {false};
struct Queue q;
initQueue(&q);
visited[startNode] = true;
printf("Visited node: %d\n", startNode);
enqueue(&q, startNode);
while (!isEmpty(&q)) {
int current = dequeue(&q);
for (int i = 0; i < nodes; ++i) {
if (adjMatrix[current][i] == 1 && !visited[i]) {
visited[i] = true;
printf("Visited node: %d\n", i);
enqueue(&q, i);
}
}
}
}
int main() {
int nodes, edges, startNode;
printf("Enter the number of nodes in the graph: ");
scanf("%d", &nodes);
int adjMatrix[MAX_NODES][MAX_NODES];
for (int i = 0; i < nodes; ++i) {
for (int j = 0; j < nodes; ++j) {
adjMatrix[i][j] = 0;
}
}
printf("Enter the number of edges in the graph: ");
scanf("%d", &edges);
printf("Enter the edges in the graph:\n");
for (int i = 0; i < edges; ++i) {
int u, v;
scanf("%d %d", &u, &v);
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // If the graph is undirected
}
printf("Enter the starting node for BFS: ");
scanf("%d", &startNode);
printf("BFS Traversal:\n");
bfs(adjMatrix, nodes, startNode);
return 0;
}
Output:
![BFS Algorithm in C](https://static.tutorialandexample.com/c/bfs-algorithm-in-c1.png)
A fundamental graph traversal technique known as breadth-first search (BFS) searches all of a graph's vertices in breadth-first order or by examining all of a vertex's neighbors before going on to the level of vertices below it. BFS has several applications in computer science, notably in graph theory and problem-solving. The following are some significant justifications for why BFS is crucial in C and computer science in general:
- Graph traversal
- Shortest path finding
- Minimum spanning trees
- Bipartite graph detection
- Web Crawling
Graph traversal:
BFS enables systematic traversal of or visits to each vertex in a graph. Before going to the next level, it ensures every vertex in the previous level has been visited. This characteristic is helpful for various graph-related problems, including finding the shortest path, detecting connected components, and spotting cycles in a graph.
Shortest path finding:
Finding the shortest route between two vertices in an unweighted network is one of the essential uses of BFS. The first time a vertex is visited during the traversal offers us the shortest path from the beginning vertex to that vertex since BFS accesses vertices in layers. This property is used by several techniques, including Dijkstra's algorithm, which can find the shortest path in weighted graphs.
Minimum spanning trees:
To determine a graph's minimal spanning tree (MST), algorithms like Prim's and Kruskal's employ BFS. MST is a tree that covers every vertex of a weighted, linked graph with the least amount of edge weight. These algorithms effectively search the network and create the MST by utilizing BFS.
Bipartite graph detection:
BFS may be used to determine whether or not a given graph is bipartite. A graph that can be separated into two groups of vertices with no edges connecting vertices in the same set is said to be bipartite. We can determine whether there is a coloring conflict by giving the vertices alternate colors while doing the BFS traverse. The graph is bipartite if there is no dispute.
Web crawling:
BFS may be used in web crawling or web scraping programs to methodically investigate web pages by accessing every link reachable at each level after beginning from a given URL. This strategy ensures that the online pages are covered by the breadth-first crawling process, which is advantageous for activities like indexing web material, creating search engine databases, or data mining.
The BFS Algorithm's time complexity is
The time complexity of the Breadth-First Search (BFS) algorithm, where V is the number of graph vertices (nodes), and E is the number of graph edges, is O(V + E). Each vertex and each edge are walked through once in the BFS algorithm. Starting with the source node and visiting all of its neighbors before going on to the next level of nodes, the method performs a breadth-first exploration of the graph.
A breakdown of the time complexity is shown below:
- It takes O(1) time to visit each vertex.
- Each edge requires O(1) time to traverse.
- With a total time complexity of O(V + E), the method visits each vertex and travels down each edge once.
It's crucial to remember that this temporal complexity is predicated on the network represented by an adjacency matrix, enabling constant-time access to neighbors. The time complexity may change based on the implementation and the particular operations used to access neighbors if the graph is represented using an adjacency list.