Graph

A graph represents objects and relationships between them. The objects are vertices, and the relationships are edges.

Graphs are useful because many problems are really about reachability, connection, dependency, movement, or cost between things.

Core Idea

A graph does not have to look like a road map. A graph can represent people connected by friendships, tasks connected by prerequisites, web pages connected by links, or states connected by possible moves.

Once a problem is modeled as a graph, graph algorithms can answer questions about traversal, shortest paths, components, cycles, and ordering.

The hardest beginner step is often recognizing the graph. The problem statement may not use the word “graph.” It may talk about transformations, jumps, prerequisites, rooms, dependencies, or allowed moves. If things can be connected or moved between, a graph may be hiding inside the problem.

Usage Contract

A graph model needs two decisions before code starts: what counts as a vertex, and what counts as an edge.

In the grid-neighbor example, row and col identify the current cell, while rows and cols define the valid grid boundary. The function yields only neighboring cells that stay inside the grid.

Python Example

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

This dictionary represents each vertex with the vertices connected to it.

Modeling a Problem as a Graph

To build a graph model, ask two questions.

First, what is a vertex? It might be a city, a course, a word, a grid cell, a user, or a state of a puzzle.

Second, what is an edge? It might be a road, a prerequisite relation, a one-letter word transformation, a legal move, or a dependency.

For a grid, each cell can be a vertex:

def neighbors(row, col, rows, cols):
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr = row + dr
        nc = col + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

The graph does not need to be stored explicitly if neighbors can be generated when needed.

Main Questions Graphs Answer

Graph algorithms often answer one of these questions:

• Can one vertex reach another?
• What is the shortest path?
• How many connected groups exist?
• Does a cycle exist?
• What order satisfies all dependencies?
• What is the cheapest way to connect everything?

The right algorithm depends on the question and on graph properties such as direction, weights, and cycles.

Common Confusions

A graph is a model, not only a drawing. The same graph can be stored as a dictionary, a list of edges, an adjacency matrix, or another representation.

A tree is a special kind of graph. Not every graph is a tree because graphs may have cycles, disconnected parts, or arbitrary relationships.

Another common mistake is choosing vertices too coarsely. If future choices depend on extra information, that information may need to be part of the state. For example, (row, col, keys) may be the graph vertex in a maze with keys, not just (row, col).

When To Use It

Use graph thinking when the problem involves relationships, movement from one state to another, dependencies, networks, connected groups, or paths.

If the problem can be described as “from this thing, what other things can I go to?”, graph thinking is usually worth trying.

The Main Point

A graph is a model of objects and allowed relationships. The algorithm becomes clearer when the vertex meaning and edge meaning are explicit.