Skip to content

Graph Terminology & Representation

A graph \(G = (V, E)\) has vertices (nodes) and edges (links). Edges may be directed or undirected, and may carry weights (costs, lengths).

Common terms

Term Meaning
Degree Number of incident edges (in/out degree if directed).
Path Sequence of distinct vertices with consecutive edges.
Cycle Path that starts and ends at the same vertex.
Connected Undirected: every pair reachable. Strongly connected (directed): mutual reachability.
Tree Connected acyclic undirected graph; (
DAG Directed acyclic graph — enables topological order.

Adjacency list (typical in CP)

For each vertex u, store neighbors (and weights). Time/memory \(O(|V| + |E|)\).

#include <vector>
using namespace std;

// Unweighted directed: graph[u] = list of v
using Graph = vector<vector<int>>;

// Weighted: graph[u] = list of (v, weight)
using WGraph = vector<vector<pair<int, int>>>;

Adjacency matrix

adj[u][v] holds weight or 0/1 for presence. Simple for dense graphs; \(O(|V|^2)\) memory and slower for sparse graphs.

Input patterns

  • \(n, m\) then \(m\) edges — build adjacency list in one pass.
  • Grid as graph — cells are vertices; edges to 4 or 8 neighbors.