# 7.3 Directed Graphs

> One-way edges, in-degree and out-degree, directed paths and cycles, and how the matrix and list change.

Chapter: Graphs · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/directed-graphs

## Mental 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**:

```cpp
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 **D**irected **A**cyclic **G**raph has no directed cycles. Course prerequisites, task schedules and build systems are DAGs: you can always find an order that respects every arrow.

## C++ code: directed-graph.cpp

```cpp
#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";
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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**.

## Videos

- [Graph Types: Directed and Undirected](https://youtu.be/amaH38_mXK4) (TutorialsPoint): A 4-minute side-by-side of directed and undirected graphs.
- [Intro to Directed Graphs](https://youtu.be/mXoiHgH4mEE) (Wrath of Math): Digraph vocabulary (in/out-degree, directed paths and cycles) with clear drawings.

## Exam 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]` and `m[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).

## Quick check

1. In a digraph, the sum of all out-degrees equals…
   A. V
   B. E
   C. 2E
   D. V²
   Answer: B. Each arrow leaves exactly one vertex.

2. Edges 0→1, 1→2, 2→0, 2→3. In-degree of 0?
   A. 0
   B. 1
   C. 2
   D. 3
   Answer: B. Only 2 → 0 points into 0.

3. Which is naturally a directed graph?
   A. Facebook friendships
   B. Twitter/X follows
   C. Two-way roads
   D. A handshake network
   Answer: B. You can follow someone who does not follow you back.

## Practice

**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.

Solution:

| 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]++;`

**Problems:**

- [Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/) (easy). Hint: Trust is a directed edge. The judge has in-degree n − 1 and out-degree 0.
- [Course Schedule](https://leetcode.com/problems/course-schedule/) (medium). Hint: Courses and prerequisites form a digraph. You can finish all courses iff there is no directed cycle.

## Mastery checklist

- [ ] I can explain directed vs undirected edges with examples.
- [ ] I can compute in-degree and out-degree.
- [ ] I can draw the matrix and list of a digraph.