Introduction

Have you ever thought about how Instagram knows who your mutual friends are or suggests people you might want to follow? Behind the scenes, platforms like Instagram, Facebook, and LinkedIn use a powerful data structure called a graph.

A graph is simply a way to represent relationships between things. In the case of Instagram, each user is a node, and a follow between two users is an edge. Whether it’s mapping your social network, analyzing flight routes, or finding the shortest path in a map app — graphs are everywhere.

In this post, we’ll dive into what graphs are, how they work, and how we can implement them in code. We'll cover essential concepts like nodes, edges, directed vs. undirected graphs, and popular algorithms like BFS and DFS.

Different types of graph

Graphs are defined as an ordered pair:

G = (V, E)

where V is a set of vertices (or nodes) and E is a set of edges that connect pairs of vertices. Graphs can be categorized based on their properties.

1. Undirected Graph

In an undirected graph, edges have no direction. Each edge is represented as an unordered pair (V, E). Whenever (A, B) ∈ E, there exists a connection between nodes A and B.

2. Directed Graph

In a directed graph, edges have a direction and are represented as ordered pairs (A, B). This means there is a connection from vertex A to vertex B, but not necessarily vice versa unless (B, A) is also in E.

3. Weighted Graph

A weighted graph is a triple (V, E, W). It assigns a weight or cost to each edge. This is often represented with a function W: E → R, where W(E) denotes the weight of edge E. In a weighted directed graph, the edge (A, B) may have a different weight than (B, A), if it exists at all.

Graph Representation

Graphs can be broadly categorized into dense and sparse types, depending on how many edges they contain relative to the number of nodes. A dense graph has edges between most pairs of nodes, meaning the number of edges approaches the maximum possible, which is n * (n − 1) / 2 for undirected graphs.

For example, a fully connected computer network where every server is linked to every other server is a dense graph. On the other hand, a sparse graph has relatively few edges, with most nodes connected to only a small number of others. Social networks like X are good examples of sparse graphs—most users follow only a handful of accounts, while only a few have millions of followers.

Understanding whether a graph is dense or sparse is important because it influences the choice of data structures: adjacency matrices are suited for dense graphs, while adjacency lists are ideal for sparse graphs due to their memory efficiency.