鉄道・道路・航空などの交通、通信・電気・ガス・水道などのインフラストラクチャなどなど、我々の生活にネットワークは欠かせません。ネットワークに対して行う処理は多岐にわたり、アルゴリズムの研究と応用の代表的分野になっています。前回に打ち上げた「アルゴリズムアニメーション」実例としてネットワークアルゴリズムを取り上げます。これからの説明は前回紹介した程度の教科書・参考書を一応見た方に、理解を確実にしていただくことを想定しています。まったく初めてという方はまず教科書を一読願います。
いろんなネットワークがありますが、その本質は(V, E, w)という3つ組みで表現できます。V は頂点の集合、EはV✖️Vの部分集合で辺の集合、wはEからR(実数の集合)かN(自然数の集合)への関数で辺の重みを示します。(V, E) だけで w は考慮しない時はグラフと言います。次にネットワークの例を示します。
ここでは
- V={a,b,c,d,e,f}
- E = {(a,b), (a,c), (b,c), (b,d), (c,a), (d,f), (d,e), (e,b), (e,c), (e,f), (f,e)}
- w(a,b) = 4 など、あとは省略
となります。このネットワークは辺に矢印があり方向がついているので、有向ネットワーク(グラフ)と言います。辺の向きを無視した無向ネットワーク(グラフ)もあります。
ネットワーク(グラフ)について多くの問題が昔から研究されており、多くのアルゴリズムがあります。次のリストはほんの一例です。
- 探索(幅優先、深さ優先)
- 最短路
- 最大フロー
- 最小スパニング木
- 2連結成分
- マッチング
- オイラー閉路
- ハミルトン閉路
- 巡回セールスマン(重みの和最小のハミルトン閉路)
- 頂点彩色/辺彩色
これらの問題(の一部)を解くアルゴリズムをアニメーションで(動作のひとこまひとこまを逐次示す)お見せします。その前に例題としてネックワークを作らなくてはけ ません。そこで
という機能を持つプログラムを作りました。A は一定で、B のアルゴリズムは様々なネットワークアルゴリズムに取り替えがきくよう作ってあります。有向/無向どちらのネットワークにも対応しています。ネットワークを作るところの動画へのリンクです。
探索アルゴリズム(辺をたどって行ける頂点をピックアップする)は最初に取り上げるのに向くアルゴリズムです。入力はネットワーク(重みはいらないのでグラフで良い)と出発点の頂点です。幅優先探索と深さ優先探索があります。幅優先は各頂点xの幅優先探索番号 fw(x) を出力します。fw(x) は初めはすべて0になっています。アルゴリズムは次のように表現されます。
ここでqはキュー(待ち行列)という記憶装置、cは補助変数、! は論理否定を表します。キューについて説明する前に深さ優先探索を紹介します。深さ優先探索は各頂点xの深さ優先探索番号fd(x)を出力します。fd(x)は初めは全て0になっています。
非再帰版で使っているsはスタックという記憶装置です。次の図に示す通り、キューは「先入先出」、スタックは「先入後出し」で内容を管理します。
q.top(), s.top() はキューやスタックの次に出力すべきデータ項目を読み出す関数です。その項目はそのまま残ります。消すときはq.delete(), s.delete()を使います。q.isempty(), s.isempty()はキューやスタックが空(データが一つもない)どうか返す関数です。もちろん、空の時、真(true)が返ります。 再帰呼び出しはコンピュータ(プログラミング言語とコンパイラ)の側でスタックを使って実現されますから、再帰呼び出し版は内部でスタックを使っているのです。探索のアルゴリズムアニメーションはこちらでみることができます。
