Representing a Graph in C++: Adjacency Matrix vs Adjacency List, and Degree in Directed Graphs

A graph is a set of vertices and a set of edges

Formally, a graph is a pair G = (V, E): a finite set of vertices V, and a set of edges E where each edge joins a pair of vertices. That is the whole definition, and everything else is a qualifier on it.

A graph is non-linear, like a tree — but unlike a tree it has no root, no notion of parent and child, and no rule against cycles. A tree is a special case of a graph, not the other way round. Trees model hierarchies; graphs model general relationships: road networks, social follows, dependencies between build targets, web pages linking to web pages.

The vocabulary below is small and every term earns its place. Learn it once and the rest of the page reads itself.

Two of these are not descriptions but decisions you make about your own data: sparse and dense. They are the entire basis for choosing between the two representations, so it is worth being concrete. A social network with ten million users and an average of two hundred friends each is sparse — E ≈ 2×10⁹ against a possible V² = 10¹⁴. A five-city travel-time table where every city has a time to every other is dense; in fact it is complete.

Path, cycle and self-loop are three different things

These three get swapped for each other constantly, and they are not interchangeable.

• A path is a sequence: A, B, E, G is a path if each consecutive pair is joined by an edge. It has a length (usually counted in edges) and it goes from somewhere to somewhere else.
• A cycle is a path whose first and last vertex are the same. B, D, G, E, B is a cycle. It involves several vertices and several edges. "A path that starts and ends at the same vertex" is the definition to be able to write down.
• A self-loop (sometimes just "loop") is a single edge from a vertex to itself: U → U. One edge, one vertex. It is not a cycle in the interesting sense and it is not a path.

The distinction that matters in practice: a cycle is a property of how the edges are arranged, so it is what makes a traversal need a visited array (without one, BFS or DFS on a cyclic graph loops forever). A self-loop is a single entry in your data structure — one diagonal cell in the matrix, one entry in a vertex's own list — and its consequence is arithmetic: it counts twice towards that vertex's degree.

One more pair that is easy to mix up. Vertices are adjacent to vertices; edges are incident to vertices. If you are describing the relationship between an edge and one of its endpoints, the word is incident.

Which end of the arrow is which

In a directed graph, edge (u, v) means u → v. The two ends have names, and they come in matched sets:

The useful anchor is the ordered pair itself. Write the edge down as (u, v) — first position, second position — and every row of that table follows. Origin is the first coordinate. When a question hands you an edge label and asks for its origin and destination, find the labelled arrow, write it out as X → Y, and read off X as origin and Y as destination. Do not try to infer it from where the vertices sit on the page; a diagram is free to draw the destination above, below or to the left of the source.

The same first-position/second-position rule is how you count degrees without drawing anything, which is the subject of a later section: out-degree of v is how many times v appears in the first slot across the edge list, in-degree is how many times it appears in the second.

The adjacency matrix: one cell per ordered pair

Number the vertices 0 … n−1. Allocate an n × n array A. Then A[i][j] records whether there is an edge from i to j.

For the undirected graph A-B, A-C, B-D, B-E, C-E, C-F, D-G, E-G, F-G the matrix is:

Three checks you can run on any undirected matrix in about five seconds, and should:

1. It is symmetric about the main diagonal. If it is not, either you have missed a mirrored cell or the graph was directed after all.
2. The number of 1s is exactly 2|E|. Here 18, for nine edges. Every undirected edge is recorded twice.
3. The diagonal is all zeros unless the graph has self-loops.

And the property that turns the matrix into a degree calculator: the sum of row i is the degree of vertex i (out-degree, if the graph is directed) and the sum of column j is its in-degree. In the matrix above, row B sums to 3, and B does have three neighbours.

What the matrix buys you is the cell lookup. "Is there an edge from i to j?" is one array read — O(1), independent of how large or how dense the graph is. What it costs you is everything else: n² cells whether or not the edges exist, and O(V) work to list one vertex's neighbours because you have to scan the whole row, most of which is zeros.

The adjacency list: one list per vertex

Instead of a cell for every possible edge, give every vertex a list of the neighbours it actually has. Classically that is a linked list — a node per neighbour holding a vertex field and a link to the next node, plus a weight field if the graph is weighted. In modern C++ you would write std::vector<std::vector<int>>, which is the same structure with better cache behaviour and no manual delete.

The same graph:

A -> B, C
B -> A, D, E
C -> A, E, F
D -> B, G
E -> B, C, G
F -> C, G
G -> D, E, F

The rules mirror the matrix:

• Undirected: each edge appears twice, once in each endpoint's list. So the total number of list entries is 2|E| — 18 above, matching the count of 1s in the matrix, because they are literally the same 18 facts.
• Directed: each edge appears once, in the list of its source. A vertex's list is its successors. The total number of entries is |E|.
• Self-loop on v: v appears in its own list. Forgetting this is the most common list-building slip on directed graphs.
• A vertex with no neighbours gets an empty list. When you are writing one out by hand, write something visible — a dash — rather than leaving a blank that reads as an omission.
• Order within a list is not part of the graph. B -> A, D, E and B -> E, D, A describe the same graph. But it is part of the traversal: BFS and DFS visit neighbours in list order, so if you are asked to trace a traversal in ascending order, sort the lists first and do it once, carefully, before you start.

What the list buys you is proportionality: space is O(V + E) — the V is for the array of heads, which you pay for even for isolated vertices — and enumerating a vertex's neighbours costs O(deg(v)), touching nothing that is not an actual edge. What it costs you is the cell lookup: "is there an edge i → j?" now means scanning i's list, O(deg(i)), up to O(V) in the worst case.

Both representations, built from one edge list

Here is the whole idea in one program. It takes a single edge list and produces both structures from it, then prints them and checks them against each other. Read the two build functions side by side: the matrix writes two cells per edge, the list appends two entries per edge, and those are the same two facts stored two ways.

Note the two hasEdge functions at the bottom. They answer the same question and their bodies tell you the whole trade-off: one is an array read, the other is a loop.

Output:

Adjacency matrix
    A B C D E F G
  A 0 1 1 0 0 0 0
  B 1 0 0 1 1 0 0
  C 1 0 0 0 1 1 0
  D 0 1 0 0 0 0 1
  E 0 1 1 0 0 0 1
  F 0 0 1 0 0 0 1
  G 0 0 0 1 1 1 0

Adjacency list
  A -> B, C
  B -> A, D, E
  C -> A, E, F
  D -> B, G
  E -> B, C, G
  F -> C, G
  G -> D, E, F

Degree (row sum of the matrix == length of the list)
  deg(A) = 2  list length = 2
  deg(B) = 3  list length = 3
  deg(C) = 3  list length = 3
  deg(D) = 2  list length = 2
  deg(E) = 3  list length = 3
  deg(F) = 2  list length = 2
  deg(G) = 3  list length = 3
  total = 18 and 18 = 2|E| = 18

Edge lookup B-E: matrix 1, list 1
Edge lookup B-F: matrix 0, list 0

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

// One undirected, unweighted graph, built twice from the same edge list.
//   A-B  A-C  B-D  B-E  C-E  C-F  D-G  E-G  F-G      |V| = 7, |E| = 9
const std::vector<std::string> NAME = {"A", "B", "C", "D", "E", "F", "G"};
const int V = 7;
const std::vector<std::pair<int, int>> EDGES = {
    {0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 6}, {4, 6}, {5, 6}};

// ---- Representation 1: adjacency matrix. V*V cells, allocated up front. ----
std::vector<std::vector<int>> buildMatrix() {
    std::vector<std::vector<int>> a(V, std::vector<int>(V, 0));
    for (const auto& e : EDGES) {
        a[e.first][e.second] = 1;
        a[e.second][e.first] = 1;   // undirected: fill BOTH cells
    }
    return a;
}

// ---- Representation 2: adjacency list. One list per vertex. ----
std::vector<std::vector<int>> buildList() {
    std::vector<std::vector<int>> adj(V);
    for (const auto& e : EDGES) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);   // undirected: append TWICE
    }
    for (auto& row : adj) std::sort(row.begin(), row.end());
    return adj;
}

// O(1): one array read, no matter how big the graph is.
bool hasEdgeMatrix(const std::vector<std::vector<int>>& a, int i, int j) {
    return a[i][j] != 0;
}

// O(deg(i)): scan i's neighbour list.
bool hasEdgeList(const std::vector<std::vector<int>>& adj, int i, int j) {
    for (int u : adj[i])
        if (u == j) return true;
    return false;
}

int main() {
    std::vector<std::vector<int>> a = buildMatrix();
    std::vector<std::vector<int>> adj = buildList();

    std::cout << "Adjacency matrix\n    ";
    for (int j = 0; j < V; ++j) std::cout << NAME[j] << " ";
    std::cout << "\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << NAME[i] << " ";
        for (int j = 0; j < V; ++j) std::cout << a[i][j] << " ";
        std::cout << "\n";
    }

    std::cout << "\nAdjacency list\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << NAME[i] << " -> ";
        for (std::size_t k = 0; k < adj[i].size(); ++k)
            std::cout << NAME[adj[i][k]] << (k + 1 < adj[i].size() ? ", " : "");
        std::cout << "\n";
    }

    std::cout << "\nDegree (row sum of the matrix == length of the list)\n";
    int sumRow = 0, sumLen = 0;
    for (int i = 0; i < V; ++i) {
        int row = 0;
        for (int j = 0; j < V; ++j) row += a[i][j];
        sumRow += row;
        sumLen += static_cast<int>(adj[i].size());
        std::cout << "  deg(" << NAME[i] << ") = " << row
                  << "  list length = " << adj[i].size() << "\n";
    }
    std::cout << "  total = " << sumRow << " and " << sumLen
              << " = 2|E| = " << 2 * EDGES.size() << "\n";

    std::cout << "\nEdge lookup B-E: matrix " << hasEdgeMatrix(a, 1, 4)
              << ", list " << hasEdgeList(adj, 1, 4) << "\n";
    std::cout << "Edge lookup B-F: matrix " << hasEdgeMatrix(a, 1, 5)
              << ", list " << hasEdgeList(adj, 1, 5) << "\n";
}

The trade-off, and why every traversal bound has two versions

Why BFS and DFS are O(V + E) on a list. A traversal does two things: it visits each vertex once, and at each vertex it walks that vertex's neighbour list. The first is V units of work. The second, summed over all vertices, is Σ deg(v) — which is 2E for an undirected graph and E for a directed one, so O(E) either way. Total O(V + E). Nothing in that argument depends on the graph being sparse; the bound is exact.

Why the same code is O(V²) on a matrix. Change one thing — the neighbour loop now scans a row of V cells instead of a list of deg(v) entries — and the second term becomes V per vertex, V² overall, regardless of how few edges there are. On a sparse graph that is not a small constant factor: with V = 10⁵ and E = 3×10⁵, V + E is about 4×10⁵ and V² is 10¹⁰. The matrix version does twenty-five thousand times the work, and needs 10¹⁰ cells to hold a graph with 3×10⁵ edges, which it cannot.

When the matrix genuinely wins. When E is close to V², O(V²) space is O(E) space and you are paying nothing for the zeros — plus you get contiguous memory, no indirection, and a bit-per-edge encoding if you want it. When the dominant operation is "is i connected to j?" rather than "who are i's neighbours?" — think a fixed 200-airport route table queried millions of times — the O(1) lookup is worth the grid. And when V is small and fixed, V² is small and fixed; nobody worries about a 50×50 array.

The default, in the absence of a reason, is the adjacency list. Real graphs are overwhelmingly sparse.

Directed graphs: the same code, minus the mirroring

Everything about direction reduces to one edit in each builder. The matrix writes one cell instead of two. The list appends one entry instead of two. That is it — and it is also why the total storage halves, and why the matrix stops being symmetric.

The program below uses the digraph 0→1, 0→2, 1→2, 2→2, 2→3, 3→1, 3→4, 4→0, which has a self-loop on vertex 2. Watch three things in the output: the matrix is not symmetric, A[2][2] is the self-loop sitting on the diagonal, and the row sums and column sums reproduce the out-degrees and in-degrees exactly.

Output:

Adjacency matrix (row = from, column = to)
    0 1 2 3 4
  0 0 1 1 0 0
  1 0 0 1 0 0
  2 0 0 1 1 0
  3 0 1 0 0 1
  4 1 0 0 0 0

Adjacency list (successors only)
  0 -> 1, 2
  1 -> 2
  2 -> 2, 3
  3 -> 1, 4
  4 -> 0

  v  out  in  degree   (out = row sum, in = column sum)
  0   2   1     3     (row 2, col 1)
  1   1   2     3     (row 1, col 2)
  2   2   3     5     (row 2, col 3)
  3   2   1     3     (row 2, col 1)
  4   1   1     2     (row 1, col 1)

  sum of out-degrees = 8, sum of in-degrees = 8, |E| = 8
  vertex 2 carries a self-loop: out 1 + in 1, so it adds 2 to degree(2)

#include <iostream>
#include <utility>
#include <vector>

// One DIRECTED graph, with a self-loop on vertex 2.
//   0->1  0->2  1->2  2->2  2->3  3->1  3->4  4->0        |V| = 5, |E| = 8
const int V = 5;
const std::vector<std::pair<int, int>> EDGES = {
    {0, 1}, {0, 2}, {1, 2}, {2, 2}, {2, 3}, {3, 1}, {3, 4}, {4, 0}};

int main() {
    std::vector<std::vector<int>> a(V, std::vector<int>(V, 0));
    std::vector<std::vector<int>> succ(V);   // out-edges only
    std::vector<int> outDeg(V, 0), inDeg(V, 0);

    for (const auto& e : EDGES) {
        int from = e.first, to = e.second;   // from --> to
        a[from][to] = 1;                     // ONE cell, not two
        succ[from].push_back(to);            // ONE list, not two
        ++outDeg[from];                      // tail of the arrow
        ++inDeg[to];                         // head of the arrow
    }

    std::cout << "Adjacency matrix (row = from, column = to)\n    ";
    for (int j = 0; j < V; ++j) std::cout << j << " ";
    std::cout << "\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << i << " ";
        for (int j = 0; j < V; ++j) std::cout << a[i][j] << " ";
        std::cout << "\n";
    }

    std::cout << "\nAdjacency list (successors only)\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << i << " -> ";
        if (succ[i].empty()) std::cout << "-";
        for (std::size_t k = 0; k < succ[i].size(); ++k)
            std::cout << succ[i][k] << (k + 1 < succ[i].size() ? ", " : "");
        std::cout << "\n";
    }

    std::cout << "\n  v  out  in  degree   (out = row sum, in = column sum)\n";
    int sumOut = 0, sumIn = 0;
    for (int v = 0; v < V; ++v) {
        int row = 0, col = 0;
        for (int j = 0; j < V; ++j) row += a[v][j];   // row sum  = out-degree
        for (int i = 0; i < V; ++i) col += a[i][v];   // col sum  = in-degree
        sumOut += outDeg[v];
        sumIn += inDeg[v];
        std::cout << "  " << v << "   " << outDeg[v] << "   " << inDeg[v]
                  << "     " << outDeg[v] + inDeg[v]
                  << "     (row " << row << ", col " << col << ")\n";
    }
    std::cout << "\n  sum of out-degrees = " << sumOut
              << ", sum of in-degrees = " << sumIn
              << ", |E| = " << EDGES.size() << "\n";
    std::cout << "  vertex 2 carries a self-loop: out 1 + in 1, so it adds 2 "
                 "to degree(2)\n";
}

Counting degree by hand, and the check that catches your mistake

You will not always have a compiler. The reliable manual procedure works straight off the edge list, with no diagram:

• Out-degree d⁺(v): count how many pairs have v in the first slot — (v, _).
• In-degree d⁻(v): count how many pairs have v in the second slot — (_, v).
• Total degree of v in a digraph is d⁺(v) + d⁻(v).

Do it column-wise, one vertex per row of a scratch table, and write the actual edges into the cells rather than just a tally — you can then re-read them instead of re-counting.

The self-loop. An edge v → v puts v in the first slot and the second slot. So it adds one to out-degree and one to in-degree, and therefore two to the total degree of v. In the matrix it is the single diagonal cell A[v][v], which is counted once by the row sum and once by the column sum — the same two contributions, arrived at from the other direction. In the adjacency list, v appears in its own list. Undirected graphs use the same rule for the same reason: a self-loop contributes 2 to deg(v).

The check, and it takes ten seconds. Every directed edge has exactly one tail and exactly one head, so

Σ d⁺(v) = Σ d⁻(v) = |E|

Add up your out-degree column. Add up your in-degree column. Both must equal the number of edges. If either is off, you have miscounted, missed a self-loop, or reversed an arrow — and you know it before you use the numbers for anything. In the digraph above, both sums are 8 and there are 8 edges.

The undirected version of the same statement is the handshake lemma: Σ deg(v) = 2|E|, because each undirected edge is incident to two vertex-ends. That is the 18-for-9-edges check from the matrix section. (Both statements are really the same counting argument, so in a digraph the total degrees also sum to 2|E| — but the useful check there is the sharper one, Σ d⁺ = Σ d⁻ = |E|, because it will catch a reversed arrow, which the combined sum will not.)

One consequence worth knowing because it makes questions trivial: since Σ deg(v) = 2|E| is even, the number of odd-degree vertices in an undirected graph is always even. If you count degrees and end up with three odd ones, you have made an arithmetic error, not discovered a strange graph.

Weights, and converting between the two forms

Adding weights changes nothing structural. The matrix stores the weight in place of the 1, with a sentinel value standing in for "no edge". The list stores a {neighbour, weight} pair per entry instead of a bare vertex index.

The only real decision is the sentinel. 0 is the natural choice and is wrong the moment a zero-cost edge is legal. -1 works when all weights are positive and is compact to write by hand. ∞ — in practice INT_MAX or a value larger than any possible path — is what shortest-path code wants, because it makes dist + w comparisons behave, though you then have to watch for overflow when you add to it. Pick one, and say which one you picked.

Matrix → list. Scan row i left to right; for every cell that is not the sentinel, append j to vertex i's list. Because j increases as you scan, each list comes out already sorted ascending — you never need a sort step. That is worth remembering when you are asked for adjacency lists "in ascending order" and you have been given a matrix: just read the rows left to right.

List → matrix. Fill the whole grid with the sentinel first, then walk every list and set A[i][j]. If the graph is undirected and the lists were written out in full (each edge in both endpoints' lists), you will set both mirrored cells naturally; if you were given only one direction per edge, you must set A[j][i] yourself.

The checks after any conversion:

The program below builds a weight matrix for the weighted version of our seven-vertex graph, prints it, converts it row by row into a weighted adjacency list, and confirms the entry count.

Output:

Weight matrix (-1 means no edge)
      A  B  C  D  E  F  G
  A  -1  3  2 -1 -1 -1 -1
  B   3 -1 -1  4  1 -1 -1
  C   2 -1 -1 -1  5  2 -1
  D  -1  4 -1 -1 -1 -1  3
  E  -1  1  5 -1 -1 -1  4
  F  -1 -1  2 -1 -1 -1  6
  G  -1 -1 -1  3  4  6 -1

Weighted adjacency list
  A -> (B,3) (C,2)
  B -> (A,3) (D,4) (E,1)
  C -> (A,2) (E,5) (F,2)
  D -> (B,4) (G,3)
  E -> (B,1) (C,5) (G,4)
  F -> (C,2) (G,6)
  G -> (D,3) (E,4) (F,6)
  list nodes = 18 = 2|E| = 18

#include <iostream>
#include <string>
#include <utility>
#include <vector>

// A WEIGHTED undirected graph, stored as a weight matrix, then converted
// row by row into a weighted adjacency list.
//   A-B(3) A-C(2) B-D(4) B-E(1) C-E(5) C-F(2) D-G(3) E-G(4) F-G(6)
const std::vector<std::string> NAME = {"A", "B", "C", "D", "E", "F", "G"};
const int V = 7;
const int NO_EDGE = -1;   // safe only because every real weight is positive

struct WEdge { int to; int weight; };

int main() {
    const std::vector<std::vector<int>> raw = {
        {0, 1, 3}, {0, 2, 2}, {1, 3, 4}, {1, 4, 1}, {2, 4, 5},
        {2, 5, 2}, {3, 6, 3}, {4, 6, 4}, {5, 6, 6}};

    std::vector<std::vector<int>> w(V, std::vector<int>(V, NO_EDGE));
    for (const auto& e : raw) {
        w[e[0]][e[1]] = e[2];
        w[e[1]][e[0]] = e[2];
    }

    std::cout << "Weight matrix (-1 means no edge)\n    ";
    for (int j = 0; j < V; ++j) std::cout << "  " << NAME[j];
    std::cout << "\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << NAME[i] << " ";
        for (int j = 0; j < V; ++j) {
            std::cout << (w[i][j] == NO_EDGE ? " -1" : "  " + std::to_string(w[i][j]));
        }
        std::cout << "\n";
    }

    // Matrix -> list. Scanning j in increasing order makes each list sorted
    // for free; there is nothing to sort afterwards.
    std::vector<std::vector<WEdge>> adj(V);
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            if (w[i][j] != NO_EDGE) adj[i].push_back(WEdge{j, w[i][j]});

    std::cout << "\nWeighted adjacency list\n";
    int nodes = 0;
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << NAME[i] << " -> ";
        for (std::size_t k = 0; k < adj[i].size(); ++k) {
            std::cout << "(" << NAME[adj[i][k].to] << "," << adj[i][k].weight << ")"
                      << (k + 1 < adj[i].size() ? " " : "");
            ++nodes;
        }
        std::cout << "\n";
    }
    std::cout << "  list nodes = " << nodes << " = 2|E| = " << 2 * raw.size() << "\n";
}

"Adjacent to" is ambiguous in a directed graph — say which you mean

In an undirected graph, "u is adjacent to v" is unambiguous and symmetric: there is an edge between them, full stop.

In a directed graph it is not, and sources genuinely disagree. Given the edge u → v:

• One tradition says u is adjacent to v, and v is adjacent from u — the preposition carries the direction, and "the vertices adjacent to v" therefore means v's predecessors, the vertices with arrows pointing at it.
• The other tradition — the one most C++ and algorithms texts use, and the one implied by the phrase "adjacency list" — says the vertices adjacent to u are the ones u points at: its successors.

Both are in print. This is not a subtlety you can resolve by thinking harder about it; it is a naming collision. What you can do is:

1. Look for the definition in front of you. If the material you are working from defines it, that definition wins for that material, whatever any other book says.
2. Watch for a parenthetical. A question that says "adjacent (successor) vertices" has told you which one it means, and that overrides everything.
3. When you are the one writing, do not use the bare word. Write successors of `u`, or predecessors of `v`, or out-neighbours and in-neighbours. Nobody has ever been confused by "out-neighbours".

One thing is stable across both traditions and worth holding onto: an adjacency list stores successors. When you are asked to build the adjacency list of a digraph, each vertex's row is the set of vertices it points at. If you need the predecessors — and you sometimes do, for example when you want the in-degrees, or when you want to walk a dependency graph backwards — you build the reverse graph, which is exercise 3.

The mistakes people actually make

Building the structures

1. Filling one matrix cell for an undirected edge. A[i][j] = 1 without A[j][i] = 1 silently gives you a directed graph. The tell is that the matrix is not symmetric; check for symmetry every single time.
2. Filling two cells for a directed edge. The mirror-image mistake, and worse, because it invents edges. Now every arrow is two-way, Σd⁺ comes out at 2|E|, and any shortest-path answer is wrong in a way that still looks plausible.
3. Appending an undirected edge to only one list. Same bug, list-flavoured. If your entry count is |E| and the graph is undirected, you have written each edge once and half the graph is unreachable from the other half.
4. Dropping the self-loop out of a vertex's own list. 2 → 2 means 2 appears in 2's successor list. It looks redundant, so it gets dropped, and then the degree count is wrong by two.
5. Forgetting the V in O(V + E). The adjacency list needs an array of V heads whether or not the vertices have any edges, so an edgeless graph on a million vertices still costs a million pointers. The space is O(V + E), never O(E).
6. Using 0 as the "no edge" sentinel in a weighted matrix that allows zero weights. A free edge and a missing edge become indistinguishable. Use a value the weights cannot take, and write down which.
7. Assuming the neighbour lists are sorted. They are only sorted if you sorted them or built them by scanning matrix rows. If a traversal must visit neighbours in ascending order, sort first — the traversal will not do it for you.

Direction and degree

1. Reversing an arrow when reading a diagram. The arrowhead is the destination. Write each edge out as an ordered pair (from, to) before you count anything, and count from the pairs, not from the picture.
2. Reading a labelled edge's origin and destination off the layout. Vertical or leftward arrows are common; position on the page means nothing. Find the arrow, write X → Y, origin is X.
3. Swapping row and column. In a directed matrix the convention is row = from, column = to, so row sum is out-degree and column sum is in-degree. Getting this backwards flips every degree in the graph. Sanity check on one vertex you know.
4. Counting a self-loop once. It is one edge but two ends, so it contributes 1 to out-degree, 1 to in-degree, and 2 to total degree.
5. Not running Σ d⁺ = Σ d⁻ = |E|. Ten seconds, and it catches missed edges, doubled edges and reversed arrows. The undirected equivalent is Σ deg = 2|E|.
6. Treating "adjacent to" as self-evident in a digraph. It is not; see the previous section. Say successors or predecessors.
7. Using a matrix for a large sparse graph out of habit. V = 10⁵ needs 10¹⁰ cells. The program will not run out of correctness, it will run out of memory. When E ≪ V², use the list.

Exercises with solutions

Work through each question before opening the solution below it.

0 -> 1, 2
1 -> 0, 3, 4
2 -> 0, 4
3 -> 1, 4, 5
4 -> 1, 2, 3, 5
5 -> 3, 4

A -> B, D
B -> C
C -> A, C, E
D -> B, C
E -> -

#include <iostream>
#include <vector>

// Given the successor lists of a directed graph, build the predecessor lists
// (the reverse graph) in O(V + E).
std::vector<std::vector<int>> reverseGraph(const std::vector<std::vector<int>>& succ) {
    std::vector<std::vector<int>> pred(succ.size());
    for (std::size_t u = 0; u < succ.size(); ++u)
        for (int v : succ[u])
            pred[v].push_back(static_cast<int>(u));   // edge u->v seen from v
    return pred;
}

int main() {
    // 0->1 0->2 1->2 2->2 2->3 3->1 3->4 4->0
    std::vector<std::vector<int>> succ = {{1, 2}, {2}, {2, 3}, {1, 4}, {0}};
    std::vector<std::vector<int>> pred = reverseGraph(succ);

    for (std::size_t v = 0; v < pred.size(); ++v) {
        std::cout << "  predecessors of " << v << ": ";
        if (pred[v].empty()) std::cout << "-";
        for (std::size_t k = 0; k < pred[v].size(); ++k)
            std::cout << pred[v][k] << (k + 1 < pred[v].size() ? ", " : "");
        std::cout << "   in-degree = " << pred[v].size() << "\n";
    }
}

  predecessors of 0: 4   in-degree = 1
  predecessors of 1: 0, 3   in-degree = 2
  predecessors of 2: 0, 1, 2   in-degree = 3
  predecessors of 3: 2   in-degree = 1
  predecessors of 4: 3   in-degree = 1

Related pages