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.
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:
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).
<ul> <li>Vertex A: [B, C]</li> <li>Vertex B: [C]</li> <li>Vertex C: </li> </ul>
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.