TL;DR
頂点と、向きのある辺（弧）からなるグラフ。辺は頂点の順序対で表される。
なぜ必要か
「A から B へ」のように、向きのある関係を表せる。Wikipedia では、プログラムの実行経路を表す制御フローグラフ、有限状態機械を表す状態遷移図、ネットワークの流れを表すフローネットワークなどを応用例に挙げている。依存グラフも有向グラフである。
仕組み
Wikipedia によると、有向グラフは頂点の集合と、頂点の順序対である弧の集合からなる。ある頂点に入ってくる弧の数を入次数、出ていく弧の数を出次数と呼ぶ。
向きに沿ってたどると元に戻る道を有向閉路という。有向閉路のない有向グラフを DAG（有向非巡回グラフ）と呼ぶ。DAG の頂点は、すべての弧が前から後ろを向くように並べられ、これをトポロジカルソートと呼ぶ。