PYTHON
Represent an Undirected Graph with an Adjacency List
Learn to represent graph data structures in Python using an adjacency list, a flexible and efficient way to store connections between nodes for various algorithms.
def create_graph():
return {} # Using a dictionary to store the adjacency list
def add_node(graph, node):
if node not in graph:
graph[node] = []
else:
print(f"Node {node} already exists.")
def add_edge(graph, u, v):
# Add edge for undirected graph
if u not in graph:
add_node(graph, u)
if v not in graph:
add_node(graph, v)
if v not in graph[u]: # Prevent duplicate edges
graph[u].append(v)
if u not in graph[v]:
graph[v].append(u)
def print_graph(graph):
print("Graph Adjacency List:")
for node, neighbors in graph.items():
print(f"{node}: {neighbors}")
# Example Usage:
my_graph = create_graph()
add_node(my_graph, 'A')
add_node(my_graph, 'B')
add_node(my_graph, 'C')
add_node(my_graph, 'D')
add_edge(my_graph, 'A', 'B')
add_edge(my_graph, 'A', 'C')
add_edge(my_graph, 'B', 'D')
add_edge(my_graph, 'C', 'D')
add_edge(my_graph, 'C', 'E') # 'E' will be added automatically
print_graph(my_graph)
# Output should look like:
# A: ['B', 'C']
# B: ['A', 'D']
# C: ['A', 'D', 'E']
# D: ['B', 'C']
# E: ['C']
How it works: An adjacency list is a way to represent a graph using a dictionary where each key represents a node, and its corresponding value is a list of its neighboring nodes. This method is memory-efficient for sparse graphs (graphs with relatively few edges) and allows for easy iteration over a node's neighbors. For an undirected graph, an edge between `u` and `v` means `v` is added to `u`'s list, and `u` is added to `v`'s list.