Pythonで全ノードに到達可能な最小の頂点集合を見つけるプログラム

問題概要

有向非巡回グラフ(DAG)を考えます。グラフにはn個の頂点があり、各ノードには0からn-1までの番号が付けられています。グラフはエッジリストとして表現され、edges[i] = (u, v)はノードuからノードvへ向かう有向エッジを意味します。このとき、そこから出発すればグラフ内のすべてのノードに到達できるような、最小の頂点集合を見つける必要があります(頂点は任意の順序で返して構いません)。

例えば、入力が次のような場合を考えてみましょう。

この場合、出力は [0, 2, 3] となります。これらの頂点は他のどの頂点からも到達できないため、ここから探索を開始すれば全ノードをカバーできるからです。

解決のアプローチ

鍵となるのは「入ってくるエッジを持たない頂点」に着目することです。ある頂点が別の頂点から到達可能であるなら、必ずどこかからの有向エッジの終点になっているはずです。逆に言えば、どのエッジの終点にもなっていない頂点は、他の頂点から辿り着くことができません。したがって、求めるべき答えは「エッジリスト中に一度も終点として現れない頂点」の集合と一致します。

具体的には、以下の手順で解くことができます。

• n := エッジリストのサイズ
• all_nodes := 0からn-1までのすべての頂点を含む集合を作成
• v := 空の集合を作成
• edges内の各エッジ(i, j)について、終点であるjをvに追加
• ans := all_nodesからvに含まれる要素を除外した差集合
• ansを返す

実装例

それでは、実際のコードを見て理解を深めましょう。

def solve(edges):
    n = len(edges)
    all_nodes = set(range(n))
    v = set()
    for edge in edges:
        v.add(edge[1])
    ans = all_nodes - v
    return ans

edges = [(0,1),(2,1),(3,1),(1,4),(2,4)]
print(solve(edges))

入力

[(0,1),(2,1),(3,1),(1,4),(2,4)]

出力

{0, 2, 3}

計算量について

このアルゴリズムは、エッジリストを一度走査するだけなので、時間計算量はO(E)(Eはエッジ数)、空間計算量はO(V)(Vは頂点数)となり、非常に効率的です。集合演算を活用することで、簡潔かつ高速に最小の起点となる頂点集合を求められます。