Pythonで隣接行列を用いたグラフ探索

Pythonには、グラフの探索に便利なツールがいくつかあります。その中でも、隣接行列を用いた探索は特に効率的であり、大規模なグラフでも問題なく扱うことができます。

隣接行列とは？

隣接行列は、グラフを行列で表現する方法のひとつです。グラフに含まれる頂点の数を $n$ とすると、$n \times n$ の行列にグラフの情報を格納します。行列の $(i, j)$ 要素は、頂点 $i$ から頂点 $j$ への辺が存在する場合は1、存在しない場合は0とします。

隣接行列を用いた探索

隣接行列を用いた探索では、すべての頂点を一度に扱うことができるため、効率的に探索を行うことができます。具体的には、深さ優先探索や幅優先探索などが利用できます。

以下は、隣接行列を用いた深さ優先探索の例です。

def dfs(adj_matrix, start):
    visited = [False] * len(adj_matrix)
    stack = [start]

    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v)
            for i in range(len(adj_matrix)):
                if adj_matrix[v][i] == 1 and not visited[i]:
                    stack.append(i)

まとめ

Pythonを用いて、隣接行列を用いたグラフ探索を行うことができます。特に、大規模なグラフでも効率的に探索が可能であるため、重要なアルゴリズムの一つです。