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

Traversal

BFS DFS