Breadth-first search (BFS) and Depth-first search (DFS) are algorithms commonly used for traversing and searching in graphs and trees. They form the foundation of graph and tree algorithms and are crucial concepts for any computer science student or programmer to master.
What is Breadth-First Search?
BFS is an algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at distance 1 from the starting vertex, then all the vertices at distance 2, and so on. This algorithm can be implemented in python using data structures such as queues, lists, and dictionaries.
In a BFS algorithm, a queue is used to keep track of the vertices to be visited next. The algorithm starts by visiting the starting vertex, marking it as visited, and adding its neighbors to the queue. The next vertex to be visited is the one at the front of the queue, and the process is repeated until all vertices have been visited or the search has been completed.
The implementation of BFS in python can be used for various applications such as finding the shortest path between two vertices, searching for a specific vertex, or checking if a graph is connected. In addition, BFS can also be used to solve problems in artificial intelligence, such as finding the optimal solution for a problem through state space search.
Breadth-first search (BFS) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at distance 1 from the starting vertex, then all the vertices at distance 2, and so on. BFS is implemented using a queue data structure to keep track of the vertices to be visited next.
Here's a step-by-step example of how BFS works:- Start by selecting a starting vertex. Let's say the starting vertex is "A".
- Mark the starting vertex as visited. In our example, mark "A" as visited.
- Add all the neighbors of the starting vertex to the queue. In our example, add the neighbors of "A", i.e., "B" and "C", to the queue.
- The next vertex to be visited is the one at the front of the queue. In our example, "B" is the first vertex in the queue, so it is visited next.
- Mark the visited vertex as visited. In our example, mark "B" as visited.
- Add all the neighbors of the visited vertex to the queue, but only if they have not been visited yet. In our example, add the neighbors of "B", i.e., "D" and "E", to the queue.
- Repeat steps 4-6 until all vertices have been visited or the search has been completed. In our example, the next vertex to be visited is "C". Mark "C" as visited and add its neighbors, "F" and "G", to the queue.
- The next vertex to be visited is "D". Mark "D" as visited and add its neighbors, "H" and "I", to the queue.
- Repeat steps 4-6 until all vertices have been visited. In our example, the next vertices to be visited are "E", "F", "G", "H", and "I".
- The BFS algorithm ends when all vertices have been visited or the search has been completed. In our example, all vertices have been visited, so the BFS algorithm ends.
- This is how the BFS algorithm works in a nutshell. The output of the BFS algorithm depends on the starting vertex and the order in which the vertices are visited. In our example, the output is "A B C D E F G H I".
Breadth-first search (BFS)
- Here’s a general pseudocode for the Breadth-first search (BFS) algorithm:
- Create a queue Q to keep track of the vertices to be visited next.
- Mark the starting vertex as visited and add it to the queue Q.
- Repeat the following steps until the queue is empty: a. Dequeue the front vertex from Q. b. Mark the dequeued vertex as visited. c. Add all the unvisited neighbors of the dequeued vertex to the queue Q. d. Mark the added neighbors as visited.
- End the algorithm when the queue is empty.
This is a basic implementation of the BFS algorithm. The details and implementation can vary depending on the specific problem and use case.
Here’s an implementation of breadth-first search (BFS) in Python using an adjacency list representation of a graph:
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
def BFS(self, s):
visited = [False] * (len(self.graph))
queue = []
visited[s] = True
queue.append(s)
while queue:
s = queue.pop(0)
print(s, end=" ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
print("Following is Breadth First Traversal (starting from vertex 2)")
g.BFS(2)
This is a basic implementation of the BFS algorithm in Python. The output of the above code would be Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1.
Here’s a step-by-step explanation of the code:
A Graph class is defined that has a defaultdict to represent the graph.
The addEdge method is used to add edges to the graph.
The BFS method is defined to implement the BFS algorithm.
- A list visited is created to keep track of the visited vertices.
- A queue queue is created to keep track of the vertices to be visited next.
- The starting vertex is marked as visited and added to the queue.
- The following steps are repeated until the queue is empty:
i. Dequeue the front vertex from the queue.
ii. Mark the dequeued vertex as visited.
iii. Add all the unvisited neighbors of the dequeued vertex to the queue. - End the algorithm when the queue is empty.
This is a basic implementation of the BFS algorithm in Python. The details and implementation can vary depending on the specific problem and use case.
