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