A directed graph or digraph is a pair $G=(V,E)$ where $V$ is a set of vertices and $E$ is a subset of $V \times V$ called edges or arcs.

If $E$ is symmetric (i.e., $(u,v) \in E$ if and only if $(v,u) \in E$ ), then the digraph is isomorphic to an ordinary (that is, undirected) graph.

Digraphs are generally drawn in a similar manner to graphs with arrows on the edges to indicate a sense of direction. For example, the digraph $$\left (\{a,b,c,d\}, \{(a,b),(b,d),(b,c),(c,b),(c,c),(c,d)\}\right )$$ may be drawn as

Since the graph is directed, one has the concept of the number of edges originating or terminating at a given vertex $v$ . The out-degree, $d_{{out}}(v)$ of a vertex $v$ is the number of edges having $v$ as their originating vertex; similarly, the in-degree, $d_{{in}}(v)$ is the number of edges having $v$ as their terminating vertex.

If the graph has a finite number of vertices, say $v_1,\ldots,v_n$ , then obviously $$ \sum_{i=1}^n d_{\textrm{in}}(v_i)=\sum_{i=1}^n d_{\textrm{out}}(v_i $$

A directed path in a digraph $G$ is a sequence of edges $e_1,\ldots,e_k$ such that the end vertex of $e_i$ is the start vertex of $e_{i+1}$ for $i=1,2,\ldots,k-1$ . Such a path is called a directed circuit if, in addition, the end vertex of $e_k$ is the start vertex of $e_1$ .

A digraph is connected (or, sometimes, strongly connected) if for every pair of vertices $u$ and $v$ there is a directed path from $u$ to $v$ . In addition, a digraph $G=(V,E)$ is said to have a root $r\in V$ if every vertex $v\in V$ is reachable from $r$ , i.e. if there is a directed path from $r$ to $v$ .

A digraph is called a directed tree if it has a root and if the underlying (undirected) graph is a tree. That is, it must morphologically look like a tree, and the structure imposed by the directional arrows must flow ``away'' from the root.

If $H$ is a subgraph of a digraph $G$ , then $H$ is said to be a directed spanning tree of $G$ if $H$ is a directed tree and $H$ contains all vertices of $G$ . This is a direct analog of the concept of spanning trees for undirected graphs. Note that if $r$ is the root of $H$ , then $r$ is clearly a root of $G$ . Also, if $r$ is any root of $G$ , it is possible to construct a directed spanning tree of $G$ with root $r$ : construct $H$ edge by edge starting from $r$ . At each vertex, add any edge from $G$ whose terminus is a vertex not yet in $H$ . Since $r$ is a root of $G$ , this process is guaranteed to include each vertex in $G$ ; since we are choosing at each step only vertices not yet visited, we are guaranteed to end up with a tree.