Graph Theory Basics

What is a Graph?

At its core, a graph is a mathematical structure used to model pairwise relations between objects. In pathfinding, it is the foundation for representing the environment.

A graph consists of two primary components:

• Vertices (Nodes): These represent distinct points or locations in space (e.g., a specific tile on a game board).
• Edges: These are the connections between nodes, representing the possibility of movement between them.
• Weights: These are numerical values assigned to edges, representing the "cost" of traveling across that specific connection.

Deep Dive: Graph Representations

While graphs are conceptually simple, how we represent them in memory matters significantly for performance. Two common ways to represent a graph are the Adjacency Matrix and the Adjacency List.

Adjacency Matrix

An adjacency matrix is a 2D array of size V x V, where V is the number of vertices. If there is an edge from vertex i to vertex j, the matrix[i][j] is set to 1 (or the weight of the edge). Otherwise, it is 0.

Pros: Quick lookup (O(1)) to check if an edge exists between two nodes.

Cons: Uses O(V²) space, which is inefficient for sparse graphs where most nodes have few connections.

Adjacency List

An adjacency list represents the graph as an array of lists. Each index in the array represents a vertex, and the list at that index contains all vertices connected to it.

Pros: More space-efficient (O(V + E)) for sparse graphs.

Cons: Slower to check if a specific edge exists (O(degree of V)).

Types of Graphs

Graphs are categorized based on their connectivity and properties:

• Directed vs. Undirected: In a directed graph, edges have a direction (one-way movement). In an undirected graph, edges are bidirectional.
• Weighted vs. Unweighted: Edges in weighted graphs have associated costs (e.g., travel time, fuel usage). Unweighted graphs treat all connections equally.
• Cyclic vs. Acyclic: A cyclic graph contains at least one cycle (path that starts and ends at the same node). Directed Acyclic Graphs (DAGs) are crucial for tasks like scheduling or dependency analysis.

Real-World Example: Navigational Complexity

Imagine navigating a city map. The city is a graph:

• Nodes = Intersections.
• Edges = Streets connecting them.
• Weights = Traffic-dependent time to travel that street.

An algorithm must navigate this efficiently. If you only move in one direction (one-way streets), the graph is directed. If traffic changes (e.g., peak hour), the weights of the edges change dynamically. This makes pathfinding in a real city much more complex than simple grid movement.

Grid-Based Graphs

For most pathfinding applications, we use a grid-based representation. This maps the environment into discrete cells, where each cell is a node.

Visualizing a simple grid:

┌─┬─┬─┬─┐
│S│ │ │ │  S = Start
├─┼─┼─┼─┤
│ │█│ │ │  █ = Obstacle
├─┼─┼─┼─┤
│ │ │ │E│  E = End
└─┴─┴─┴─┘

Movement Types

4-Directional Movement

Allows movement only vertically and horizontally. This is often called "Manhattan" movement.

8-Directional Movement

Allows movement vertically, horizontally, and diagonally. Diagonal movement typically has a higher cost (usually 1.414, which is the square root of 2).