What Is Directed Graph Data Structure?


Angela Bailey

A directed graph is a data structure that consists of a set of vertices (or nodes) connected by edges, where the edges have a specific direction. Unlike an undirected graph, where edges are bidirectional, in a directed graph, the edges have a specific origin and destination. This data structure is also known as a digraph.

Basic Definitions

Before diving deeper into directed graphs, it’s important to understand some basic definitions:

  • Vertex: Also referred to as a node, it represents an entity or object in the graph. Each vertex can have zero or more outgoing and incoming edges.
  • Edge: An edge represents a connection or relationship between two vertices. It has a direction from the source vertex (tail) to the destination vertex (head).
  • Outdegree: The outdegree of a vertex refers to the number of outgoing edges from that vertex.
  • Indegree: The indegree of a vertex refers to the number of incoming edges to that vertex.


A directed graph can be represented in various ways. Two commonly used representations are:

Adjacency List

In this representation, each vertex maintains a list of its neighboring vertices. It can be implemented using an array of linked lists or using associative arrays (hash maps).

  <li>Vertex A: [B, C]</li>
  <li>Vertex B: [C]</li>
  <li>Vertex C: []</li>

Adjacency Matrix

In this representation, a matrix of size VxV is used, where V is the number of vertices in the graph. Each cell (i, j) in the matrix represents an edge from vertex i to vertex j.

<th>          A</td>
<td align="center">0</td>
<td align="center">1</td>
<td align="center">1</td>
<td align="center">0</td>
<td align="center">0</td>
<td align="center">1</td>