Pythonで辞書を使ってグラフを実装する方法｜隣接リストの作成から経路探索まで

Pythonの辞書によるグラフの実装

Pythonでは、辞書（Dictionary）を使ってグラフを簡単に実装できます。辞書では、各キーが頂点（Vertex）に対応し、その値として、その頂点に接続されている頂点のリストを保持します。この構造全体は、まさにグラフG(V, E)の「隣接リスト」と同じ形になります。

基本的なdictオブジェクトでも実装可能ですが、ここではdefaultdictを使用します。defaultdictには、存在しないキーへアクセスした際にデフォルト値を自動生成できるなど、通常の辞書にはない便利な機能が備わっています。

本記事では、頂点の数、辺の数、頂点名、そして辺のリストが記述されたテキストファイルを読み込んでグラフを構築します。無向グラフの場合は、(u, v)と(v, u)のように、同じ辺を両方向で記述します。

以下のグラフを例として使用します。

グラフの入力ファイルは次のようになっています。

Graph_Input.txt

6
8
A|B|C|D|E|F
A,B
B,A
A,C
C,A
B,D
D,B
B,E
E,B
C,E
E,C
D,E
E,D
D,F
F,D
E,F
F,E

まず最初に頂点名を読み取り、続いて辺の情報を1行ずつ読み込んでリストに格納していきます。

サンプルコード：グラフの生成

from collections import defaultdict

def create_graph(filename):
   graph = defaultdict(list)  # キーと対応するリストを持つ辞書を作成
   with open(filename, 'r') as graph_file:
      vertex = int(graph_file.readline())
      edges = int(graph_file.readline())
      vert_Names = graph_file.readline()
      vert_Names = vert_Names.rstrip('\n')  # 行末の改行文字を削除
      nodes = vert_Names.split('|')  # 頂点名を分割
      for node in nodes:  # 各頂点に対して空のリストを作成
         graph[node] = []
      # ファイルから辺を読み込み、リストに格納
      for line in graph_file:
         line = line.rstrip('\n')  # 行末の改行文字を削除
         edge = line.split(',')
         graph[edge[0]].append(edge[1])  # edge[0]が始点、edge[1]が終点
   return graph

my_graph = create_graph('Graph_Input.txt')
for node in my_graph.keys():  # グラフを表示
   print(node + ': ' + str(my_graph[node]))

出力結果

A: ['B', 'C']
B: ['A', 'D', 'E']
C: ['A', 'E']
D: ['B', 'E', 'F']
E: ['B', 'C', 'D', 'F']
F: ['D', 'E']

始点から終点への経路を1つ取得する

次に、このグラフG(V, E)に対する基本的な操作を見ていきましょう。まずは、始点（Source Vertex）から終点（Destination Vertex）への経路を1つ取得する方法です。以下のコードはその操作の一部です。実行するには、先ほどの方法でグラフを生成しておく必要があります。

サンプルコード

# 始点から終点への経路を検索する関数
def get_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest:  # 終点が見つかったら処理を停止
      return path
   for vertex in graph[src]:
      if vertex not in path:
         path_new = get_path(graph, vertex, dest, path)
         if path_new:
            return path_new
   return None

my_graph = create_graph('Graph_Input.txt')
path = get_path(my_graph, 'A', 'C')
print('Path From Node A to C: ' + str(path))

出力結果

Path From Node A to C: ['A', 'B', 'D', 'E', 'C']

始点から終点へのすべての経路を取得する

続いて、始点から終点までの考えられるすべての経路を取得する方法を見てみましょう。以下のコードはその操作の一部です。実行するには、先ほどと同様にグラフを生成しておく必要があります。

サンプルコード

# 始点から終点へのすべての経路を検索する関数
def get_all_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest:  # 終点が見つかったら処理を停止
      return [path]
   paths = []
   new_path_list = []
   for vertex in graph[src]:
      if vertex not in path:
         new_path_list = get_all_path(graph, vertex, dest, path)
      for new_path in new_path_list:
         paths.append(new_path)
   return paths

my_graph = create_graph('Graph_Input.txt')
paths = get_all_path(my_graph, 'A', 'C')
print('All Paths From Node A to C: ')
for path in paths:
   print(path)

出力結果

All Paths From Node A to C:
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'D', 'F', 'E', 'C']
['A', 'B', 'E', 'C']
['A', 'C']

始点から終点への最短経路を取得する

最後に、始点から終点までの最短経路を取得する方法を見ていきましょう。以下のコードはその操作の一部です。実行するには、これまでと同じ方法でグラフを生成しておきます。

サンプルコード

# 始点から終点への最短経路を検索する関数
def get_shortest_path(graph, src, dest, path = []):
   path = path + [src]
   if src == dest:  # 終点が見つかったら処理を停止
      return path
   short = None
   for vertex in graph[src]:
      if vertex not in path:
         new_path_list = get_shortest_path(graph, vertex, dest, path)
         if new_path_list:
            if not short or len(new_path_list) < len(short):
               short = new_path_list
   return short

my_graph = create_graph('Graph_Input.txt')
path = get_shortest_path(my_graph, 'A', 'C')
print('Shortest Paths From Node A to C: ' + str(path))

出力結果

Shortest Paths From Node A to C: ['A', 'C']