What is a directed graph and what are its features?

Directed graph — is a graph that has a set of vertices (nodes) and a set of edges (arcs), where each arc has a direction.

Features:

• Directed edges: Movement along an edge is only possible in the direction indicated by the arrow.
• Vertex degree: For a directed graph, the in-degree (number of edges ending at the vertex) and out-degree (number of edges starting at the vertex) are defined.
• Paths and cycles: A path is a sequence of vertices connected by edges in the correct direction. A cycle is a path that starts and ends at the same vertex. Directed graphs can contain directed cycles.
• Connectivity: There is weak connectivity (ignoring the directions of edges, the graph is connected as an undirected graph) and strong connectivity (for any two vertices A and B, there exists a directed path from A to B and from B to A).
• Representation: They can be represented by an adjacency list or an adjacency matrix, where for a directed graph, the matrix is generally not symmetric.

Example of adjacency list representation:

# Graph G = (V, E), where V = {0, 1, 2}, E = {(0, 1), (1, 2), (2, 0)}

graph = {
    0: [1],
    1: [2],
    2: [0]
}

Example of adjacency matrix representation:

# Graph G = (V, E), where V = {0, 1, 2}, E = {(0, 1), (1, 2), (0, 2)}

matrix = [
    [0, 1, 1],  # 0 -> 1, 0 -> 2
    [0, 0, 1],  # 1 -> 2
    [0, 0, 0]   # no outgoing edges from 2
]