Introduction to Graphs: Terms and Representation

Lesson 1 of 17 · Graphs and trees

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.

TermMeaningIn the example
node (vertex)an object we connect1, 2, 3, 4, 5
edgea connection between two nodes1–2, 2–5, …
neighboursnodes joined by an edgethe neighbours of node 2 are 1, 3 and 5
degree of a nodethe number of edges that leave the nodethe degree of node 2 is 3
patha sequence of nodes in which neighbouring ones are connected by an edge5 – 2 – 3 – 4
cyclea path that returns to the starting node1 – 2 – 3 – 4 – 1
connected graphthere is a path from every node to every other nodeyes

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;
RepresentationMemoryAre u and v neighbours?All the neighbours of uWhen
adjacency matrixn²O(1)O(n)n ≤ a few thousand; Floyd-Warshall
adjacency listn + mO(degree of u)O(degree of u)almost always
edge listmO(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)
    }
}

This is how the tasks The number of islands and The shortest path in a maze are solved.

Practice tasks

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
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
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?