Directed Graphs
One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
On Facebook, friendship goes both ways. On Instagram, you can follow someone who does not follow you back. The first is an undirected graph; the second is a directed graph (digraph). Every edge is an arrow from u to v.
What changes
- Degree splits in two. Out-degree = arrows leaving a vertex; in-degree = arrows arriving.
- Paths follow the arrows. 0 → 1 does not let you go from 1 to 0.
- Storage: a directed edge u → v is stored once:
m[u][v] = 1; // not m[v][u]
adj[u].push_back(v); // not adj[v]So the matrix is usually not symmetric. Its row sum is the out-degree, and its column sum is the in-degree.
DAGs
A Directed Acyclic Graph has no directed cycles. Course prerequisites, task schedules and build systems are DAGs: you can always find an order that respects every arrow.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Press "Build directed". Each edge is stored once, and the matrix is no longer symmetric.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
using namespace std;
const int V = 6;
int main() {
// one-way arrows u -> v
int edges[][2] = {{0, 1}, {1, 2}, {2, 5}, {3, 0}, {4, 3}, {1, 4}, {5, 4}};
int matrix[V][V] = {};
vector<vector<int>> out(V);
for (auto& e : edges) {
matrix[e[0]][e[1]] = 1; // only one direction
out[e[0]].push_back(e[1]);
}
for (int u = 0; u < V; u++) {
int in = 0;
for (int w = 0; w < V; w++) in += matrix[w][u]; // column sum
cout << u << ": out ->";
for (int v : out[u]) cout << " " << v;
cout << " | in-degree " << in << ", out-degree " << out[u].size() << "\n";
}
bool symmetric = true;
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (matrix[i][j] != matrix[j][i]) symmetric = false;
cout << "matrix symmetric? " << (symmetric ? "yes" : "no") << "\n";
cout << "0->1? " << matrix[0][1] << " 1->0? " << matrix[1][0] << "\n";
}0: out -> 1 | in-degree 1, out-degree 1 1: out -> 2 4 | in-degree 1, out-degree 2 2: out -> 5 | in-degree 1, out-degree 1 3: out -> 0 | in-degree 1, out-degree 1 4: out -> 3 | in-degree 2, out-degree 1 5: out -> 4 | in-degree 1, out-degree 1 matrix symmetric? no 0->1? 1 1->0? 0
05Complexity
| out-degree of u | list O(1) (size of adj[u]) · matrix O(V) (row sum) |
|---|---|
| in-degree of u | list O(V + E) · matrix O(V) (column sum) |
| space | matrix O(V²) · list O(V + E) |
The sum of all in-degrees equals the sum of all out-degrees, and both equal E.
06Watch
Graph Types: Directed and Undirected
Why this one: A 4-minute side-by-side of directed and undirected graphs.
Intro to Directed Graphs
Why this one: Digraph vocabulary (in/out-degree, directed paths and cycles) with clear drawings.
07Exam lens
Likely questions
- What is a directed graph? Give two real examples.
- Find the in-degree and out-degree of every vertex in a drawn digraph.
- Draw the adjacency matrix of a digraph. Why is it not symmetric?
- What is a DAG?
Common mistakes
- Adding both
m[u][v]andm[v][u]for a directed edge. - Following an arrow backwards when tracing a path.
- Mixing up in-degree (arrows coming in) and out-degree (arrows going out).
08Quick check
09Practice
🟢 Trace by hand
Digraph with edges A→B, A→C, B→C, C→A, C→D. Give in- and out-degree for each vertex, the adjacency list, and one directed cycle.
Show answer
| vertex | in | out | list |
|---|---|---|---|
| A | 1 | 2 | B, C |
| B | 1 | 1 | C |
| C | 2 | 2 | A, D |
| D | 1 | 0 | – |
Cycle: A → B → C → A (or A → C → A). Totals: in 5 = out 5 = E.
🟡 Implement it
Given an adjacency list of a digraph, build its reverse (every arrow flipped) and compute all in-degrees in O(V + E).
Hint
For every u and every v in adj[u]: rev[v].push_back(u); in[v]++;
🔴 Solve problems
Hint
Trust is a directed edge. The judge has in-degree n − 1 and out-degree 0.
Hint
Courses and prerequisites form a digraph. You can finish all courses iff there is no directed cycle.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.