PYTHON
Representing Graphs with Adjacency Lists for Pathfinding
Learn to represent graph data structures using adjacency lists in Python. This snippet demonstrates adding nodes, edges, and performing a basic Breadth-First Search (BFS) for pathfinding, essential for network or routing applications.
class Graph:
def __init__(self):
self.graph = {} # Using a dictionary to store adjacency lists
def add_node(self, node):
if node not in self.graph:
self.graph[node] = []
def add_edge(self, node1, node2, bidirectional=True):
self.add_node(node1)
self.add_node(node2)
self.graph[node1].append(node2)
if bidirectional:
self.graph[node2].append(node1)
def bfs_shortest_path(self, start, end):
if start not in self.graph or end not in self.graph:
return None # Start or end node not in graph
queue = [(start, [start])] # (current_node, path_so_far)
visited = {start}
while queue:
current_node, path = queue.pop(0) # Pop from front for BFS
if current_node == end:
return path
for neighbor in self.graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # No path found
# Example Usage:
# my_graph = Graph()
# my_graph.add_edge('A', 'B')
# my_graph.add_edge('B', 'C')
# my_graph.add_edge('A', 'D')
# my_graph.add_edge('D', 'E')
# my_graph.add_edge('C', 'E')
# path = my_graph.bfs_shortest_path('A', 'E')
# print(f"Shortest path from A to E: {path}")
# Output: Shortest path from A to E: ['A', 'D', 'E'] or ['A', 'B', 'C', 'E'] depending on traversal order and specific impl.
How it works: This snippet defines a `Graph` class using a Python dictionary where keys are nodes and values are lists of adjacent nodes (an adjacency list). Methods `add_node` and `add_edge` manage the graph structure. The `bfs_shortest_path` method demonstrates a Breadth-First Search (BFS) algorithm to find the shortest path between two nodes, useful for navigation and network analysis in web applications. It uses a list as a queue and a set to track visited nodes.