Graphs (Data Structure Perspective)

Introduction

Graphs are one of the most versatile and important data structures in computer science. They model relationships and connections between entities, from social networks to road maps to computer networks. This chapter focuses on implementing and representing graphs; algorithms are covered in the next module.

Learning Objectives

By the end of this reading, you will be able to:

• Implement graphs using adjacency lists and matrices
• Choose appropriate representations for different scenarios
• Perform basic graph operations
• Understand weighted and directed graphs

1. Graph Refresher

A graph G = (V, E) consists of:

• V: Set of vertices (nodes)
• E: Set of edges (connections between vertices)

Types of Graphs

Directed vs Undirected

Undirected:        Directed:
  A --- B          A → B
  |     |          ↓   ↓
  C --- D          C ← D

Weighted vs Unweighted

Weighted:          Unweighted:
  A -5- B          A --- B
  |     |          |     |
  3     2          |     |
  |     |          |     |
  C -4- D          C --- D

2. Adjacency List Representation

Each vertex stores a list of its neighbors. Most efficient for sparse graphs.

Basic Implementation

class Graph:
    def __init__(self, directed=False):
        self.adj = {}  # vertex -> list of neighbors
        self.directed = directed

    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = []

    def add_edge(self, u, v):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

    def remove_edge(self, u, v):
        if u in self.adj:
            self.adj[u] = [x for x in self.adj[u] if x != v]
        if not self.directed and v in self.adj:
            self.adj[v] = [x for x in self.adj[v] if x != u]

    def remove_vertex(self, v):
        # Remove all edges to v
        for u in self.adj:
            self.adj[u] = [x for x in self.adj[u] if x != v]
        # Remove v
        if v in self.adj:
            del self.adj[v]

    def has_edge(self, u, v):
        return u in self.adj and v in self.adj[u]

    def neighbors(self, v):
        return self.adj.get(v, [])

    def vertices(self):
        return list(self.adj.keys())

    def degree(self, v):
        return len(self.adj.get(v, []))

    def num_vertices(self):
        return len(self.adj)

    def num_edges(self):
        total = sum(len(neighbors) for neighbors in self.adj.values())
        return total if self.directed else total // 2

    def __str__(self):
        result = []
        for v in self.adj:
            result.append(f"{v}: {self.adj[v]}")
        return '\n'.join(result)

Usage

g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'C')
g.add_edge('C', 'D')

print(g)
# A: ['B', 'C']
# B: ['A', 'C']
# C: ['A', 'B', 'D']
# D: ['C']

print(g.neighbors('A'))  # ['B', 'C']
print(g.degree('C'))     # 3
print(g.has_edge('A', 'B'))  # True

3. Weighted Graph with Adjacency List

class WeightedGraph:
    def __init__(self, directed=False):
        self.adj = {}
        self.directed = directed

    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = {}

    def add_edge(self, u, v, weight=1):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u][v] = weight
        if not self.directed:
            self.adj[v][u] = weight

    def get_weight(self, u, v):
        if u in self.adj and v in self.adj[u]:
            return self.adj[u][v]
        return float('inf')

    def neighbors(self, v):
        return list(self.adj.get(v, {}).keys())

    def neighbors_with_weights(self, v):
        return list(self.adj.get(v, {}).items())

    def edges(self):
        """Return all edges as (u, v, weight) tuples"""
        result = []
        seen = set()
        for u in self.adj:
            for v, w in self.adj[u].items():
                if self.directed or (v, u) not in seen:
                    result.append((u, v, w))
                    seen.add((u, v))
        return result

Usage

g = WeightedGraph()
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 3)
g.add_edge('B', 'C', 2)

print(g.get_weight('A', 'B'))  # 5
print(g.neighbors_with_weights('A'))  # [('B', 5), ('C', 3)]
print(g.edges())  # [('A', 'B', 5), ('A', 'C', 3), ('B', 'C', 2)]

4. Adjacency Matrix Representation

A 2D matrix where entry [i][j] indicates an edge from vertex i to j.

class GraphMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
        self.vertex_map = {}  # vertex -> index
        self.index_map = {}   # index -> vertex

    def add_vertex(self, v):
        if v not in self.vertex_map:
            idx = len(self.vertex_map)
            if idx >= self.num_vertices:
                raise ValueError("Graph is full")
            self.vertex_map[v] = idx
            self.index_map[idx] = v

    def add_edge(self, u, v, weight=1, directed=False):
        self.add_vertex(u)
        self.add_vertex(v)
        i, j = self.vertex_map[u], self.vertex_map[v]
        self.matrix[i][j] = weight
        if not directed:
            self.matrix[j][i] = weight

    def has_edge(self, u, v):
        i, j = self.vertex_map.get(u), self.vertex_map.get(v)
        if i is None or j is None:
            return False
        return self.matrix[i][j] != 0

    def get_weight(self, u, v):
        i, j = self.vertex_map[u], self.vertex_map[v]
        return self.matrix[i][j]

    def neighbors(self, v):
        i = self.vertex_map[v]
        return [self.index_map[j] for j in range(self.num_vertices)
                if self.matrix[i][j] != 0]

    def degree(self, v):
        i = self.vertex_map[v]
        return sum(1 for j in range(self.num_vertices) if self.matrix[i][j] != 0)

    def print_matrix(self):
        print("   ", " ".join(str(self.index_map.get(i, i)) for i in range(self.num_vertices)))
        for i in range(self.num_vertices):
            v = self.index_map.get(i, i)
            print(f"{v}: {self.matrix[i]}")

Comparison

5. Edge List Representation

Simply a list of edges. Simple but less efficient for neighbor queries.

class EdgeListGraph:
    def __init__(self, directed=False):
        self.edges = []
        self.directed = directed

    def add_edge(self, u, v, weight=1):
        self.edges.append((u, v, weight))
        if not self.directed:
            self.edges.append((v, u, weight))

    def neighbors(self, v):
        return [e[1] for e in self.edges if e[0] == v]

    def vertices(self):
        vertices = set()
        for u, v, _ in self.edges:
            vertices.add(u)
            vertices.add(v)
        return list(vertices)

Use case: Kruskal's algorithm (sort edges by weight)

6. Common Graph Operations

Graph Conversion

def adj_list_to_matrix(adj_list):
    """Convert adjacency list to matrix"""
    vertices = list(adj_list.keys())
    n = len(vertices)
    v_to_idx = {v: i for i, v in enumerate(vertices)}

    matrix = [[0] * n for _ in range(n)]
    for u in adj_list:
        for v in adj_list[u]:
            matrix[v_to_idx[u]][v_to_idx[v]] = 1

    return matrix, vertices

def matrix_to_adj_list(matrix, vertices=None):
    """Convert matrix to adjacency list"""
    n = len(matrix)
    if vertices is None:
        vertices = list(range(n))

    adj_list = {v: [] for v in vertices}
    for i in range(n):
        for j in range(n):
            if matrix[i][j] != 0:
                adj_list[vertices[i]].append(vertices[j])

    return adj_list

Transpose of Directed Graph

def transpose(graph):
    """Reverse all edges in a directed graph"""
    transposed = Graph(directed=True)
    for v in graph.adj:
        transposed.add_vertex(v)
    for u in graph.adj:
        for v in graph.adj[u]:
            transposed.add_edge(v, u)
    return transposed

Check if Graph is Connected

def is_connected(graph):
    """Check if undirected graph is connected"""
    if not graph.adj:
        return True

    start = next(iter(graph.adj))
    visited = set()
    stack = [start]

    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            stack.extend(graph.neighbors(v))

    return len(visited) == len(graph.adj)

Find All Connected Components

def connected_components(graph):
    """Find all connected components in undirected graph"""
    visited = set()
    components = []

    def dfs(v, component):
        visited.add(v)
        component.append(v)
        for neighbor in graph.neighbors(v):
            if neighbor not in visited:
                dfs(neighbor, component)

    for v in graph.vertices():
        if v not in visited:
            component = []
            dfs(v, component)
            components.append(component)

    return components

Check for Cycle

def has_cycle_undirected(graph):
    """Check for cycle in undirected graph"""
    visited = set()

    def dfs(v, parent):
        visited.add(v)
        for neighbor in graph.neighbors(v):
            if neighbor not in visited:
                if dfs(neighbor, v):
                    return True
            elif neighbor != parent:
                return True
        return False

    for v in graph.vertices():
        if v not in visited:
            if dfs(v, None):
                return True
    return False


def has_cycle_directed(graph):
    """Check for cycle in directed graph"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph.vertices()}

    def dfs(v):
        color[v] = GRAY
        for neighbor in graph.neighbors(v):
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[v] = BLACK
        return False

    for v in graph.vertices():
        if color[v] == WHITE:
            if dfs(v):
                return True
    return False

7. Special Graph Types

Bipartite Graph

def is_bipartite(graph):
    """Check if graph can be 2-colored"""
    color = {}

    def bfs(start):
        queue = [start]
        color[start] = 0

        while queue:
            v = queue.pop(0)
            for neighbor in graph.neighbors(v):
                if neighbor not in color:
                    color[neighbor] = 1 - color[v]
                    queue.append(neighbor)
                elif color[neighbor] == color[v]:
                    return False
        return True

    for v in graph.vertices():
        if v not in color:
            if not bfs(v):
                return False
    return True

Complete Graph Generator

def complete_graph(n):
    """Create complete graph K_n"""
    g = Graph()
    vertices = list(range(n))
    for i in range(n):
        for j in range(i + 1, n):
            g.add_edge(i, j)
    return g

Grid Graph

def grid_graph(rows, cols):
    """Create 2D grid graph"""
    g = Graph()

    def vertex(r, c):
        return (r, c)

    for r in range(rows):
        for c in range(cols):
            if c + 1 < cols:
                g.add_edge(vertex(r, c), vertex(r, c + 1))
            if r + 1 < rows:
                g.add_edge(vertex(r, c), vertex(r + 1, c))

    return g

8. Graph Traversal Preview

Depth-First Search (DFS)

def dfs(graph, start):
    """Visit all reachable vertices depth-first"""
    visited = set()
    result = []

    def explore(v):
        visited.add(v)
        result.append(v)
        for neighbor in graph.neighbors(v):
            if neighbor not in visited:
                explore(neighbor)

    explore(start)
    return result

Breadth-First Search (BFS)

from collections import deque

def bfs(graph, start):
    """Visit all reachable vertices breadth-first"""
    visited = {start}
    queue = deque([start])
    result = []

    while queue:
        v = queue.popleft()
        result.append(v)
        for neighbor in graph.neighbors(v):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result

Full coverage of graph algorithms in the Algorithms module.

9. Practical Applications

Social Network

class SocialNetwork(Graph):
    def __init__(self):
        super().__init__(directed=False)
        self.user_data = {}

    def add_user(self, user_id, name):
        self.add_vertex(user_id)
        self.user_data[user_id] = {'name': name}

    def add_friendship(self, user1, user2):
        self.add_edge(user1, user2)

    def get_friends(self, user_id):
        return self.neighbors(user_id)

    def mutual_friends(self, user1, user2):
        friends1 = set(self.neighbors(user1))
        friends2 = set(self.neighbors(user2))
        return friends1 & friends2

    def friend_suggestions(self, user_id, limit=5):
        """Suggest friends of friends"""
        friends = set(self.neighbors(user_id))
        suggestions = {}

        for friend in friends:
            for fof in self.neighbors(friend):
                if fof != user_id and fof not in friends:
                    suggestions[fof] = suggestions.get(fof, 0) + 1

        # Sort by number of mutual connections
        sorted_suggestions = sorted(suggestions.items(),
                                   key=lambda x: x[1], reverse=True)
        return [user for user, _ in sorted_suggestions[:limit]]

Dependency Graph

class DependencyGraph(Graph):
    def __init__(self):
        super().__init__(directed=True)

    def add_dependency(self, dependent, dependency):
        """dependent depends on dependency"""
        self.add_edge(dependent, dependency)

    def get_dependencies(self, item):
        """Direct dependencies"""
        return self.neighbors(item)

    def get_all_dependencies(self, item):
        """All transitive dependencies"""
        all_deps = set()
        stack = [item]

        while stack:
            current = stack.pop()
            for dep in self.neighbors(current):
                if dep not in all_deps:
                    all_deps.add(dep)
                    stack.append(dep)

        return all_deps

    def topological_sort(self):
        """Return items in dependency order"""
        in_degree = {v: 0 for v in self.adj}
        for v in self.adj:
            for neighbor in self.adj[v]:
                in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

        queue = deque([v for v in in_degree if in_degree[v] == 0])
        result = []

        while queue:
            v = queue.popleft()
            result.append(v)
            for neighbor in self.neighbors(v):
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        if len(result) != len(self.adj):
            raise ValueError("Circular dependency detected")

        return result[::-1]  # Reverse for dependency order

Exercises

Basic

1. Implement remove_vertex for the adjacency matrix representation.

2. Write a function to count the number of edges in an undirected graph.

3. Create a function to find all vertices with degree greater than k.

Intermediate

4. Implement a method to find the shortest path (number of edges) between two vertices using BFS.

5. Write a function to clone a graph (create a deep copy).

6. Implement a function to check if a directed graph is a DAG (Directed Acyclic Graph).

Advanced

7. Implement a function to find all bridges (edges whose removal disconnects the graph).

8. Create a function to find the strongly connected components of a directed graph.

9. Implement a graph data structure that efficiently supports both neighbor queries and edge existence checks.

Summary

• Graphs model relationships between entities
• Adjacency list: O(V + E) space, efficient for sparse graphs
• Adjacency matrix: O(V²) space, O(1) edge lookup, good for dense graphs
• Edge list: Simple, good for edge-focused algorithms
• Common operations: add/remove vertex/edge, find neighbors, check connectivity
• Graph types: directed/undirected, weighted/unweighted, bipartite, DAG
• Applications: social networks, dependency management, routing, scheduling

Next Module

Algorithm Analysis and Big O →