Tag: Beginner

If you’ve ever used Google Maps, browsed a social network, or watched a package get routed across the internet — you’ve already interacted with a graph without knowing it. Graphs are one of the most powerful and widely-used data structures in computer science, and understanding them will level up the way you think about problems.

In this first post of a three-part series, we’ll cover everything you need to get started: what graphs are, the vocabulary you’ll need to know, and how to represent them in code.

---

What Is a Graph?

A graph is a collection of two things:

• Vertices (also called nodes) — the “things” in your model (cities, people, web pages)
• Edges — the connections between them (roads, friendships, links)

That’s it. Any problem that can be expressed as objects with relationships can be modeled as a graph.

Real-World Examples

Graph	Vertices	Edges
Road network	Cities	Roads
Social network	People	Friendships
The internet	Web pages	Hyperlinks
Course catalog	Courses	Prerequisites
Computer network	Servers	Cables / connections

---

Types of Graphs

Not all graphs are built the same. Here are the four key variations you’ll encounter:

Undirected vs. Directed

In an undirected graph, edges have no direction — if A is connected to B, then B is also connected to A. Think friendships on Facebook: if you’re friends with someone, they’re friends with you too.

In a directed graph (also called a digraph), edges point one way. Following someone on Twitter is directed — you can follow someone without them following you back.

Unweighted vs. Weighted

In an unweighted graph, all edges are equal. There’s no “cost” to travel along one edge vs. another.

In a weighted graph, each edge carries a value — a distance, cost, or time. Road networks are weighted: the road from city A to city B might be 200 km, while A to C is only 50 km.

---

Key Terminology

Before we write any code, here’s the vocabulary you need to know:

Degree — the number of edges connected to a node.

• In undirected graphs, a node’s degree is simply how many neighbors it has.
• In directed graphs, this splits into in-degree (edges coming in) and out-degree (edges going out).

Path — a sequence of vertices connected by edges.

Cycle — a path that starts and ends at the same vertex.

Connected graph — every vertex can be reached from every other vertex.

---

How to Represent a Graph in Code

There are two standard approaches, and your choice affects the performance of every algorithm you run on it.

Option 1: Adjacency List

Store a list of neighbors for each vertex. In C++, this is typically an unordered_map (or array) where each key is a node and the value is a vector of its neighbors.

// graph[node] = list of neighbors
unordered_map<int, vector<int>> graph;

graph[0] = {1, 2};    // node 0 connects to 1 and 2
graph[1] = {3};       // node 1 connects to 3
graph[2] = {3};       // node 2 connects to 3
graph[3] = {};        // node 3 has no outgoing edges

Memory-efficient for sparse graphs (few edges)
Fast to iterate over a node's neighbors 
Slower to check if a specific edge exists: O(degree)

Option 2: Adjacency Matrix

An n×n grid where matrix[u][v] = 1 (or the edge weight) if there’s an edge from u to v, and 0 otherwise.

int n = 4;
vector<vector<int>> matrix(n, vector<int>(n, 0));

matrix[0][1] = 1;   // edge from 0 to 1
matrix[0][2] = 1;   // edge from 0 to 2
matrix[1][3] = 1;
matrix[2][3] = 1;

O(1) edge lookup 
Simple to implement 
Uses O(V²) memory — wasteful for sparse graphs

Which One Should You Use?

Use an adjacency list for most problems — real-world graphs tend to be sparse (not every city is connected to every other city). Use a matrix when the graph is dense or when you need constant-time edge checks.

Wrapping Up

You now have a solid foundation:

• A graph is vertices + edges, used to model connected relationships
• Graphs can be directed or undirected, weighted or unweighted
• Adjacency lists are your default representation; matrices when the graph is dense
• The vocabulary (degree, cycle, path) you’ll see in every algorithm explanation

In Part 2, we’ll put this foundation to work by implementing the two fundamental graph traversal algorithms — Breadth-First Search (BFS) and Depth-First Search (DFS) — with step-by-step walkthroughs and code.

---