PYTHON
Build a Graph using Adjacency List with defaultdict
Construct a graph using an adjacency list representation with Python's defaultdict, simplifying the creation and management of nodes and their connections for graph algorithms.
from collections import defaultdict
class Graph:
def __init__(self, directed=False):
self.graph = defaultdict(list) # Adjacency list
self.directed = directed
def add_edge(self, u, v):
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u) # Add reverse edge for undirected graph
def get_neighbors(self, node):
return self.graph[node]
def __str__(self):
output = []
for node in sorted(self.graph.keys()):
output.append(f"{node}: {', '.join(map(str, sorted(self.graph[node])))}")
return "
".join(output)
# Example usage for an undirected graph
print("
--- Undirected Graph ---")
ug = Graph(directed=False)
ug.add_edge('A', 'B')
ug.add_edge('A', 'C')
ug.add_edge('B', 'D')
ug.add_edge('C', 'E')
ug.add_edge('D', 'E')
print(ug)
print(f"Neighbors of A: {ug.get_neighbors('A')}")
# Example usage for a directed graph
print("
--- Directed Graph ---")
dg = Graph(directed=True)
dg.add_edge(0, 1)
dg.add_edge(0, 2)
dg.add_edge(1, 3)
dg.add_edge(2, 3)
dg.add_edge(3, 0) # Back edge
print(dg)
print(f"Neighbors of 0: {dg.get_neighbors(0)}")
print(f"Neighbors of 3: {dg.get_neighbors(3)}")
How it works: This snippet demonstrates building a graph using an adjacency list, a common and efficient representation, especially for sparse graphs. `collections.defaultdict(list)` is used to automatically create an empty list for a node if it's accessed for the first time, simplifying the `add_edge` logic by removing the need for explicit checks. Each key in the dictionary represents a node, and its value is a list of its directly connected neighbors. The `directed` flag allows for easy toggling between directed and undirected graph behavior.