A graph is a set of nodes connected by edges. Towns and roads, friends on a social network, the cells of a maze, tasks that depend on one another – all of these are graphs. In this lesson we get to know the basic terms and three ways of writing a graph in a program.
Before you start: prerequisites – vector in C++, matrices. How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.
Basic terms
1 ----- 2
| | \
| | 5
4 ----- 3
This graph has 5 nodes and 5 edges: 1–2, 1–4, 2–3, 2–5 and 3–4.
Term
Meaning
In the example
node (vertex)
an object we connect
1, 2, 3, 4, 5
edge
a connection between two nodes
1–2, 2–5, …
neighbours
nodes joined by an edge
the neighbours of node 2 are 1, 3 and 5
degree of a node
the number of edges that leave the node
the degree of node 2 is 3
path
a sequence of nodes in which neighbouring ones are connected by an edge
5 – 2 – 3 – 4
cycle
a path that returns to the starting node
1 – 2 – 3 – 4 – 1
connected graph
there is a path from every node to every other node
yes
Kinds of graphs:
undirected – an edge works in both directions (friendship, a two-way street);
directed – an edge u → v goes in only one direction (a one-way street, "task u must come before task v");
weighted – every edge has a number (a length, a price, a time).
In tasks a graph is almost always given like this: the first line contains the number of nodes n and the number of edges m, and then m lines follow, each with the two nodes that the edge joins (and a weight, if the graph is weighted).
The adjacency matrix
A matrix a of size n × n: a[u][v] = 1 if there is an edge between u and v, otherwise 0. For an undirected graph the matrix is symmetric.
#include <iostream>
using namespace std;
int a[101][101]; // the adjacency matrix, nodes 1..n (n <= 100)
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
a[u][v] = 1; // an undirected graph: the edge goes both ways
a[v][u] = 1;
}
// the degree of every node = the number of ones in its row
for (int u = 1; u <= n; u++) {
int degree = 0;
for (int v = 1; v <= n; v++) degree += a[u][v];
cout << "degree(" << u << ") = " << degree << endl;
}
return 0;
}
The check "are u and v connected by an edge" takes O(1), but the matrix takes n² memory – for n = 105 that is 1010 cells, which is impossible.
The adjacency list
For every node we keep a list of its neighbours – vector<int> graph[n + 1]. The memory is proportional to the number of edges, so this works even for a million nodes. This is the representation used in almost all algorithms on graphs (BFS, DFS, Dijkstra…).
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1); // graph[u] = the list of neighbours of the node u
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u); // for a directed graph this line is left out
}
for (int u = 1; u <= n; u++) {
cout << u << ":";
for (int v : graph[u]) cout << " " << v;
cout << endl;
}
return 0;
}
For the graph from the beginning of the lesson (input 5 5 / 1 2 / 1 4 / 2 3 / 2 5 / 3 4) the program prints:
1: 2 4
2: 1 3 5
3: 2 4
4: 1 3
5: 2
For a weighted graph we put pairs (neighbour, weight) into the list: vector<vector<pair<int,int>>> graph(n + 1); and graph[u].push_back({v, w});
The edge list
Sometimes it is enough just to store all the edges in one array. This is how Kruskal's(SR) and the Bellman-Ford(SR) algorithm work:
struct Edge {
int u, v, w; // the ends and the weight
};
vector<Edge> edges(m);
for (auto &e : edges) cin >> e.u >> e.v >> e.w;
Representation
Memory
Are u and v neighbours?
All the neighbours of u
When
adjacency matrix
n²
O(1)
O(n)
n ≤ a few thousand; Floyd-Warshall
adjacency list
n + m
O(degree of u)
O(degree of u)
almost always
edge list
m
O(m)
O(m)
Kruskal, Bellman-Ford
A matrix as a graph
A board or a maze is a graph even without writing down the edges: the cell (i, j) is a node, and its neighbours are the cells above, below, to the left and to the right. We visit the neighbours with arrays of moves:
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
int ni = i + di[k], nj = j + dj[k];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && board[ni][nj] != '#') {
// (ni, nj) is a neighbour of the cell (i, j)
}
}
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
TASK 01Difficulty: easy
The most popular user
On a social network with n users there are m follows: the line u v means that user u follows user v (a directed edge). Print the user followed by the most people and the number of followers; for an equal number – the smaller number.
Example
Input
4 5
1 2
3 2
4 2
2 1
4 1
Output
2 3
Hint
You do not need to keep the whole graph – an array inDegree[v] that counts the edges coming into v (the in-degree) is enough.
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> inDegree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
inDegree[v]++; // u follows v
}
int best = 1;
for (int v = 2; v <= n; v++)
if (inDegree[v] > inDegree[best]) best = v;
cout << best << " " << inDegree[best] << endl;
return 0;
}
TASK 02Difficulty: medium
Common friends
An undirected graph of friendships (n ≤ 1000) and q queries a b are given. For every query print how many common friends a and b have.
Example
Input
5 6
1 2
1 3
2 3
2 4
3 4
4 5
3
1 4
2 3
1 5
Output
2
2
0
Hint
Use both the list and the adjacency matrix: go through the neighbours of the node a (the list) and for each of them check in the matrix whether it is also a neighbour of the node b.
Solution (C++)
#include <iostream>
#include <vector>
using namespace std;
bool isNeighbour[1001][1001];
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
isNeighbour[u][v] = isNeighbour[v][u] = true;
}
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
int count = 0;
for (int x : graph[a]) // every friend of the person a
if (isNeighbour[x][b]) count++; // is it also a friend of the person b?
cout << count << endl;
}
return 0;
}
Common mistakes and tips
In tasks the nodes are usually numbered from 1 – make an array of size n + 1.
For an undirected graph add the edge in both directions; for a directed one only u → v.
For n larger than a few thousand do not use an adjacency matrix – the memory is n².
Check your knowledge
Open the quiz
Introduction to graphs
1. What is the degree of a node in an undirected graph?
2. Which representation is used for a graph with 10⁵ nodes and 2·10⁵ edges?
3. How much memory does the adjacency matrix of a graph with n nodes take?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.