[Data Structure] Directed Graphs

A directed graph, or digraph, consists of vertices connected by directed edges. 

A directed edge is a connection between a starting vertex and a terminating vertex. In a directed graph, a vertex Y is adjacent to a vertex X, if there is an edge from X to Y. 

Many graphs are directed, like those representing links between web pages, maps for navigation, or college course prerequisites.

 

Airline Routes Digraph

From above digraph, Tucson is adjacent to Los Angles; Dellas is adjacent to Tucson.

 

 

In a directed graph:

- A path is a sequence of directed edges leading from a source vertex to a destination vertex. 

- A cycle is a path that starts and ends at the same vertex. A directed graph is cyclic if the graph contains a cycle, and acyclic if the graph doesn't contain a cycle.

 

 

A vertex's degree is defined by the sum of the number of outgoing and incoming edges. 

For example, vertex B's degree from above acyclic digraph is 2 (incoming) + 1 (outgoing) = 3.