データ構造入門：有向グラフの深さ優先探索（DFS）と辺の4種類の分類

有向グラフにおける深さ優先探索（DFS）とは

無向グラフの場合と同様に、有向グラフ（ダイグラフ）に対しても深さ優先探索（DFS）を適用できます。ただし、有向グラフでは辺に向きが存在するため、探索の過程で現れる辺をいくつかの種類に分類できる点が大きな特徴です。

DFSアルゴリズムを実行すると、「DFS木」と呼ばれる木構造が形成されます。このとき、グラフ内の辺は以下の4種類に分類されます。

辺の4つの分類

• 木辺（Tree Edge：T） ― DFS木そのものに含まれる辺です。

• 前進辺（Forward Edge：F） ― 一連の木辺の経路と平行になる辺です。具体的には、DFS番号が小さい頂点から大きい頂点へ向かい、かつDFS完了番号が大きい頂点から小さい頂点へ向かう辺を指します。

• 後退辺（Backward Edge：B） ― DFS番号が大きい頂点から小さい頂点へ向かい、かつDFS完了番号が小さい頂点から大きい頂点へ向かう辺です。後退辺が存在する場合、そのグラフには閉路（サイクル）が存在することを意味します。

• 交差辺（Cross Edge：C） ― DFS番号が大きい頂点から小さい頂点へ向かい、かつDFS完了番号も大きい頂点から小さい頂点へ向かう辺です。木において祖先と子孫の関係にない頂点間をつなぐ辺に相当します。

具体例で学ぶDFSの実行手順

それでは、次のようなグラフを例に考えてみましょう。

頂点Aを始点としてDFSを実行し、各頂点にDFS番号とDFS完了番号を割り当てると、形成されるDFS木は以下のようになります。

探索結果と辺の分類

このDFSによる頂点の訪問順序は、A → B → F → D → G → C → E となります。探索の結果、各辺は次のように分類されます。

• 木辺：T = {(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

• 前進辺：F = {(A, G)}

• 後退辺：B = {(G, B)}

• 交差辺：C = {(G, D)}

このように、有向グラフのDFSでは探索中に得られるDFS番号と完了番号を比較することで、すべての辺を木辺・前進辺・後退辺・交差辺のいずれかに厳密に分類できます。特に後退辺の有無はグラフが閉路を持つかどうかの判定に直結するため、トポロジカルソートやサイクル検出などの応用において重要な概念となります。