fc2ブログ



グラフの表現

2006.04.19 18:10  グラフ

グラフはコンピュータ上で表されるデータ構造の一種です。コンピュータの中で、問題に応じたグラフ構造を効率的に表現し操作されるようなプログラムを実装しなければなりません。

プログラム上でグラフを表現し操作する代表的な方法に、
隣接行列 (adjacency matrices)による表現と、
隣接リスト (adjacency lists)による表現があります。

これらの方法とその特徴を簡単に紹介します。

スポンサーサイト



| コメント(1) | トラックバック(0) | ↑ページトップ |




グラフの種類

2006.04.19 18:09  グラフ

グラフの種類には大きく分けて4つあります。

名前 特徴
無向グラフ エッジに方向がない
有向グラフ エッジに方向がある
重みつき無向グラフ エッジに重みがあり、方向がない
重みつき有向グラフ エッジに重みがあり、方向がある


無向グラフの例

友達関係をグラフにした例です。この例ではエッジに方向をもたせていません。例えば、「友達の友達は友達としたとき、A君とB君は友達ですか?」や「いくつの友達グループがありますか?」などの問題が考えられます。

graphExample1.gif

有向グラフの例

物事の手順をグラフにした例です。朝起きてから学校に行くまでの簡単な手順を示していますが、このグラフから様々な要素が読み取れます。例えば、朝起きてから朝食を食べなくても学校へ行けますが、着替えなければ学校には行けないことが分かります。起きて→着替えて→学校へ行く、というのがこの手順の最短経路となります。

graphExample2.gif

重みつき無向グラフの例

各ノードが市町を表し、エッジが市町を行き来するのにかかる時間を表しています(架空のもの)。ある町からある町への最短経路を求めたいなどの類の問題はよくあります。

graphExample3.gif


ここで取り上げたものは、ほんの例でしかありません。「すべての問題はグラフで表せる」と言われるほど、グラフ構造は様々な問題で応用されます。

| コメント(0) | トラックバック(0) | ↑ページトップ |




グラフとは

2006.04.19 18:09  グラフ


グラフ(Graph)とは「対象の集合と、それらのつながりの集合」を表すためのデータ構造で、様々な問題に応用されます。現実世界のあらゆる問題をモデル化することができるので、グラフに関する重要なアルゴリズムが数多く存在します。

簡単なグラフの例を以下に示します。


graph.gif



「対象」はノード(node)またはバーテックス(vertex)と呼ばれ、上図の円に相当します。「つながり」はノードとノードの関係を表し、エッジ(edge)と呼ばれ、上図で円と円を結んでいる線に相当します。

グラフには様々な種類があり、問題によって応用の方法も違ってきます。

| コメント(0) | トラックバック(0) | ↑ページトップ |




キュー (待ち行列) Queue

2006.04.19 17:03  データ構造

キューは「待ち行列」とも呼ばれ、データを到着順に処理したいときに使用するデータ構 造で、データの中で最初に入ったものが最初に取り出される、先入れ先出し(FIFO: First In First Out)のルールに従ってデータを管理します。スーパーのレジやATMの待ち行列にお ける人々の動きやそこにある暗黙のルール(割り込みや追い越しの禁止)は、キューのデー タ構造そのものです。

キューの操作
  • enqueue(x): キューの末尾に要素 x を追加します。
  • dequeue(): キューの先頭から要素を取り出します。
  • isEmpty(): キューが空かどうかを調べます。
  • isFull(): キューが満杯かどうかを調べます。

実用的なキューには、これらの他にもキューの先頭の要素を参照したり、キューに指定され たデータが含まれているかを調べたりするオプション的な操作も含まれますが、ここでは上 記4つの操作を含むキューを実装します。

キューの制約
  • データの中で最初に入ったものが最初に取り出されます。


整数型のデータが格納されるキューを配列を用いて実装します。以下に、実装に必要なもの を示します(下図参照)。

array queue


データを格納するための整数型1 次元配列: buffer
配列buffer の各要素にエンキューされたデータを格納していきます。問題に応じた十分な 記憶領域を確保することが必要です。Fig.4.3-1 では、既にいくつかの要素が格納されてい ます。

先頭カーソルである整数型変数:head
キューの先頭の場所を指し示す変数です。dequeue されるとhead で指された要素が取り出 されます。キューの先頭の要素のインデックスが0 とは限らないことに注意して下さい。

末尾カーソルである整数型変数:tail
キューの末尾+ 1 の場所(最後の要素の隣)を指し示す変数です。tail は新しい要素が追加 される場所を示します。

実際にキューのデータ構造を操作する様子を見てみましょう。Fig. 4.3-2は、実際にキューに適当な値を適当に出し入れしている様子を示しています。

array queue 初期化: head = tailのときキューが空になります。初期値はhead = tail = 0とします。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 3 )。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 7 )。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 1 )。

dequeue: headが指す要素を取り出し、headを1増やします (例: 3を取り出す)。

enqueue(x): tailが指す場所にxを追加し、tailを1増やします (例: x = 8 )。

dequeue: headが指す要素を取り出し、headを1増やします (例: 7を取り出す)



このように配列によってキューを実装すると、上図に示すように、データの追加と取り出し操作を繰り返すことによって、headとtailに挟まれたキューのデータ本体が配列の末尾に向かって(図の右側に)移動していき、すぐに要領をオーバーしてしまいそうに見えます。

下図に示すように、dequeueされたときにheadを常に0に保つようにデータ全体を配列の先頭に(左に)向かってシフトしていては、dequeueの度にO(n)の計算が必要になってしまいます。一方で、tailが配列の領域を超えた時点でoverflowとしてしまったのでは、まだ使える配列の領域を無駄にしてしまいます。

array queue shift

これらの問題を避けるために、配列によるキューの実装ではFig.4.3-4に示すように、配列をリングバッファとみなしてキュー内のデータを管理します。

array queue ring

リングバッファとは通常の1次元配列で実現しますが、キューの範囲を指し示すカーソルheadまたはtailが配列の領域を超えてしまったときにこれらのカーソルを循環させます。つまり、カーソルを1つ増やして、それが配列の範囲を超えてしまった場合には、カーソルを0にリセットします。

上図は既にいくつかのデータが格納されたキューにデータを出し入れしている様子を示しています。最初に1を追加したときに、tailの値が1つ増えますが、配列の領域を超えてしまうので、tailを0に設定します。リングバッファを時計回りに見ると、キューにデータがある場合は必ずhead→tailの順番に並びます。

次のは配列によってキューを実現し、キューへのデータの追加・取り出しをシミュレーションします。



main関数
キューのオブジェクトqueueを操作します。無限ループによってキーボードからコマンドcommandの入力を待ち続けます。commandがenqueueであればxを読み込みそれをqueueに追加します。commandがdequeueであればqueueからデータを取り出し、それを出力します。それ以外のcommandが入力されたときループから抜けプログラムが終了します。

initialize
queue を空にします。queue が空のときhead とtail が同じ位置を示します。ここでは初期 値を0 と設定します。

isEmpty
queue が空の場合真を返します。head とtail が同じ値のときキューが空となります。

isFull
queue が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されていま す。head が(tail+1)%MAX に等しいとき、queue が満杯になります。リングバッファを時 計回りに見ると、tail → head の間は常に1 つ以上の空きがあります。

enqueue(x)
queue が満杯の場合は”overflow” と出力します。そうでなければ、tail が指す場所にx を追 加します。queue の要素が1 つ増えたのでtail を1 増やします。ただし、増やした値が配 列の容量であるMAX 以上になってしまう場合はtail を0 として循環させます。

dequeue
queue が空の場合は”underflow” と出力します。そうでなければ、head が指すqueue の先 頭の要素を変数x に一時記録し、head を1 増やしてからx を返します。ただし、head を 増やした値がMAX 以上になってしまう場合はhead を0 として循環させます。

| コメント(1) | トラックバック(0) | ↑ページトップ |




スタック Stack

2006.04.19 17:02  データ構造

スタックは一時的にデータを退避したいときに有効なデータ構造で、データの中で最後に 入ったものが最初に取り出される後入れ先出し(LIFO: Last In First Out)のルールに従いデー タを管理します。例えば、以下の何気ない日常の行動が、スタックのデータ構造をうまく表 現してくれます。

テストの勉強中で以下のような一連の行動をとった場面があるかもしれません。
  • 1. 英語の教科書を読む
  • 2. 分からない単語があったので、辞書を引く
  • 3. 辞書を引いている途中で、友達からメールがキタのでメールを書く
  • 4. メールの返信が終わったので、辞書を引きなおす
  • 5. 単語を理解したので、教科書の続きを読む
  • 6. 教科書を読み終える

この行動の流れをスタックで表わすと以下のようになります:

stack.gif

積み木のように「行動」が順番に重なっていきます。積み木の最上部が進行中の行動で、そ の下にあるもの全てが中断されている行動になります。この例での重要なポイントは、例え ばステップ4 でメールを返信した後に教科書を読むのではなく、メールの対応によって中 断されていた「辞書を引く」ことに戻るということです。

このように、コンピュータにおいても処理していたことを一時的に退避させ、適時それを取 り出して正しい順番で続行しなければならない場面は多くあります。この例では、もし順番 が乱れて単語の意味を理解しないまま教科書を読もうとしてもつまづいてしまいます。この ような行動をコンピュータにおけるデータや処理と置き換えたものが、スタックのデータ構 造です。

スタックの操作
  • push(x): スタックの先頭(頂点)に要素 x を追加します。
  • pop(): スタックの先頭(頂点)から要素を取り出します。
  • isEmpty(): スタックが空かどうかを調べます。
  • isFull(): スタックが満杯かどうかを調べます。

スタックの制約
  • データの中で最後に入ったものが最初に取り出されます。

スタックやその他のデータ構造の実装には配列やリストを使ったものなどいくつかの方法があります。ここでは、データ構造の操作と制約の理解に重点をおきますので、簡単な例を通して1つの実装方法を示します。整数型のデータが格納されるスタックを配列を用いて実装します。以下に、実装に必要なものを示します(下図参照)。

データを格納するための整数型1次元配列: buffer
配列bufferの各要素にプッシュされたデータを格納していきます。問題に応じた十分な記憶領域を確保することが必要です。また、便宜上 0 番目には常に何も入れないようにします。Fig. 4.2-2は、容量が7のスタックに既に5つの要素が格納されている様子を表しています。

array stack

スタックポインタである整数型変数: top
スタックの頂点の要素(一番最後に追加された要素)を指し示す整数型の変数です。この変数をスタックポインタといいます。またtop の値はスタックの要素数をも示します。

実際にスタックのデータ構造を操作する様子を見てみましょう。Fig. 4.2-3は、実際にスタックに適当な値を適当に出し入れしている様子を示しています。データ構造の操作は動的に発生するものなので、スタックの要素は変動していきます。

array stack 初期化: top = 0としてスタックを空にします。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 3 )。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 12 )。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 1 )。

pop: topが指している要素を取り出し、topを1減らします (例: 1を取り出す)。

pop: topが指している要素を取り出し、topを1減らします (例: 12を取り出す)。

push(x): top を1増やし、topが指す場所にxを追加します (例: x = 5 )

以下のプログラムは配列によってスタックを実現し、スタックへのデータの追加・取り出しをシミュレーションします。プログラムは、”push x” (xは整数)とキーボードから入力されると、スタックにxを追加し、”pop” と入力されると、スタックの頂点の要素を取り出しそれを出力します。これら以外の形式が入力されたときプログラムが終了します。
スタックのデータ構造はクラスとして実装されています。クラスとしてデータ構造を実装しておけば、それらを部品として使えるので、プログラムで複数の異なるスタックを使いたい場合などに便利になります。


main 関数
スタックのオブジェクト(※ 1)stack を操作します。無限ループによってキーボードから コマンドcommand の入力を待ち続けます。command がpush であればx を読み込みそれ をstack に追加します。command がpop であればstack からデータを取り出し、それを出 力します。それ以外のcommand が入力されたときループから抜けプログラムが終了します。

initialize
stack を空にします。stack が空のときはtop が0 を指します。

isEmpty
stack が空の場合真を返します。top が0 のときstack が空の状態になります。

isFull
stack が満杯の場合真を返します。プログラムではbuffer の容量がMAX で定義されています。 top がMAX 以上のときにstack が満杯の状態になります。

push(x)
stack が満杯の場合は”overflow” と出力します。そうでなければ、top を1 つ増やし、その 場所にx を追加します。

pop
stack が空の場合は”underflow” と出力します。そうでなければ、stack の頂点の要素を変数 x に一時記録し、top を1 減らしてからx を返します。



普通は、以下のように便利なライブラリを使います。



練習問題1

see-try-see

| コメント(0) | トラックバック(0) | ↑ページトップ |




データ構造

2006.04.19 17:01  データ構造

データ構造とは、プログラムの中でデータを一定の形式に系統立てて格納するときの形式です。プログラムの中で、どのようなデータ構造を用いたかが、そこで実装されたアルゴリズムの効率に大きく影響します。 データ構造は、
  • 「データの集合」
  • 「データの集合に対する操作」
  • 「データをルールに従って正しく保つための制約」

から成りたっています。

これから記録していきたいデータ構造↓

  • スタック Stack
  • キュー Queue
  • 優先順位キュー Priority Queue
  • Disjoint Sets
  • 二分探索木
  • etc.

| コメント(0) | トラックバック(0) | ↑ページトップ |