Graph Traversal
Graph traversal algorithms allow us to explore and visit each vertex in a graph. These algorithms are essential for solving various problems like finding connected components, detecting cycles, and searching for paths.
One common algorithm for traversing a graph is Depth-First Search (DFS). It starts at a given vertex and explores as far as possible before backtracking. This algorithm is implemented using a stack.
Here's an example of implementing DFS in Python:
1if __name__ == '__main__':
2 class Graph:
3 def __init__(self, num_vertices):
4 self.num_vertices = num_vertices
5 self.adj_list = [[] for _ in range(num_vertices)]
6
7 def add_edge(self, source, destination):
8 self.adj_list[source].append(destination)
9 self.adj_list[destination].append(source)
10
11 def dfs(self, start_vertex):
12 stack = [start_vertex]
13 visited = [False] * self.num_vertices
14
15 while stack:
16 vertex = stack.pop()
17
18 if not visited[vertex]:
19 print(vertex)
20 visited[vertex] = True
21
22 for adj_vertex in self.adj_list[vertex]:
23 if not visited[adj_vertex]:
24 stack.append(adj_vertex)
25
26 # Create a graph with 5 vertices
27 g = Graph(5)
28
29 # Add edges to the graph
30 g.add_edge(0, 1)
31 g.add_edge(0, 4)
32 g.add_edge(1, 2)
33 g.add_edge(1, 3)
34 g.add_edge(1, 4)
35 g.add_edge(2, 3)
36 g.add_edge(3, 4)
37
38 # Perform DFS starting from vertex 0
39 print('DFS traversal:')
40 g.dfs(0)In the above code, we define a Graph class that represents a graph using an adjacency list. The dfs method performs the DFS traversal starting from a given vertex. It uses a stack to keep track of the vertices to visit. The visited list is used to mark the visited vertices and avoid infinite loops.
DFS traversal visits all the vertices in the graph in a depth-first manner. It can be used to explore all connected components of a graph and detect cycles.
Another common graph traversal algorithm is Breadth-First Search (BFS), which explores all the vertices at the current level before moving to the next level. It is implemented using a queue.
Here's an example of implementing BFS in 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):
14 queue = deque([start_vertex])
15 visited = [False] * self.num_vertices
16
17 while queue:
18 vertex = queue.popleft()
19
20 if not visited[vertex]:
21 print(vertex)
22 visited[vertex] = True
23
24 for adj_vertex in self.adj_list[vertex]:
25 if not visited[adj_vertex]:
26 queue.append(adj_vertex)
27
28 # Create a graph with 5 vertices
29 g = Graph(5)
30
31 # Add edges to the graph
32 g.add_edge(0, 1)
33 g.add_edge(0, 4)
34 g.add_edge(1, 2)
35 g.add_edge(1, 3)
36 g.add_edge(1, 4)
37 g.add_edge(2, 3)
38 g.add_edge(3, 4)
39
40 # Perform BFS starting from vertex 0
41 print('BFS traversal:')
42 g.bfs(0)In this code, we define a similar Graph class, and the bfs method performs the BFS traversal starting from a given vertex. It uses a queue to keep track of the vertices to visit and the visited list to mark visited vertices.
BFS traversal visits all the vertices in the graph in a breadth-first manner. It can be used to find the shortest path between two vertices as well as to explore all the vertices in the graph.
Understanding graph traversal algorithms is crucial when working with graphs in robotics and computer vision. These algorithms can help in tasks like path planning, object recognition, and environment exploration.
xxxxxxxxxxif __name__ == '__main__': class Graph: def __init__(self, num_vertices): self.num_vertices = num_vertices self.adj_list = [[] for _ in range(num_vertices)] def add_edge(self, source, destination): self.adj_list[source].append(destination) self.adj_list[destination].append(source) # Create a graph with 5 vertices g = Graph(5) # Add edges to the graph g.add_edge(0, 1) g.add_edge(0, 4) g.add_edge(1, 2) g.add_edge(1, 3) g.add_edge(1, 4) g.add_edge(2, 3) g.add_edge(3, 4) # Print the adjacency list for vertex, adj_vertices in enumerate(g.adj_list): print(f'Adjacent vertices of vertex {vertex}: {adj_vertices}')