Breadth-First Search Function for Graph Object

Breadth-First Search (BFS) is a graph traversal algorithm that starts from a source node and explores its neighbors before moving to their neighbors. BFS is often used for finding the shortest path in unweighted graphs.

The Graph object contains an adjacency list for each vertex.

Java

Assuming Graph class has LinkedList<Integer>[] adjList:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    LinkedList<Integer>[] adjList;
    int vertices;

    // Constructor and other methods...

    public void bfs(int startVertex) {
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();

        visited[startVertex] = true;
        queue.add(startVertex);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        System.out.println();
    }
}

C++

Assuming Graph class has vector<vector<int>> adjList:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Graph {
public:
    vector<vector<int>> adjList;
    int vertices;

    // Constructor and other methods...

    void bfs(int startVertex) {
        vector<bool> visited(vertices, false);
        queue<int> queue;

        visited[startVertex] = true;
        queue.push(startVertex);

        while (!queue.empty()) {
            int current = queue.front();
            cout << current << " ";
            queue.pop();

            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
        cout << endl;
    }
};

Python

Assuming Graph class has adjList as a list of lists:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjList = [[] for _ in range(vertices)]

    # Other methods to add edges, etc...

    def bfs(self, startVertex):
        visited = [False] * self.vertices
        queue = deque([startVertex])

        visited[startVertex] = True

        while queue:
            current = queue.popleft()
            print(current, end=" ")

            for neighbor in self.adjList[current]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)
        print()

To implement BFS, we use a queue to keep track of nodes to be explored. We also maintain a visited array to mark nodes that have already been visited. We start by marking the source vertex as visited and adding it to the queue. We then loop until the queue is empty, removing each vertex and exploring its unvisited neighbors.