Graph basics

A graph is a set of points, called vertices, joined by lines, called edges. It describes anything made of objects and links between them, such as towns and the roads between them. This page names the parts of a graph and counts, straight from the input, how many edges touch each vertex. To store a graph for an algorithm such as a search, use an adjacency list.

Explanation

Eight towns are joined by nine roads.

Fig. 1. Eight vertices and nine edges; vertex 8 has none.

A program doesn't see this picture, only a list of the nine roads. From that list alone, it has to find how many roads touch each town.

Vertices, edges and degree

Each town is a vertex of the graph, and the vertices are numbered from 1 to 8. Each road is an edge. An edge joins two vertices, its two ends: the road between towns 2 and 4 has ends 2 and 4. Two vertices joined by an edge are neighbours, so the neighbours of vertex 4 are 2, 3, 5 and 6.

The degree of a vertex is the number of edges that touch it. Vertex 4 has degree 4. Vertex 8 has degree 0: no road leads to it, but it is still a vertex of the graph.

Directed edges

So far every road can be driven both ways, so its edge is undirected. A one-way street leads from one town to another and not back. Its edge is directed: a directed edge from $u$ to $v$ is drawn as an arrow and leads from $u$ to $v$ only.

Loops and multiple edges

A loop joins a vertex to itself, like a road that leaves a town and comes back to it. It adds 2 to the degree of its vertex, one for each end.

Two or more edges between the same two vertices, like two roads between the same pair of towns, are multiple edges, and each of them counts in the degree. A graph with no loops and no multiple edges is called simple. The graph in Fig. 1 is simple.

Paths, cycles and connected graphs

A route goes from vertex to vertex along edges. A path is a route that never visits a vertex twice. The blue route in Fig. 1 is a path from vertex 1 to vertex 7. The length of a path is the number of its edges, so the blue route has length 3. In a directed graph a path must follow the arrows: a directed edge from vertex 2 to vertex 4 leads from 2 to 4, but not back.

A cycle is a route that comes back to the vertex it started from without using any other vertex twice. The red route in Fig. 1 is a cycle: it goes from vertex 2 through vertices 4 and 5 and back to 2. The graph has other cycles too, for example through vertices 3, 4 and 6.

A graph is connected if a path leads between every two vertices. The two vertices don't need to be joined by an edge: vertices 1 and 7 are not, but the blue route leads from one to the other.

Implementation

Graph problems give the graph in the same format almost every time. The first line has two numbers: n, the number of vertices, and m, the number of edges. The vertices are numbered from 1 to n. Then come m lines, one per edge: the line u v is an edge between u and v. For the graph in Fig. 1 the input is:

8 9
1 2
1 3
2 4
3 4
2 5
4 6
3 6
6 7
4 5

Vertex 8 is on no line, so only the first line tells the program that the graph has 8 vertices. A program that takes n from the largest number in the lines gets 7 and prints only 7 degrees, without the 0 of vertex 8.

Which vertex has the most edges? On Fig. 1 you can count them, but a program sees only these lines. The direct way is to take the vertices one by one and, for each, read through all the lines and count those that mention it. That is 8 · 9 = 72 checks here, and n \cdot m in general. For n = m = 10^5 it is 10^{10} checks, a hundred times more than the rule of thumb of about 10^8 simple steps per second (see complexity). But each line already names both vertices it touches, so one pass over the lines is enough.

We keep an array deg with one counter per vertex. After the program has read some of the lines, deg[v] is the number of those lines that mention v; after the last line it is the degree of v. A line u v is an undirected edge that touches both its ends, so it adds 1 to deg[u] and 1 to deg[v].

1. Read the sizes: read n and m, and set deg[v] = 0 for every vertex v.

2. Read the edges: read the m lines one by one.

3. Count: for each line u v, add 1 to deg[u] and to deg[v].

4. Print: print deg[1], deg[2], …, deg[n].

On the example, the count goes line by line like this:

After the last line the degrees are 2 3 3 4 2 3 1 0. Vertex 4 has the most edges, 4, as we counted on Fig. 1, and vertex 8 stays at 0.

The program prints these degrees on the first line. The lines marked "only needed for a directed graph" keep two more counts and, on the example, print two more lines.

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

int main() {
    // read the sizes
    int n, m;
    cin >> n >> m;
    vector<int> deg(n + 1, 0);
    vector<int> outdeg(n + 1, 0), indeg(n + 1, 0);   // only needed for a directed graph

    // read the edges
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        // count
        deg[u]++;
        deg[v]++;
        outdeg[u]++;   // only needed for a directed graph
        indeg[v]++;    // only needed for a directed graph
    }

    // print
    for (int v = 1; v <= n; v++) {
        cout << deg[v] << ' ';
    }
    cout << '\n';

    // print out-degrees and in-degrees; remove this block if the graph is undirected
    for (int v = 1; v <= n; v++) cout << outdeg[v] << ' ';
    cout << '\n';
    for (int v = 1; v <= n; v++) cout << indeg[v] << ' ';
    cout << '\n';
}

The program does a constant amount of work for each edge and for each vertex, so it runs in O(n + m) time.

Each edge adds 1 to the degree of each of its two ends, so in every graph the degrees add up to $2m$, and a program can use this as a quick check of its counts. A loop needs no special code: the line 3 3 runs deg[3]++ twice and adds 2, as the rule for loops says.

Roads also have lengths. A number written on an edge, such as the length of a road in kilometres, is the edge's weight, and a graph with such numbers is weighted. The length of a path is then the sum of the weights of its edges. In the input, each line gets a third number, u v w for an edge of weight w. The program reads it into a variable and, for counting degrees, ignores it.

Directed graphs

In a directed graph, the line u v is a directed edge from u to v. The number of edges that leave a vertex is its out-degree, and the number that enter it is its in-degree. The edge u v leaves u and enters v, so it adds 1 to outdeg[u] and 1 to indeg[v]. These are the marked lines in the program.

Read as directed edges, the example gives the out-degrees 2 2 2 2 0 1 0 0 on the second line of the output and the in-degrees 0 1 1 2 2 2 1 0 on the third. Every directed edge adds 1 to one out-degree and 1 to one in-degree, so each line adds up to m = 9.

Storing the graph

Counting degrees needs each edge once, in any order. Most algorithms need more: they take a vertex and go over its neighbours. For that, the program stores the graph first. An adjacency list keeps, for every vertex, the list of its neighbours. It takes O(n + m) memory and lists the neighbours of a vertex in time proportional to its degree, so most graph algorithms use it. An adjacency matrix is an n \times n table that says for every pair of vertices whether they are joined by an edge. It takes n^2 cells of memory and answers "is there an edge between u and v?" in $O(1)$. An edge list keeps the input lines as they are, for algorithms that go over all edges.

Common mistakes

• Adding 1 to only one end of an edge: deg[u]++ alone counts out-degrees, which is right only in a directed graph. In an undirected graph, add 1 to both deg[u] and deg[v].

• Comparing m with the number of pairs, n(n-1)/2, to check that every two vertices are joined; with multiple edges the counts can match while a pair is missing. When the statement allows multiple edges, mark which pairs are joined, for example in an adjacency matrix, and check every pair.

• Reading a directed graph as undirected, or the other way round, which counts the wrong ends of each edge. Look for words like "directed", "one-way" or "from $u$ to $v$" in the statement.

Related topics

• Breadth-first search and depth-first search find every vertex a path reaches from a given vertex. Breadth-first search also finds the paths with the fewest edges.

• Connected components split a graph that isn't connected into its connected parts.

• Cycle detection finds out whether a graph has a cycle.

• Trees are connected graphs without cycles.

Practice

The last problem also needs a search, such as depth-first search.