Graphs

Graphs are the most flexible and expressive data structure. They model relationships between entities — think social networks, road maps, web links, and dependency graphs.

Graph Terminology

• Vertex (node): a fundamental unit of the graph
• Edge: a connection between two vertices
• Directed graph (digraph): edges have a direction (A → B)
• Undirected graph: edges are bidirectional (A — B)
• Weighted graph: edges carry a numerical weight (cost, distance, etc.)
• Path: a sequence of vertices connected by edges
• Cycle: a path that starts and ends at the same vertex

Graph Representations

Adjacency Matrix

A 2D array where matrix[i][j] is 1 (or the edge weight) if there is an edge from vertex i to vertex j. Space: O(V²). Good for dense graphs.

class GraphMatrix:
    def __init__(self, num_vertices):
        self.n = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v, weight=1):
        self.matrix[u][v] = weight
        # For undirected:
        # self.matrix[v][u] = weight

    def has_edge(self, u, v):
        return self.matrix[u][v] != 0

Adjacency List

An array of lists where each vertex stores a list of its neighbors. Space: O(V + E). Good for sparse graphs.

class GraphList:
    def __init__(self, num_vertices):
        self.n = num_vertices
        self.adj = [[] for _ in range(num_vertices)]

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        # For undirected:
        # self.adj[v].append((u, weight))

    def get_neighbors(self, u):
        return self.adj[u]

Breadth-First Search (BFS)

Explores the graph level by level. Uses a queue. Finds the shortest path in unweighted graphs.

from collections import deque

def bfs(graph, start):
    visited = [False] * graph.n
    q = deque([start])
    visited[start] = True
    while q:
        v = q.popleft()
        print(v, end=" ")
        for neighbor, _ in graph.adj[v]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)

Depth-First Search (DFS)

Recursive DFS

def dfs_recursive(graph, v, visited):
    visited[v] = True
    print(v, end=" ")
    for neighbor, _ in graph.adj[v]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

Iterative DFS (using a stack)

def dfs_iterative(graph, start):
    visited = [False] * graph.n
    stack = [start]
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=" ")
            for neighbor, _ in reversed(graph.adj[v]):
                if not visited[neighbor]:
                    stack.append(neighbor)

Cycle Detection

For undirected graphs, use DFS and check if a neighbor is visited and is not the parent. For directed graphs, use a recursion stack to track nodes currently in the recursion path.

def has_cycle_directed(graph):
    visited = [False] * graph.n
    rec_stack = [False] * graph.n

    def dfs(v):
        visited[v] = True
        rec_stack[v] = True
        for neighbor, _ in graph.adj[v]:
            if not visited[neighbor]:
                if dfs(neighbor):
                    return True
            elif rec_stack[neighbor]:
                return True
        rec_stack[v] = False
        return False

    for v in range(graph.n):
        if not visited[v]:
            if dfs(v):
                return True
    return False

Topological Sort (DAG)

A topological ordering of a Directed Acyclic Graph (DAG) arranges vertices such that for every edge u → v, u comes before v. Used for task scheduling, build systems, and dependency resolution.

def topological_sort(graph):
    visited = [False] * graph.n
    stack = []

    def dfs(v):
        visited[v] = True
        for neighbor, _ in graph.adj[v]:
            if not visited[neighbor]:
                dfs(neighbor)
        stack.append(v)

    for v in range(graph.n):
        if not visited[v]:
            dfs(v)
    return stack[::-1]