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.