PYTHON
Represent Graphs with Adjacency List
Learn to represent graph data structures in Python using an adjacency list (a dictionary of lists) to model relationships and perform traversals effectively.
class Graph:
def __init__(self):
# Adjacency list: A dictionary where keys are nodes
# and values are lists of adjacent nodes.
self.graph = {}
def add_node(self, node: str) -> None:
if node not in self.graph:
self.graph[node] = []
def add_edge(self, node1: str, node2: str, directed: bool = False) -> None:
self.add_node(node1)
self.add_node(node2)
self.graph[node1].append(node2)
if not directed:
# For an undirected graph, add edge in both directions
self.graph[node2].append(node1)
def get_neighbors(self, node: str) -> list:
return self.graph.get(node, [])
def display(self):
for node, neighbors in self.graph.items():
print(f"{node}: {', '.join(neighbors)}")
# 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("C", "E", directed=True) # Directed edge from C to E
print("Undirected and Directed Graph Representation:")
my_graph.display()
print(f"
Neighbors of B: {my_graph.get_neighbors('B')}")
print(f"Neighbors of E: {my_graph.get_neighbors('E')}")
How it works: An adjacency list is a common and efficient way to represent graphs in programming, especially for sparse graphs (graphs with relatively few edges). It uses a dictionary where each key represents a node in the graph, and its corresponding value is a list of all nodes directly connected to it. This snippet demonstrates how to build such a graph representation, allowing for adding nodes and edges (both directed and undirected) and retrieving neighbors for any given node, forming a flexible base for graph algorithms.