読み方：ゆうこうグラフ

有向グラフ【directed graph】

有向グラフとは？

点とそれらを結ぶ線からなるグラフ構造のうち、各線に向きが定められているもの。線は始点と終点を持ち、関係の方向性を表現できるため、順序や因果関係を伴う対象の表現に用いられる。

グラフ理論では、複数の頂点（ノード）を辺（エッジ）で繋いだ構造について考察する。有向グラフでは辺に向きがあり、頂点AからBへ向かう辺と、BからAへ向かう辺は別の辺として区別する。

有向グラフにおける辺は「有向辺」または「弧」という。ある頂点から別の頂点へ向かう辺が存在する場合、始点から終点へ移動可能であることを意味するが、逆方向の移動は別の辺が存在しない限り認められない。これにより、到達可能性や依存関係を厳密に表現できる。

有向グラフでは、頂点に入ってくる辺の数を「入次数」、外へ出ていく辺の数を「出次数」と呼び、各頂点の役割や位置関係を把握する指標として用いられる。また、ある頂点から出発して同じ頂点に戻ってくる循環的な経路を「閉路」と呼び、閉路の有無によって性質が変化する。閉路を持たない有向グラフは「有向非巡回グラフ」（DAG：Directed Acyclic Graph）と呼ばれ、処理の順序決定や依存関係の整理に用いられる。頂点を順序付けするトポロジカルソートは、このような構造に対して定義される操作である。

有向グラフによる表現が適している対象の例として、プログラムの制御フロー、タスクの依存関係、交通網の一方通行路、Webページ間のリンク関係などが挙げられる。ネットワーク解析では、頂点間の経路探索や最短経路問題が扱われ、アルゴリズムとして幅優先探索や深さ優先探索、ダイクストラ法などが利用される。プログラム実装上のデータ構造としては隣接行列や隣接リストが用いられ、扱う頂点数や辺数に応じて選択される。