📘 Graph Representation: Adjacency Lists

🎯 Introduction

Welcome to this exciting tutorial on Graph Representation using Adjacency Lists! 🎉 In this guide, we’ll explore how to represent graphs efficiently in Python using one of the most popular and flexible data structures.

You’ll discover how adjacency lists can transform your ability to work with networks, relationships, and connected data. Whether you’re building social networks 🌐, route planning systems 🗺️, or recommendation engines 🎯, understanding adjacency lists is essential for efficient graph manipulation.

By the end of this tutorial, you’ll feel confident implementing and using adjacency lists in your own projects! Let’s dive in! 🏊‍♂️

📚 Understanding Adjacency Lists

🤔 What is an Adjacency List?

An adjacency list is like a phone book for graphs! 📱 Think of it as a collection where each person (node) has their own list of contacts (connected nodes) that they can directly call.

In Python terms, an adjacency list is a way to represent a graph where each vertex stores a list of its neighboring vertices. This means you can:

• ✨ Efficiently store sparse graphs (graphs with few edges)
• 🚀 Quickly find all neighbors of a vertex
• 🛡️ Use minimal memory for large graphs

💡 Why Use Adjacency Lists?

Here’s why developers love adjacency lists:

1. Space Efficiency 🔒: Only stores existing edges
2. Fast Neighbor Access 💻: O(1) to get all neighbors
3. Dynamic Structure 📖: Easy to add/remove vertices and edges
4. Flexible Representation 🔧: Works with weighted and directed graphs

Real-world example: Imagine building a social network 🌐. With adjacency lists, you can efficiently store each user’s friends list without wasting space on non-existent friendships!

🔧 Basic Syntax and Usage

📝 Simple Example

Let’s start with a friendly example:

# 👋 Hello, Graph Adjacency Lists!
# 🎨 Creating a simple graph using a dictionary
graph = {
    'A': ['B', 'C'],      # 👤 A is connected to B and C
    'B': ['A', 'D', 'E'], # 🎂 B is connected to A, D, and E
    'C': ['A', 'F'],      # 🎯 C is connected to A and F
    'D': ['B'],           # 📍 D is connected to B
    'E': ['B', 'F'],      # 🌟 E is connected to B and F
    'F': ['C', 'E']       # 🎊 F is connected to C and E
}

# 🔍 Accessing neighbors
print(f"Neighbors of A: {graph['A']}")  # Output: ['B', 'C']

💡 Explanation: Notice how we use a dictionary where keys are vertices and values are lists of neighbors. Simple and efficient!

🎯 Common Patterns

Here are patterns you’ll use daily:

# 🏗️ Pattern 1: Graph class implementation
class Graph:
    def __init__(self):
        self.adjacency_list = {}  # 📦 Initialize empty graph
    
    # ➕ Add a vertex
    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []
            print(f"✨ Added vertex: {vertex}")
    
    # 🔗 Add an edge (undirected)
    def add_edge(self, v1, v2):
        if v1 in self.adjacency_list and v2 in self.adjacency_list:
            self.adjacency_list[v1].append(v2)
            self.adjacency_list[v2].append(v1)
            print(f"🌉 Connected {v1} ↔️ {v2}")

# 🎮 Using our graph
my_graph = Graph()
my_graph.add_vertex("Alice")
my_graph.add_vertex("Bob")
my_graph.add_edge("Alice", "Bob")

💡 Practical Examples

🛒 Example 1: Social Network Friend System

Let’s build something real:

# 🌐 Social Network using Adjacency Lists
class SocialNetwork:
    def __init__(self):
        self.users = {}  # 👥 User -> Friends list
        self.user_data = {}  # 📊 Additional user info
    
    # 👤 Add a new user
    def add_user(self, username, emoji="😊"):
        if username not in self.users:
            self.users[username] = []
            self.user_data[username] = {"emoji": emoji, "friend_count": 0}
            print(f"{emoji} {username} joined the network!")
    
    # 🤝 Add friendship (mutual connection)
    def add_friendship(self, user1, user2):
        if user1 in self.users and user2 in self.users:
            if user2 not in self.users[user1]:
                self.users[user1].append(user2)
                self.users[user2].append(user1)
                self.user_data[user1]["friend_count"] += 1
                self.user_data[user2]["friend_count"] += 1
                print(f"🎉 {user1} and {user2} are now friends!")
    
    # 🔍 Get friend recommendations
    def get_friend_suggestions(self, user):
        if user not in self.users:
            return []
        
        suggestions = set()
        # Friends of friends who aren't already friends
        for friend in self.users[user]:
            for friend_of_friend in self.users[friend]:
                if friend_of_friend != user and friend_of_friend not in self.users[user]:
                    suggestions.add(friend_of_friend)
        
        return list(suggestions)
    
    # 📊 Display network stats
    def show_network(self):
        print("\n📊 Social Network Status:")
        for user, friends in self.users.items():
            emoji = self.user_data[user]["emoji"]
            print(f"  {emoji} {user}: {len(friends)} friends → {friends}")

# 🎮 Let's use it!
network = SocialNetwork()
network.add_user("Alice", "👩")
network.add_user("Bob", "👨")
network.add_user("Charlie", "🧑")
network.add_user("Diana", "👩‍💼")
network.add_user("Eve", "👩‍🎨")

network.add_friendship("Alice", "Bob")
network.add_friendship("Bob", "Charlie")
network.add_friendship("Charlie", "Diana")
network.add_friendship("Bob", "Eve")

network.show_network()
print(f"\n💡 Friend suggestions for Alice: {network.get_friend_suggestions('Alice')}")

🎯 Try it yourself: Add a method to find the shortest path between two users!

🎮 Example 2: City Route Planner

Let’s make it fun with a route planning system:

# 🗺️ City Route Planner with Weighted Edges
class CityMap:
    def __init__(self):
        self.cities = {}  # City -> [(neighbor, distance, emoji)]
    
    # 🏙️ Add a city
    def add_city(self, name, emoji="🏙️"):
        if name not in self.cities:
            self.cities[name] = []
            print(f"{emoji} Added city: {name}")
    
    # 🛣️ Add a road between cities
    def add_road(self, city1, city2, distance, road_type="🛣️"):
        if city1 in self.cities and city2 in self.cities:
            self.cities[city1].append((city2, distance, road_type))
            self.cities[city2].append((city1, distance, road_type))
            print(f"{road_type} Connected {city1} ↔️ {city2} ({distance} km)")
    
    # 🚗 Find all routes from a city
    def find_routes_from(self, start_city):
        if start_city not in self.cities:
            return []
        
        routes = []
        for destination, distance, road_type in self.cities[start_city]:
            routes.append({
                "to": destination,
                "distance": distance,
                "road": road_type,
                "travel_time": distance / 60  # Assuming 60 km/h average
            })
        return routes
    
    # 🎯 Find cities within distance
    def find_nearby_cities(self, city, max_distance):
        if city not in self.cities:
            return []
        
        nearby = []
        for dest, dist, road in self.cities[city]:
            if dist <= max_distance:
                nearby.append((dest, dist, road))
        
        return sorted(nearby, key=lambda x: x[1])  # Sort by distance
    
    # 📊 Display map
    def show_map(self):
        print("\n🗺️ City Map Network:")
        for city, connections in self.cities.items():
            print(f"\n📍 {city}:")
            for dest, dist, road in connections:
                print(f"  {road} → {dest} ({dist} km)")

# 🎮 Create our map!
city_map = CityMap()
city_map.add_city("Paris", "🗼")
city_map.add_city("London", "🏰")
city_map.add_city("Berlin", "🏛️")
city_map.add_city("Rome", "🏛️")
city_map.add_city("Madrid", "🏰")

city_map.add_road("Paris", "London", 344, "🚄")  # High-speed rail
city_map.add_road("Paris", "Berlin", 878, "✈️")  # Flight
city_map.add_road("Berlin", "Rome", 1181, "🛣️") # Highway
city_map.add_road("Rome", "Madrid", 1365, "✈️")  # Flight
city_map.add_road("Madrid", "Paris", 1052, "🚄") # High-speed rail

city_map.show_map()
print(f"\n🚗 Routes from Paris: {city_map.find_routes_from('Paris')}")
print(f"\n📍 Cities within 1000km of Berlin: {city_map.find_nearby_cities('Berlin', 1000)}")

🚀 Advanced Concepts

🧙‍♂️ Advanced Topic 1: Directed Graphs

When you’re ready to level up, try directed graphs:

# 🎯 Advanced: Directed Graph with Cycle Detection
class DirectedGraph:
    def __init__(self):
        self.adj_list = {}
        
    def add_vertex(self, v):
        if v not in self.adj_list:
            self.adj_list[v] = []
    
    def add_directed_edge(self, from_v, to_v):
        if from_v in self.adj_list and to_v in self.adj_list:
            self.adj_list[from_v].append(to_v)
            print(f"➡️ {from_v} → {to_v}")
    
    # 🔄 Detect cycles using DFS
    def has_cycle(self):
        visited = set()
        rec_stack = set()
        
        def dfs(vertex):
            visited.add(vertex)
            rec_stack.add(vertex)
            
            for neighbor in self.adj_list.get(vertex, []):
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True
            
            rec_stack.remove(vertex)
            return False
        
        for vertex in self.adj_list:
            if vertex not in visited:
                if dfs(vertex):
                    return True
        return False

# 🪄 Using directed graphs
task_graph = DirectedGraph()
for task in ["A", "B", "C", "D"]:
    task_graph.add_vertex(task)

task_graph.add_directed_edge("A", "B")  # A must complete before B
task_graph.add_directed_edge("B", "C")  # B must complete before C
task_graph.add_directed_edge("C", "D")  # C must complete before D
# task_graph.add_directed_edge("D", "A")  # This would create a cycle!

print(f"\n🔄 Has cycle? {task_graph.has_cycle()}")

🏗️ Advanced Topic 2: Graph Traversal Algorithms

For the brave developers - BFS and DFS:

# 🚀 Graph Traversal: BFS and DFS
from collections import deque

class GraphTraversal:
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)
    
    # 🌊 Breadth-First Search
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        path = []
        
        while queue:
            vertex = queue.popleft()
            path.append(vertex)
            
            for neighbor in self.graph.get(vertex, []):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return path
    
    # 🏔️ Depth-First Search
    def dfs(self, start):
        visited = set()
        path = []
        
        def dfs_helper(vertex):
            visited.add(vertex)
            path.append(vertex)
            
            for neighbor in self.graph.get(vertex, []):
                if neighbor not in visited:
                    dfs_helper(neighbor)
        
        dfs_helper(start)
        return path

# 🎮 Test traversals
g = GraphTraversal()
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "E"), ("D", "E"), ("D", "F")]
for u, v in edges:
    g.add_edge(u, v)

print(f"🌊 BFS from A: {g.bfs('A')}")
print(f"🏔️ DFS from A: {g.dfs('A')}")

⚠️ Common Pitfalls and Solutions

😱 Pitfall 1: Missing Vertex Check

# ❌ Wrong way - no vertex validation!
graph = {'A': ['B'], 'B': ['A']}
graph['C'].append('D')  # 💥 KeyError: 'C' doesn't exist!

# ✅ Correct way - always check first!
graph = {'A': ['B'], 'B': ['A']}
if 'C' in graph:
    graph['C'].append('D')
else:
    graph['C'] = ['D']  # Create vertex first
    print("✅ Created vertex C before adding edge!")

🤯 Pitfall 2: Duplicate Edges in Undirected Graphs

# ❌ Dangerous - duplicate edges!
def add_edge_wrong(graph, u, v):
    graph[u].append(v)
    graph[v].append(u)
    # Calling again creates duplicates!

# ✅ Safe - check for existing edges!
def add_edge_safe(graph, u, v):
    if v not in graph[u]:
        graph[u].append(v)
    if u not in graph[v]:
        graph[v].append(u)
    print(f"✅ Added unique edge {u} ↔️ {v}")

🛠️ Best Practices

1. 🎯 Use Sets for Unique Edges: adjacency_list[v] = set() prevents duplicates
2. 📝 Validate Vertices: Always check if vertices exist before operations
3. 🛡️ Handle Edge Cases: Empty graphs, self-loops, disconnected components
4. 🎨 Choose Right Representation: Lists for simple graphs, dicts for weighted
5. ✨ Keep It Pythonic: Use defaultdict, list comprehensions, and generators

🧪 Hands-On Exercise

🎯 Challenge: Build a Game Quest Dependency System

Create a quest system for an RPG game:

📋 Requirements:

• ✅ Quests with prerequisites (directed graph)
• 🏷️ Quest categories (main, side, daily)
• 👤 Track completed quests per player
• 📅 Unlock new quests when prerequisites are met
• 🎨 Each quest needs an emoji and rewards!

🚀 Bonus Points:

• Find all available quests for a player
• Detect circular dependencies
• Calculate quest completion percentage

💡 Solution

# 🎯 Our quest dependency system!
class QuestSystem:
    def __init__(self):
        self.quests = {}  # quest_id -> quest_data
        self.prerequisites = {}  # quest_id -> [prerequisite_ids]
        self.player_progress = {}  # player -> set of completed quests
    
    # 📜 Add a quest
    def add_quest(self, quest_id, name, category, emoji, rewards):
        self.quests[quest_id] = {
            "name": name,
            "category": category,
            "emoji": emoji,
            "rewards": rewards
        }
        self.prerequisites[quest_id] = []
        print(f"{emoji} Added quest: {name}")
    
    # 🔗 Add prerequisite
    def add_prerequisite(self, quest_id, prereq_id):
        if quest_id in self.prerequisites:
            self.prerequisites[quest_id].append(prereq_id)
            print(f"📋 {quest_id} requires {prereq_id}")
    
    # 👤 Initialize player
    def add_player(self, player_name):
        self.player_progress[player_name] = set()
        print(f"🎮 {player_name} joined the game!")
    
    # ✅ Complete quest
    def complete_quest(self, player, quest_id):
        if player in self.player_progress and quest_id in self.quests:
            self.player_progress[player].add(quest_id)
            quest = self.quests[quest_id]
            print(f"🎉 {player} completed {quest['emoji']} {quest['name']}!")
            print(f"🎁 Rewards: {quest['rewards']}")
    
    # 🔍 Get available quests
    def get_available_quests(self, player):
        if player not in self.player_progress:
            return []
        
        completed = self.player_progress[player]
        available = []
        
        for quest_id, prereqs in self.prerequisites.items():
            if quest_id not in completed:
                if all(prereq in completed for prereq in prereqs):
                    available.append(quest_id)
        
        return available
    
    # 📊 Get completion percentage
    def get_completion_rate(self, player):
        if player not in self.player_progress:
            return 0
        
        completed = len(self.player_progress[player])
        total = len(self.quests)
        return (completed / total * 100) if total > 0 else 0
    
    # 🔄 Check for circular dependencies
    def has_circular_dependency(self):
        visited = set()
        rec_stack = set()
        
        def dfs(quest):
            visited.add(quest)
            rec_stack.add(quest)
            
            for prereq in self.prerequisites.get(quest, []):
                if prereq not in visited:
                    if dfs(prereq):
                        return True
                elif prereq in rec_stack:
                    return True
            
            rec_stack.remove(quest)
            return False
        
        for quest in self.prerequisites:
            if quest not in visited:
                if dfs(quest):
                    return True
        return False

# 🎮 Test it out!
game = QuestSystem()

# Add quests
game.add_quest("Q1", "The Beginning", "main", "🏁", {"xp": 100, "gold": 50})
game.add_quest("Q2", "Find the Sword", "main", "⚔️", {"xp": 200, "item": "Iron Sword"})
game.add_quest("Q3", "Defeat the Dragon", "main", "🐉", {"xp": 1000, "gold": 500})
game.add_quest("Q4", "Collect Herbs", "side", "🌿", {"xp": 50, "item": "Healing Potion"})
game.add_quest("Q5", "Master the Blade", "main", "🗡️", {"xp": 500, "skill": "Sword Mastery"})

# Add prerequisites
game.add_prerequisite("Q2", "Q1")  # Need to complete Q1 before Q2
game.add_prerequisite("Q3", "Q2")  # Need sword before fighting dragon
game.add_prerequisite("Q3", "Q5")  # Need sword mastery too
game.add_prerequisite("Q5", "Q2")  # Need sword to master it

# Play the game!
game.add_player("Hero")
print(f"\n📋 Available quests: {game.get_available_quests('Hero')}")

game.complete_quest("Hero", "Q1")
print(f"\n📋 Available quests: {game.get_available_quests('Hero')}")

game.complete_quest("Hero", "Q4")
game.complete_quest("Hero", "Q2")
print(f"\n📋 Available quests: {game.get_available_quests('Hero')}")

print(f"\n📊 Completion: {game.get_completion_rate('Hero'):.1f}%")
print(f"🔄 Has circular dependency? {game.has_circular_dependency()}")

🎓 Key Takeaways

You’ve learned so much! Here’s what you can now do:

• ✅ Create adjacency lists with confidence 💪
• ✅ Implement graph algorithms like BFS and DFS 🛡️
• ✅ Build real-world applications using graphs 🎯
• ✅ Avoid common graph pitfalls like a pro 🐛
• ✅ Design efficient graph-based systems with Python! 🚀

Remember: Graphs are everywhere - social networks, maps, dependencies, and more. Adjacency lists are your swiss army knife for handling them efficiently! 🤝

🤝 Next Steps

Congratulations! 🎉 You’ve mastered adjacency lists for graph representation!

Here’s what to do next:

1. 💻 Practice with the quest system exercise above
2. 🏗️ Build a small project using graphs (maybe a friend recommendation system?)
3. 📚 Move on to our next tutorial: Graph Algorithms - Depth-First Search
4. 🌟 Explore weighted graphs and shortest path algorithms!

Remember: Every graph expert started with simple adjacency lists. Keep coding, keep learning, and most importantly, have fun with graphs! 🚀

Happy coding! 🎉🚀✨