加重対。重み付けされていないグラフ
1. 序章
このチュートリアルでは、加重グラフと非加重グラフについて説明します。 それらがどのように異なるかを説明し、コンピュータープログラムでそれらをどのように表現できるかを示します。
2. グラフとは何ですか？
グラフは接続されたオブジェクトのコレクションです。 それらは、純粋に数学的な概念から現実世界のオブジェクトや現象まで、何でもかまいません。 たとえば、家族の絆を持つ人々のコレクションはグラフです。 道路で相互接続された一連の都市もそうです。
通常、グラフのオブジェクトをノードまたは頂点と呼び、それらの間の接続をエッジまたはアークと呼びます。たとえば、これは都市と道路のグラフを視覚化する方法です。
各ノードは都市を表し、各エッジはある都市から別の都市への道路を表します。
3. 重み付けされていないグラフ
2つのノードが接続されているかどうかだけを気にする場合は、そのようなグラフを重み付けなしと呼びます。それらの間にエッジがあるノードの場合、それらは互いに隣接または隣接していると言います。
3.1. 隣接行列
隣接行列を使用して重み付けされていないグラフを表すことができます。これは、0と1で構成される行列です。ここで、はノードの数です。 その要素が1の場合、それは-番目と-番目のノードの間にエッジがあることを意味します。 の場合、2つのノード間にエッジはありません。
上記のロードマップグラフの隣接行列は次のようになります。
すべての無向グラフの場合と同様に、対称です。
行列表現には2つの仮定があります。
- ノードから整数にマップし、すべてのノードに一意の整数を割り当てることができます。 （この例では：。）
- ノードの数は、メモリが行列用に連続するスペースを予約するのに十分な大きさになるようなものです。
これらの仮定が成り立たない場合、またはグラフがまばらな場合は、隣接リストを使用します。
3.2. 隣接リスト
ノードごとに、隣接ノードのリンクリストを維持します。
この表現の主な利点は、グラフを格納するためのスペースが連続している必要がないことです。 ただし、行列表現の非常に便利なプロパティが失われます。これがアクセス複雑性です。
との値に関係なく、一定時間でアクセスすることにより、-番目と-番目のノードの隣接に関する情報を読み取ることができます。 リンクリストを使用すると、リスト全体をトラバースできます。 最悪の場合、-番目のノードはすべての頂点に隣接しますが、クエリの-番目の頂点は隣接します。 したがって、リンクリストの項目をチェックして、2つのノードが接続されていないと結論付けます。
4. 加重グラフ
重み付けされていないグラフは、2つのノードがリンクされている場合にのみ表示されます。 したがって、次のようなクエリに適しています。
- ノードとノードの間にパスはありますか？
- どのノードから到達可能ですか？
- との間の最短経路上にノードはいくつありますか？
ただし、多くのアプリケーションでは、エッジには、目前の問題を解決するためにアルゴリズムで利用する必要のある数値プロパティがあります。たとえば、を探す際には、道路の長さと交通密度を考慮する必要があります。 2つの都市間の最短経路。 したがって、各エッジを、その重みと呼ばれる実際の値に関連付けます。 このようなグラフを加重と呼びます。
エッジの重み、つまり道路の長さを含めると、ロードマップグラフは次のようになります。
ノードと同様に、重みは、長さ、密度、期間、コスト、確率など、目前の問題に関連するものであれば何でもかまいません。
4.1. 加重グラフの表現
加重グラフを表現する方法は、加重されていないグラフの表現を拡張したものです。
重み行列は、要素が-番目と-番目のノード間のエッジの重みを表す実数行列です：
通常、実際のエッジの重みは正であるため、ゼロは2つのノード間にエッジが存在しないことを示します。 ただし、アプリケーションがそのようなものである場合、重みは負になる可能性があります。 その場合、マトリックスにエッジがないことを示す特別なシンボルを定義する必要があります。
リンクリストを介してグラフを表す場合、これらのリストの隣接リストと一緒にエッジの重みを格納する必要があります。
4.2. 加重グラフの特殊なケースとしての非加重グラフ
重み付けされていないグラフでさえ、重み付けされていると見なすことができますが、特別な重み関数があります。
さらに、重みがすべて同じであるか、パスのコストが通過するノードの数のみに依存し、それを計算する式がある場合、重み付き表現を使用する必要はありません。 隣接行列でグラフアルゴリズムを実行し、後で重みを使用して解を導出できます。
4.3. 明示的vs。 暗黙のグラフ
重み付けされたグラフと重み付けされていないグラフはどちらも、明示的または暗黙的にすることができます。 明示的なグラフは、十分なスペースがあれば、ノードとエッジを列挙してメインメモリまたはセカンダリメモリに保存できるグラフです。 したがって、アルゴリズムを実行する前に、明示的なグラフ全体が作成されます。 都市と道路のグラフは、明示的なグラフの例です。
ただし、グラフが非常に大きいか複雑であるため、事前に作成できない場合があります。 代わりに、グラフを探索しながら拡大し、必要な部分のみを作成する手順があります。 。このようなグラフは暗黙的なグラフとして知られています。 多くの探索問題には無限の探索空間があるAIでよく使用されます。 各候補解は手元の検索グラフのノードであり、隣接する解を見つけたい場合は、その場で隣接するものを計算する関数を使用します。
明示的グラフと暗黙的グラフの違いは、熱心なグラフと遅延読み込みの違いに似ています。
5. 結論
この記事では、重み付けされていないグラフと重み付けされたグラフについて説明しました。前者のタイプのグラフは、2つのオブジェクトがエッジを介して直接接続されているかどうかだけを知る必要があるアプリケーションに適しています。 後者は、エッジにコストや長さなどの重みが関連付けられている場合に使用します。
