Adjacency List in a Graph

Understanding Graph Representation in Python with Adjacency Lists

In this post, we'll explore how to represent a graph using adjacency lists in Python, utilizing the defaultdict from the collections module. Graphs are a powerful data structure that allows us to model relationships between nodes (or vertices) with connections (or edges). This representation is particularly useful when you need to store and visualize relationships, like social networks, maps, or web page links.

Let's dive into the code and break it down step by step.

Code Overview

Here’s a Python implementation that reads a graph from user input and outputs the adjacency list representation of the graph.

Python Code: 

from collections import defaultdict

# Initialize an empty graph as a defaultdict of lists
graph = defaultdict(list)

# Read the number of vertices (v) and edges (e)
v, e = map(int, input().split())

# Iterate over the number of edges to build the graph
for i in range(e):
    u, v = map(str, input().split())
    graph[u].append(v)
    graph[v].append(u)

# Print the adjacency list representation of the graph
for i in graph:
    print(i, "->", graph[i])

Input

The program starts by reading the number of vertices (v) and edges (e). Then, for each edge, it adds a bidirectional connection between two nodes.

For example, the input:

7 9
A B
A C
A F
C E
C F
C D
D E
D G
G F

This represents a graph with 7 vertices and 9 edges, where each line after the vertex/edge count defines an edge between two vertices (e.g., A B means there’s an edge between vertex A and vertex B).

Output

The program then outputs the adjacency list representation of the graph. For each node, it shows the list of nodes it is directly connected to. Based on the input above, the output will look like this:

F -> ['A', 'C', 'G']
C -> ['A', 'E', 'F', 'D']
G -> ['D', 'F']
D -> ['C', 'E', 'G']
A -> ['B', 'C', 'F']
E -> ['C', 'D']
B -> ['A']

How the Code Works

1. Using defaultdict:
   We use defaultdict(list) to initialize our graph. This ensures that if we try to access a key that doesn't yet exist, it automatically creates an empty list for that key. This is perfect for building an adjacency list where each node will map to a list of its neighboring nodes.

2. Adding Edges:
   For each edge, we add both connections. Since it’s an undirected graph, if there is an edge between A and B, then we need to append B to the list of neighbors for A, and A to the list of neighbors for B.

3. Printing the Graph:
   Once all edges are added, we loop through each node in the graph and print its neighbors in the format node -> [neighbor1, neighbor2, ...]. This gives us a visual representation of the graph's structure.

Understanding the Output

Let’s break down the output:

• F -> ['A', 'C', 'G']
  Node F is connected to nodes A, C, and G.

• C -> ['A', 'E', 'F', 'D']
  Node C has four neighbors: A, E, F, and D.

• G -> ['D', 'F']
  Node G is connected to nodes D and F.

This adjacency list format is a convenient way to represent a graph because it shows, for each node, the nodes it's directly connected to. This format can easily be used in graph algorithms like depth-first search (DFS), breadth-first search (BFS), or shortest-path algorithms.