Warning
このページは歴史的理由でここに残り、古いまたは間違った情報が含まれているかもしれません。
Change notes: 2/22/98, 3/2/98, 12/4/00: このバージョンのエッセイでは、コードのいくつかのバグが修正されています。 6/10/19: find_shortest_path を「ほぼ最適」としたのを撤回。 8/11/19: find_path()
Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.
の代わりに find_graph() を誤って使ってしまったのを修正。グラフは、辺や円弧で結ばれたノードからなるネットワークです。 無向グラフでは、ノード間の接続は方向を持ち、アークと呼ばれる。 ここでは、主に有向グラフについて説明します。 グラフのアルゴリズムには、2つのノード間の経路を求める、2つのノード間の最短経路を求める、グラフのサイクルを求める（サイクルはノードからそれ自身への空でない経路）、すべてのノードに到達する経路を求める（有名な「巡回セールスマン問題」）などがある。 グラフのノードやアークに重みやコストがある場合もあり、最も安い経路を見つけることに興味がある。
グラフアルゴリズムについてはかなりの文献があり、離散数学の重要な部分である。 グラフはまた、コンピュータのアルゴリズムにおいても多くの実用的な用途を持っています。 明らかな例はネットワークの管理に見られるが、他の多くの分野でも例が豊富である。 例えば、コンピュータプログラムの呼び出し側と受け手側の関係はグラフとして見ることができる（ここで、サイクルは再帰を、到達不可能なノードはデッドコードを表す）。 しかし、グラフはリストや辞書から簡単に作ることができます。 例えば、次のような簡単なグラフがあります（この列では図が使えないので、グラフの円弧を書き出します）：
A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C
このグラフには6つのノード（A-F）と8つの円弧があります。 これは次のようなPythonのデータ構造で表現できます。
graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }
これはグラフのノードをキーとする辞書です。 各キーに対応する値は、このノードから直接アークで接続されているノードを含むリストである。
2つのノード間の経路を決定する簡単な関数を書いてみましょう。 グラフと開始ノード、終了ノードを引数にとります。 パスを構成するノード（開始と終了のノードを含む）のリストを返す。 パスが見つからない場合は、Noneを返す。返されたパスには、同じノードが2回以上現れることはない（つまり、サイクルを含まない）。 このアルゴリズムは、バックトラックと呼ばれる重要なテクニックを使用します。解が見つかるまで、それぞれの可能性を順番に試します。
ユーザは3つの引数でfind_path()を呼び出すが、それ自身は4番目の引数で呼び出すことに注意すること。 この引数はサイクル(forループ内の最初の’if’)を避けるために使用される。 path = path + ” という代入は、新しいリストを作成する。 もし、「path.append(start)」と書いていたら、呼び出し側の変数「path」が変更され、悲惨な結果になっていただろう。 (タプルを使えば、このようなことが起こらないようにすることができますが、「(start)」はシングルトンタプルではなく、括弧で囲まれた式なので、「path = path + (start,)」と書かなければならないという代償を払うことになります。)
この関数を変更して、最初に見つけたパスの代わりに、すべてのパス (サイクルなし) のリストを返すようにするのは簡単です：
def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths
サンプル実行：
>>> find_all_paths(graph, 'A', 'D') , , ] >>>
別の変形では最短パスを見つける：
def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest
サンプル実行：
>>> find_shortest_path(graph, 'A', 'D') >>>
これらの関数は限りなくシンプルなものです。 しかし、（Pythonで書かれたコードとしては）ほぼ最適なものです。
UPDATE: Eryk Kopczyński は、これらの関数が最適でないことを指摘しました。 それどころか、「このプログラムは指数関数的に実行されるが、find_shortest_pathはBFSを用いれば線形時間で実行できる。 さらに、線形BFSはより単純である”
# Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)
これは、例えば, 'B'], 'D']のような奇妙なフォーマットでパスを返すことに注意する。 特にlen(find_shortest_path(graph, 'A', 'D'))は正しくない答え(2, 外側のリストの長さが2なので)を返します。 これは、追加をdist+ではなく, next]で行っているためです。 2 番目の方法は、4 分の 1 の時間とメモリを使用しますが、それでも比較的小さなグラフでは問題ないはずです。
もう 1 つのバリエーションは、データの抽象化をさらに追加することです。 これは構造化プログラミングの欲求に訴えるものですが、コードをより効率的にするものではありません（その逆です）。 しかし、ノードやアークに様々なラベルを付けたり、そのラベルを考慮したアルゴリズム（例えば、地図上の2つの都市間の最短経路を求めるなど）を追加することは容易になる。 これもまた、別のコラムで紹介する予定である
。