Graphs in DSA: Vertices, Edges & Core Terminology

A graph is a set of vertices (also called nodes) connected by edges (links between pairs of vertices). Graphs model anything built from relationships: road maps, social networks, web pages and their links, task dependencies, or routes between airports. This page defines the vocabulary you’ll use across every other graph page in this course.

Vertices and edges

Formally a graph is written G = (V, E) where V is the set of vertices and E is the set of edges. An edge connects two vertices u and v. If you can store anything as a vertex and any pair as an edge, you can model it as a graph.

// 4 vertices (0..3), edges listed as pairs
int V = 4;
std::vector<std::pair<int,int>> edges = {{0,1}, {0,2}, {1,3}};

// 4 vertices (0..3), edges listed as pairs
int V = 4;
int[][] edges = {{0,1}, {0,2}, {1,3}};

// 4 vertices (0..3), edges listed as pairs
const V = 4;
const edges = [[0,1], [0,2], [1,3]];

# 4 vertices (0..3), edges listed as pairs
V = 4
edges = [(0, 1), (0, 2), (1, 3)]

Directed vs undirected

• In an undirected graph an edge {u, v} goes both ways — if you can walk from u to v, you can walk back. Friendships are undirected.
• In a directed graph (or digraph) an edge (u, v) is one-way — u → v does not imply v → u. Twitter “follows” and web links are directed.

For beginners: A handy mental rule — undirected edges are roads, directed edges are one-way streets.

Weighted vs unweighted

An edge can carry a weight — a number meaning distance, cost, time, or capacity. A graph with weights is weighted; without them it is unweighted (every edge counts as 1). Shortest-path algorithms like Dijkstra and Bellman-Ford operate on weighted graphs.

// weighted edge: (from, to, weight)
std::vector<std::array<int,3>> wedges = {{0,1,5}, {0,2,3}, {1,3,2}};

// weighted edge: {from, to, weight}
int[][] wedges = {{0,1,5}, {0,2,3}, {1,3,2}};

// weighted edge: [from, to, weight]
const wedges = [[0,1,5], [0,2,3], [1,3,2]];

# weighted edge: (from, to, weight)
wedges = [(0, 1, 5), (0, 2, 3), (1, 3, 2)]

Terminology you must know

• Adjacent / neighbor: two vertices joined by an edge.
• Degree: number of edges touching a vertex. In a directed graph this splits into in-degree (edges coming in) and out-degree (edges going out).
• Path: a sequence of vertices each connected to the next by an edge.
• Cycle: a path that starts and ends at the same vertex without repeating edges. A graph with no cycle is acyclic.
• Connected: an undirected graph is connected if there’s a path between every pair of vertices. (See connected components.)
• DAG: a Directed Acyclic Graph — a directed graph with no cycles, the foundation of topological sort.
• Dense vs sparse: a graph with edges close to V² is dense; one with far fewer (closer to V) is sparse. This choice drives how you represent the graph.
• Tree: a connected, acyclic, undirected graph with exactly V - 1 edges — a special kind of graph (see trees).

How dense is “dense”?

The maximum number of edges tells you whether to expect a big or small graph:

Undirected, no self-loops:  up to V·(V-1)/2 edges
Directed, no self-loops:    up to V·(V-1) edges

A graph near these limits is dense; one with O(V) edges is sparse. You’ll reach for an adjacency matrix for dense graphs and an adjacency list for sparse ones.

Where to go next

Now that you have the vocabulary, learn how to actually store a graph in memory on graph representations, then explore it with BFS and DFS. When you’re ready, try the graph exercises.