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. Directed Graph vs. Undirected 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.

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. Weighted Graph vs. Unweighted 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.

3. Simple Graph vs. Non-simple Graph

A simple graph is a graph that has no self-loops and no multiple edges between the same pair of vertices. This means that for any two vertices A and B, there can be at most one edge connecting them, and there are no edges like (A, A) that connect a vertex to itself. Most graph problems in computer science assume simple graphs by default.
A non-simple graph (also known as a multigraph or pseudograph) allows self-loops and/or multiple edges between the same pair of vertices. These graphs are useful in modeling real-world systems where multiple relationships or connections can exist between entities, such as transportation networks with multiple routes between two cities.

4. Sparse Graph vs. Dense Graph

A sparse graph is a graph in which the number of edges is much less than the maximum possible number of edges. For an undirected simple graph with n vertices, the maximum number of edges is n(n−1)/2. If the actual number of edges is closer to O(n), the graph is considered sparse. Sparse graphs are common in real-world data, such as social networks or web graphs, where each node connects to only a small fraction of all other nodes.

A dense graph, on the other hand, is one where the number of edges is close to the maximum possible. That means most pairs of vertices are connected by an edge. In complexity analysis, dense graphs often have O(n^2) edges. Dense graphs are common in complete networks, where every node is connected to almost every other node.

5. Other Types of Graphs

Cyclic Graph vs. Acyclic Graph An acyclic graph does not contain any cycles. Trees are connected acyclic undirected graphs. Directed acyclic graphs are called DAGs. They arise naturally in scheduling problems, where a directed edge (x, y) indicates that x must occur before y.

The degree of a vertex is the number of edges adjacent to it.

Data Structures for graphs

Adjacency Matrix Adjacency Lists