Pythonで有向グラフにおける最大の色の値を見つけるプログラム

この問題では、n個の色付きノードとm個の異なるエッジから構成される有向グラフが与えられます。ノードには0からn-1までの番号が付けられています。小文字アルファベットのみで構成された文字列colがあり、col[i]はグラフ内のi番目のノード（0インデックス）の色を表します。さらに、edges[j] = (u, v)という形式のエッジリストが与えられ、ノードuからノードvへ向かう有向エッジが存在することを示します。

グラフにおける「有効なパス」とは、ノードの系列 x₁ から xₖ までの並びであり、隣接する任意の xᵢ と xᵢ₊₁ の間に、xᵢ から xᵢ₊₁ へ向かう有向エッジが存在するものを指します。パスの色とは、そのパス上で最も多く出現するノードの色のことです。この記事では、グラフ内の任意の有効なパスの中で最大の色の値（最頻色の出現回数）を求めます。ただし、グラフにサイクル（閉路）が存在する場合は -1 を返します。

たとえば、入力が col = "aabada"、edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)] の場合、出力は 4 になります。これは、パス 0 → 1 → 2 → 3 → 5 において色 'a' が合計4回出現する longest path となるためです。

解決のためのアルゴリズム

この問題は、トポロジカルソートと動的計画法（DP）を組み合わせることで効率的に解けます。dp[i][c] を「ノード i で終わるパスにおける色 c の最大出現回数」と定義します。具体的な手順は以下の通りです。

• n := col のサイズ
• graph := エッジリストから構築した隣接リスト形式のグラフ
• indegree := 各ノードとその入次数を格納するマップ
• queue := 処理待ちノードを管理する新しいリスト
• dp := サイズ n × 26 の二次元配列を作成し、すべて 0 で初期化
• colorvalues := col の各文字 c を、アルファベット順のインデックス（a=0, b=1, ...）に変換したリスト
• u を 0 から n-1 まで繰り返す：
• u が indegree に存在しない（入次数が0）場合：
• queue の末尾に u を追加する
• dp[u][colorvalues[u]] := 1 と設定する
• visited := 0（処理済みノード数のカウンタ）
• queue が空でない間、以下を繰り返す：
• u := queue から先頭要素を取り出して削除する
• visited := visited + 1
• graph[u] 内の各 v について：
• c を 0 から 25 まで繰り返す：
• dp[v][c] := dp[v][c] と (dp[u][c] ＋ (c が colorvalues[v] と一致すれば 1、 otherwise 0)) の最大値で更新する
• indegree[v] := indegree[v] - 1
• indegree[v] が 0 になった場合：
• queue の末尾に v を追加する
• indegree から v を削除する
• visited < n の場合、グラフ内にサイクルが存在するため -1 を返す
• dp 配列全体の最大値を返す

この手法の計算量は、ノード数を n、エッジ数を m とすると O(n×26 + m×26)、空間計算量は O(n×26) となり、非常に効率的です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from collections import defaultdict

def solve(col, edges):
    n = len(col)
    graph = defaultdict(list)
    indegree = defaultdict(int)

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    queue = []
    dp = [[0]*26 for _ in range(n)]
    colorvalues = [ord(c) - ord("a") for c in col]
    
    for u in range(n):
        if u not in indegree:
            queue.append(u)
            dp[u][colorvalues[u]] = 1

    visited = 0
    while queue:
        u = queue.pop()
        visited += 1

        for v in graph[u]:
            for c in range(26):
                dp[v][c] = max(dp[v][c], dp[u][c] + (c == colorvalues[v]))
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
                del indegree[v]

    if visited < n:
        return -1
    return max(max(x) for x in dp)

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))

入力

"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]

出力

4

まとめ

本記事では、色付きノードを持つ有向グラフにおいて、有効なパス上の最頻色の最大出現回数を求める問題を扱いました。トポロジカルソートによる処理順序の確保と、26色分のDPテーブルを更新するアプローチにより、サイクル検出も含めて線形時間で解くことができます。同様の手法は、依存関係のあるタスク処理やDAG上での最適化問題など、幅広い場面で応用できる有用なパターンです。