All the edges of directed graph, digraph, have directions associated with them.

*u* and *v* are vertices of digraph G.

*u* **reaches** *v* if there is a directed path from
*u* to *v* in G.

G is **strongly connected** iff for
any pair of vertices *u* and *v,* if *u* reaches *v*
then *v* reaches *u*.

**Directed cycles** are cycles where edges are followed in
their direction.

G is **acyclic** if there are no directed
cycles.

The **transitive** **closure** of digraph G is the digraph
G* such that the vertices of G* are the same as G and if *u*
reaches *v* in G then (*u*, *v*) is an edge in G*.

The digraph traversals are similar to graph traversals; we only traverse in the direction of the edges.

**Algorithm:** DirectedDFS(Vertex *v*)

Mark vertexvas visitedforeach outgoing edge (v,w) ofvdo

ifvertexwhas not been visitedthen

recursively call DirectedDFS(w)

The directed DFS(*s*) will visit all the vertex that *s*
reaches. The time is O(*m _{s}* +

The algorithm creates a spanning tree from the *discovery*
edges. The edges that are not members of the *spanning*
*tree* can be labeled:

back- if the edge leads to an ancestor in the spanning treeforward- if the edge leads to a descendant in the spanning treecross- otherwise.

While finding the reachable vertices we can build the transitive
closure of G. Adding edges to the new digraph G* as new
vertices are reached. The time is O(*n*^{2}).

We can also determine if the di-graph is strongly connected by
running DFS for all vertices of G. All DFS should visit all
vertices of G. The time is again O(*n*^{2}).

Actually this test is not the most efficient. We could do
DFS(*s*) where s is a arbitrary vertex of G. If not all
the vertices of G have been visited then G is not strongly
connected. If all the vertices are visited then reverse the
direction of all the edges and performed a DFS(*s*) if this
search finds all the vertices of G then G is strongly connected.
What we have determined is:

anyv→s→ anyv

s→ anyv: is the original call of DirectedDFS

anyv→s: is the call of DirectedDFS with reverse direction for the edges

So all vertices can get to any vertex via *s*. The time
is O(*n+ m*).

A directed acyclic graph (DAG) is a directed graph with out cycles.

Inheritance between Java classes

Prerequisites between courses in computer science degree

Scheduling of tasks, without dead lock

A **t opological**

Use

**Proof by construction. **The trick is that an *topological
ordering * must have a vertex with **in**-**degree**
equal to **zero**. The vertex is the start of the
ordering. We keep track of the in-degree of each vertices
in a separate array, incounter(*v*). We look for vertex
with *incounter* equal to zero this becomes the start of
the sequence then for all the outgoing edges to vertex *w *we
subtract one from incounter(*w*) and look for a vertex with
incounter equal to zero that will be the next vertex in the sequence.

**Algorithm:** TopologicalSort(G)

let S be initially empty
stack **for** each vertex *u* of G **do**

let incounter(u) be the in-degree ofuifincounter(u) == 0then

S.push(u)

**while** S is not empty **do**

u= S.pop()

letube vertex numberiin the topological orderingi=i+1foreach outgoing edge (u,w) ofudo

incounter(w) = incounter(w) - 1ifincounter(w) = 0then

S.push(w)

The time is O(*n + m*) and uses space O(*n*) for
the stack.