Graph Data Structure Explained with Examples

A graph is the data structure that scares students the most. It sounds abstract and mathematical. But you already use graphs every single day without thinking about it.

Google Maps is a graph. Your Instagram follows are a graph. The web itself is a graph. Once you see that, the fear drops away and the real question becomes simple. How do you store all those connections in code? Let me show you.

What is a graph data structure?

A graph is a set of points with connections between them. The points are called nodes, or sometimes vertices. The connections are called edges. That is the whole idea.

Picture four cities on a map. Each city is a node. Each road between two cities is an edge. The graph is just the cities plus the roads that join them. Nothing more complicated than that.

This makes a graph the most flexible structure you will learn. An array lines items up in a row. A graph lets any item connect to any other item, in any pattern you want. That freedom is why graphs model so much of the real world. They are a key topic in any DSA learning path.

Types of graphs

Graphs come in a few flavours, and the difference matters. The first split is direction. In an undirected graph, an edge goes both ways, like a two way road or a mutual friendship on Facebook. In a directed graph, an edge points one way, like a one way street or a follow on Twitter where you follow someone who does not follow back.

The second split is weight. In an unweighted graph, every edge is the same. In a weighted graph, each edge carries a number, like the distance between two cities or the cost of a flight. Maps use weighted graphs so they can find not just any route, but the shortest one.

How is a graph stored?

Here is the part that actually matters in code. A graph is an idea, but the computer needs a concrete way to hold it. There are two main ways, and picking the right one is a real skill.

Let’s use one small graph for both. It has four nodes numbered 0, 1, 2 and 3. The edges are 0 to 1, 0 to 2, 1 to 2, and 2 to 3. It is undirected, so every edge works both ways.

The first way is an adjacency list. For each node, you keep a list of its neighbours. It reads almost like plain English.

0 -> 1, 2
1 -> 0, 2
2 -> 0, 1, 3
3 -> 2

Node 2 connects to three others, so its list is the longest. Node 3 connects to only one, so its list is short. The list only stores connections that actually exist, which will matter in a moment.

The second way is an adjacency matrix. You make a grid with one row and one column per node. A cell holds a 1 if those two nodes share an edge, and a 0 if they do not.

The green cells are the edges. Notice the grid is symmetric across the diagonal, because the graph is undirected. If 0 connects to 2, then 2 connects to 0, so both cells show a 1.

Graph code in Python and C++

The adjacency list is the version you will use most, so let’s build it. In Python, a dictionary of lists does the job cleanly.

class Graph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v):
        self.adj.setdefault(u, []).append(v)
        self.adj.setdefault(v, []).append(u)

    def neighbors(self, node):
        return self.adj.get(node, [])

The add_edge method adds the link in both directions, because the graph is undirected. Drop the second line if you want a directed graph. Here is the same adjacency list in C++, the language most Indian placement tests expect.

#include <vector>
using namespace std;

vector<int> adj[4];   // one list per node

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

Both versions store only the edges that exist. To find a node’s neighbours, you read its list directly. That is all a graph needs to be useful.

What is the space complexity of a graph?

The two storage methods have very different costs, and this is the heart of the choice. Call the number of nodes n and the number of edges e.

An adjacency list uses O(n + e) space. It stores each node once and each edge once, and nothing else. An adjacency matrix uses O(n squared) space, because it reserves a cell for every possible pair of nodes, even pairs that never connect. For our four node graph that is 16 cells no matter how few edges exist.

So the list wins on space for sparse graphs, which is most real graphs. The matrix wins on speed for one job. Checking whether two nodes share an edge takes O(1) in a matrix, but takes O(degree) in a list, since you scan that node’s neighbours. You can read the formal definitions on Wikipedia’s graph page.

Where are graphs used in real programs?

Graphs are everywhere once you start looking. The maps app on your phone treats every junction as a node and every road as a weighted edge, then finds the shortest path across them. That is a graph problem at heart.

Social networks store people as nodes and friendships as edges. The feature that suggests people you may know is a graph walking your friends’ friends. The web is a giant graph too, with pages as nodes and links as edges, which is how search engines crawl it. To actually move through a graph, you use a search like breadth first search or depth first search, and depth first search leans on a stack to remember where to go next.

FAQ

What is the difference between a node and an edge?

A node is a single point in the graph, like a city or a person. An edge is a connection between two nodes, like a road or a friendship. A graph is just nodes plus edges.

What is the difference between an adjacency list and an adjacency matrix?

An adjacency list stores, for each node, the neighbours it connects to. An adjacency matrix is a grid that marks every pair of nodes as connected or not. The list saves space, the matrix gives faster edge checks.

When should I use an adjacency list?

Use a list when the graph is sparse, meaning it has far fewer edges than the maximum possible. Most real graphs are sparse, so the list is the common choice.

What is the difference between a directed and undirected graph?

In an undirected graph, edges work both ways, like a mutual friendship. In a directed graph, edges point one way, like a follow that is not returned.

What is a weighted graph?

A weighted graph gives each edge a number, such as distance or cost. Maps use weights so they can find the shortest or cheapest route, not just any route.

Are trees a type of graph?

Yes. A tree is a special graph that is connected and has no cycles. Every tree is a graph, but not every graph is a tree.

So what should you remember?

A graph is just nodes joined by edges, and it models almost any set of connections you can name. The real skill is storage. Use an adjacency list for sparse graphs to save space, and an adjacency matrix when you need instant edge checks on a small or dense graph.

Get that choice right and the hard graph algorithms have a solid base to stand on. Get it wrong and you waste memory you did not need to.

Now try it. Add an edge between node 1 and node 3. What changes in the adjacency list, and which two cells in the matrix flip to 1?