PYTHON
Represent Graphs with Python's Adjacency List
Discover how to effectively represent graph structures using Python dictionaries to create an adjacency list, a common and flexible method for modeling relationships between entities.
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# Adding a new vertex
graph['G'] = []
# Adding an edge (undirected for simplicity)
def add_edge(graph, u, v):
if u not in graph: graph[u] = []
if v not in graph: graph[v] = []
graph[u].append(v)
graph[v].append(u) # For undirected graph
print("Initial Graph Adjacency List:")
for node, neighbors in graph.items():
print(f"{node}: {neighbors}")
add_edge(graph, 'A', 'G')
add_edge(graph, 'F', 'G')
print("
Graph after adding edges:")
for node, neighbors in graph.items():
print(f"{node}: {neighbors}")
# Check if an edge exists
node1 = 'A'
node2 = 'C'
edge_exists = node2 in graph.get(node1, [])
print(f"
Does an edge exist between {node1} and {node2}? {edge_exists}")
node1 = 'A'
node2 = 'X'
edge_exists = node2 in graph.get(node1, [])
print(f"Does an edge exist between {node1} and {node2}? {edge_exists}")
How it works: This snippet demonstrates how to represent a graph using an adjacency list in Python. An adjacency list uses a dictionary where each key represents a vertex (node) and its corresponding value is a list (or set) of its adjacent vertices. This representation is memory-efficient for sparse graphs (graphs with relatively few edges) and allows for quick retrieval of all neighbors of a given vertex. The example shows how to initialize a graph, add new vertices and edges, and check for the existence of an edge.