Graph search algorithms are essential for exploring and finding solutions in graphs. These algorithms help in solving various problems in robotics and computer vision. For example, they can be used to find the shortest path between two points, perform object recognition, or explore an environment.
One common search algorithm is Breadth-First Search (BFS). BFS explores all the vertices at the current level before moving to the next level. It uses a queue to keep track of the vertices to visit. This algorithm is often used for pathfinding, as it guarantees the shortest path when all edge weights are equal.
Here's an example of implementing BFS in Python:
PYTHON
1if __name__ == '__main__':
2 from collections import deque
3
4 class Graph:
5 def __init__(self, num_vertices):
6 self.num_vertices = num_vertices
7 self.adj_list = [[] for _ in range(num_vertices)]
8
9 def add_edge(self, source, destination):
10 self.adj_list[source].append(destination)
11 self.adj_list[destination].append(source)
12
13 def bfs(self, start_vertex, target_vertex):
14 queue = deque([(start_vertex, [start_vertex])])
15 visited = [False] * self.num_vertices
16
17 while queue:
18 vertex, path = queue.popleft()
19
20 if not visited[vertex]:
21 if vertex == target_vertex:
22 return path
23
24 visited[vertex] = True
25
26 for adj_vertex in self.adj_list[vertex]:
27 if not visited[adj_vertex]:
28 queue.append((adj_vertex, path + [adj_vertex]))
29
30 return None
31
32 # Create a graph with 7 vertices
33 g = Graph(7)
34
35 # Add edges to the graph
36 g.add_edge(0, 1)
37 g.add_edge(0, 2)
38 g.add_edge(1, 3)
39 g.add_edge(1, 4)
40 g.add_edge(2, 5)
41 g.add_edge(2, 6)
42 g.add_edge(3, 4)
43
44 # Perform BFS and find the shortest path from vertex 0 to 4
45 shortest_path = g.bfs(0, 4)
46
47 if shortest_path:
48 print(f'Shortest path: {shortest_path}')
49 else:
50 print('Path not found')