Graphs & Hash Tables

Introduction

In the world of Data Structures and Algorithms (DSA), Graphs and Hash Tables are two of the most powerful and frequently used structures. They are essential for solving complex problems efficiently, from social network analysis to lightning-fast data retrieval.

In this tutorial, we will explore how to implement and utilize these two data structures natively in Python.

Hash Tables (Dictionaries)

A Hash Table is a data structure that maps keys to values using a hashing function, allowing for average $O(1)$ time complexity for lookups, insertions, and deletions.

In Python, the built-in dict (dictionary) type is essentially a highly-optimized hash table under the hood. You do not need to build your own hash table from scratch for daily programming, as Python's dict covers almost all use cases.

Using Python Dictionaries

Dictionaries store data in key-value pairs. Keys must be hashable (immutable types like strings, integers, or tuples), while values can be anything.

# Creating a hash table (dictionary)
student_grades = {
    "Alice": 95,
    "Bob": 82,
    "Charlie": 88
}

# 1. Fast Lookup - O(1)
print(f"Alice's grade: {student_grades['Alice']}")

# 2. Insertion / Update - O(1)
student_grades["David"] = 91
student_grades["Bob"] = 85  # Update existing key

# 3. Deletion - O(1)
del student_grades["Charlie"]

print("Final Hash Table:", student_grades)

Alice's grade: 95
Final Hash Table: {'Alice': 95, 'Bob': 85, 'David': 91}

Handling Missing Keys safely

If you try to access a key that does not exist using bracket notation, Python will throw a KeyError. To avoid this, use the .get() method.

grades = {"Alice": 95, "Bob": 82}

# Returns None if the key is not found
print("Charlie's grade:", grades.get("Charlie"))

# Returns a default value if the key is not found
print("Charlie's grade:", grades.get("Charlie", "Not Found!"))

Charlie's grade: None
Charlie's grade: Not Found!

Graphs

A Graph is a non-linear data structure consisting of vertices (nodes) and edges (connections between nodes). Graphs are used to represent networks, such as city maps, computer networks, and relationships on social media.

Graphs can be:

• Directed or Undirected: Whether edges have a specific direction.
• Weighted or Unweighted: Whether edges have a cost or distance associated with them.

Implementing a Graph in Python

The most common and efficient way to represent a graph in Python is using an Adjacency List. An adjacency list can be easily implemented using a Python dictionary, where each key is a vertex, and the value is a list of connected vertices.

class Graph:
    def __init__(self):
        # We use a dictionary to store the adjacency list
        self.adj_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    def add_edge(self, v1, v2):
        # Assuming an undirected graph
        if v1 in self.adj_list and v2 in self.adj_list:
            self.adj_list[v1].append(v2)
            self.adj_list[v2].append(v1)

    def print_graph(self):
        for vertex, edges in self.adj_list.items():
            print(f"{vertex} -> {edges}")

# Usage
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")

g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")

g.print_graph()

A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C']

Graph Traversal

Traversing a graph means visiting every node in a systematic way. There are two primary algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS)

BFS explores the graph level by level, moving outwards from a starting node. It relies on a Queue.

from collections import deque

def bfs(graph, start_vertex):
    visited = set()
    queue = deque([start_vertex])
    visited.add(start_vertex)
    
    result = []
    
    while queue:
        current_vertex = queue.popleft()
        result.append(current_vertex)
        
        for neighbor in graph[current_vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                
    return result

# Using the adjacency list we created earlier
graph_dict = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

print("BFS Traversal:", bfs(graph_dict, "A"))

BFS Traversal: ['A', 'B', 'C', 'D']

Depth-First Search (DFS)

DFS explores as far down a single branch as possible before backtracking. It relies on a Stack (often implemented via recursion).

def dfs(graph, start_vertex, visited=None):
    if visited is None:
        visited = set()
        
    visited.add(start_vertex)
    print(start_vertex, end=" ")
    
    for neighbor in graph[start_vertex]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

print("DFS Traversal: ", end="")
dfs(graph_dict, "A")

DFS Traversal: A B D C

What's Next?

Understanding Hash Tables gives you the foundation for writing optimized code, while Graphs unlock the ability to solve highly complex relational problems. Next, you can dive into advanced algorithmic concepts like Dijkstra's Algorithm for finding the shortest path in a weighted graph!