LESSON 47/53Graphs

What a Graph Is

GOALPut nodes and edges into code as an adjacency list.

A graph is a set of nodes — cities, people, cells — and the links between them: roads, friendships. It is easy to picture and takes a moment to encode. The usual way: for each node, list who it connects to.

ON THIS PAGE

The example
Line by line
Watch it run
Two ways to store a graph
The graph hiding in the problem
Common mistakes
Key words
Quick check
Now you try

SHOW EXAMPLE IN

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);

    // undirected edges
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);

    for (int v = 0; v < n; v++) {
        cout << v << ":";
        for (int to : adj[v]) cout << " " << to;
        cout << endl;
    }
    return 0;
}

> what you see

Try this code

//LINE BY LINE

vector<vector<int>> adj(n);

One list per node. adj[3] holds the neighbours of node 3.

adj[0].push_back(1); adj[1].push_back(0);

An undirected edge is written on BOTH sides. Forgetting one is a very common bug.

for (int to : adj[v]) cout << " " << to;

Walk a node's neighbours. Nearly every graph algorithm starts like this.

cout << v << ":";

Node 4 prints empty — a node with no edges is perfectly legal.

Watch it run

There are five nodes. So far nothing joins any of them.

1 / 6

Two ways to store a graph

An adjacency LIST is the contest standard. An adjacency MATRIX is easier to write but will not fit in memory once there are many nodes.

	List	Matrix
Санах ой / Memory	цэг + холбоос / nodes + edges	цэг² / nodes²
«a–b холбоотой юу?» / "is a joined to b?"	Удаан / slow	Шууд / instant
Хөршүүдээр явах / Walking neighbours	Хурдан / fast	Бүх цэгийг шалгана / checks every node
10 000 цэг / 10 000 nodes	Асуудалгүй / fine	100 сая нүд — багтахгүй / 100 million cells — too big

When in doubt, use the list. Nearly every graph algorithm asks "the neighbours of this node", which is exactly what a list is for.

The graph hiding in the problem

A problem may never use the word "graph". If two things are CONNECTED to each other, it is one.

In the problem	Node	Edge
Хот, зам / Cities and roads	Хот / a city	Зам / a road
Найзууд / Friendships	Хүн / a person	Найз байх / being friends
Лабиринт / A maze	Нүд / a cell	Хажуугийн нүд рүү / a step to a neighbour
Хичээлийн дараалал / Course order	Хичээл / a course	Урьдчилсан нөхцөл / a prerequisite

Grid problems are graphs in disguise. Every cell is a node and every neighbour an edge — which is why BFS works on a grid unchanged.

//COMMON MISTAKES

✗ wrong

adj[a].push_back(b);

✓ right

adj[a].push_back(b); adj[b].push_back(a);

On an undirected graph, writing one side makes the road one-way. Searches then find only half of it.

✗ wrong

vector<vector<int>> adj; adj[0].push_back(1);

✓ right

vector<vector<int>> adj(n);

Without a size there is no adj[0] at all, and the program crashes.

//KEY WORDS

node (vertex)

One point in the graph.

edge

A link joining two nodes.

adjacency list

The structure listing each node's neighbours.

//QUICK CHECK

How do you record an undirected edge a—b?

//NOW YOU TRY

Read n nodes and m edges, then print the degree of each node — how many edges it has.

Open editor

DP on a Grid Depth-First Search

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 5;
    vector<vector<int>> adj(n);

    // undirected edges
    adj[0].push_back(1); adj[1].push_back(0);
    adj[0].push_back(2); adj[2].push_back(0);
    adj[1].push_back(3); adj[3].push_back(1);

    for (int v = 0; v < n; v++) {
        cout << v << ":";
        for (int to : adj[v]) cout << " " << to;
        cout << endl;
    }
    return 0;
}

> what you see

Try this code

//LINE BY LINE

vector<vector<int>> adj(n);

One list per node. adj[3] holds the neighbours of node 3.

adj[0].push_back(1); adj[1].push_back(0);

An undirected edge is written on BOTH sides. Forgetting one is a very common bug.

for (int to : adj[v]) cout << " " << to;

Walk a node's neighbours. Nearly every graph algorithm starts like this.

cout << v << ":";

Node 4 prints empty — a node with no edges is perfectly legal.

Two ways to store a graph

An adjacency LIST is the contest standard. An adjacency MATRIX is easier to write but will not fit in memory once there are many nodes.

	List	Matrix
Санах ой / Memory	цэг + холбоос / nodes + edges	цэг² / nodes²
«a–b холбоотой юу?» / "is a joined to b?"	Удаан / slow	Шууд / instant
Хөршүүдээр явах / Walking neighbours	Хурдан / fast	Бүх цэгийг шалгана / checks every node
10 000 цэг / 10 000 nodes	Асуудалгүй / fine	100 сая нүд — багтахгүй / 100 million cells — too big

When in doubt, use the list. Nearly every graph algorithm asks "the neighbours of this node", which is exactly what a list is for.

The graph hiding in the problem

A problem may never use the word "graph". If two things are CONNECTED to each other, it is one.

In the problem	Node	Edge
Хот, зам / Cities and roads	Хот / a city	Зам / a road
Найзууд / Friendships	Хүн / a person	Найз байх / being friends
Лабиринт / A maze	Нүд / a cell	Хажуугийн нүд рүү / a step to a neighbour
Хичээлийн дараалал / Course order	Хичээл / a course	Урьдчилсан нөхцөл / a prerequisite

Grid problems are graphs in disguise. Every cell is a node and every neighbour an edge — which is why BFS works on a grid unchanged.

//COMMON MISTAKES

✗ wrong

adj[a].push_back(b);

✓ right

adj[a].push_back(b); adj[b].push_back(a);

On an undirected graph, writing one side makes the road one-way. Searches then find only half of it.

✗ wrong

vector<vector<int>> adj; adj[0].push_back(1);

✓ right

vector<vector<int>> adj(n);

Without a size there is no adj[0] at all, and the program crashes.