(BFS) Algorithm

BFS stands for Breadth first search Algorithms in graphs

A graph data structure is a mathematical representation of a set of objects where some pairs of the objects are connected by links. It consists of two main components: vertices (also called nodes) and edges. Graphs are versatile data structures.

Components of a Graph:

Edges: Edges are connections or relationships between vertices. They can be directed or undirected.

Nodes: Representing entities or points.

Real-life applications where BFS

Network Routing:

Social Network Analysis:

Puzzle Solving:

GPS Navigation Systems:

Let's code

Let's try to first think that what are the main requirement for creating a graph Yes you are thinking right first is node(Vertices) and edges we should require.

#include<bits/stdc++.h>
using namesapce std;
int main(){

int numVertices, numEdges;
cout<<"Enrter the number of vertices:"<<endl;
cin>>numVertices;

cout<<"Enter the total number of edges:"<<endl;
cin>>numEdges;


return 0;
}

Now suppose you are standing on the node 1. So Now think where where you can go with the help of node one. Similarly for the other nodes.

For all of this we need a kind of list and something else so we can store the paths

we use Adjacency List:

but wait we need something else. That is a visited kind of thing where we can store the visited nodes so we can avoid the repetition of noise. In the staring make every Node un-visited.

Visited array / visited unordered_map

The size of the Both Data structure is depend on the Number of Vertices.

vector<vector<int>> adjList(numVertices); 
vector<bool> visited(numVertices, false);

Now take the input as edges in pair for example in above figure 1 is connected to 2,3,4 so this will we the input for the node 1

cout << "Enter the edges (vertex pairs):" << endl;
for(int i = 0; i<numEdges;i++)
{
  int u,v;
  cin>>u>>v;
  adjList[u].push_back(v); // Adding edges to the adjacency list (assuming an undirected graph)
  adjList[v].push_back(u); // For directed graphs, only add one direction
}

    int startNode;
    cout << "Enter the starting node for BFS traversal: ";
    cin >> startNode;

    cout << "Breadth-First Search Traversal:" << endl;
    BFS(startNode, visited, adjList);

Suppose you are standing on the Node 1 and after .then you have to traverse the another node. Means you have to out the first node. For this first in first out process we use Queue data Structure.

void BFS(int start, vector<bool> &visited, vector<vector<int>> &adjList) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int currNode = q.front();
        q.pop();
        cout << currNode << " "; // Process the current node, here we are just printing it

        // Traverse all the adjacent nodes of the current node
        for (int adjacent : adjList[currNode]) {
            if (!visited[adjacent]) {
                q.push(adjacent);
                visited[adjacent] = true;
            }
        }
    }
}

Full Code.

#include<bits/stdc++.h>
using namesapce std;

// Function to perform Breadth-First Search traversal
void BFS(int start, vector<bool> &visited, vector<vector<int>> &adjList) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int currNode = q.front();
        q.pop();
        cout << currNode << " "; /
        // Traverse all the adjacent nodes of the current node
        for (int adjacent : adjList[currNode]) {
            if (!visited[adjacent]) {
                q.push(adjacent);
                visited[adjacent] = true;
            }
        }
    }
}

int main() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices and edges: ";
    cin >> numVertices >> numEdges;

    vector<vector<int>> adjList(numVertices); 
    vector<bool> visited(numVertices, false); 

    cout << "Enter the edges (vertex pairs):" << endl;
    for (int i = 0; i < numEdges; ++i) {
        int u, v;
        cin >> u >> v;
        adjList[u].push_back(v); 
        adjList[v].push_back(u);
    }

    int startNode;
    cout << "Enter the starting node for BFS traversal: ";
    cin >> startNode;

    cout << "Breadth-First Search Traversal:" << endl;
    BFS(startNode, visited, adjList);

    return 0;
}

Input(type) for the above code

Number of vertices: 6
Number of edges: 7

Edges (vertex pairs):
0 1
0 2
1 3
1 4
2 4
3 5
4 5

Starting node for BFS traversal: 0

output

Breadth-First Search Traversal: 0 1 2 3 4 5

Thank you for reading my content. Be sure to follow and comment on what you want me to write about next 🤓