「グラフとは」の編集履歴（バックアップ）一覧に戻る

グラフとは - (2012/02/09 (木) 17:40:46) のソース

**グラフとは

&bold(){グラフ(graph)}とは、点の集合と辺の集合で構成されるものをいいます。
点は、&bold(){ノード(node)、頂点・節点(vertex)}と呼ぶこともあります。
線は、&bold(){辺・エッジ(edge)、枝(branch)、リンク(link)}と呼ぶこともあります。

今後の説明では、&bold(){ノード}と&bold(){エッジ}という言葉に統一して説明します。

なおグラフに関する詳しい説明はここではしないので詳しく知りたい人は、[[wikipediaのグラフ>>http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96]]をみるか、自分でググるなどしてください。

#image(graph1.gif)
図1.無向グラフ

上のようなものがグラフです。
上のグラフでs(スタート)からg(ゴール)へいくにはどの経路を通ればよいでしょうか？
s→a→b→g
s→a→b→c→g
の２つですね。

***有向グラフと無向グラフ
エッジに矢印(向き)があるグラフを&bold(){有向グラフ(directed graph)}といい、矢印のないグラフを&bold(){無向グラフ(undirected graph)}といいます。

#image(graph2.gif)
図2.有向グラフ

上のようなものが有向グラフです。矢印が片方しかないと一方通行です。
上のグラフでs(スタート)からg(ゴール)へいくには
s→a→b→c→g
の経路ですね。逆にg(ゴール)からs(スタート)にいくには
g→b→a→s
の経路となります。

***重みつきグラフ
グラフの辺に&bold(){重み(コスト:cost)}が付いているグラフを、&bold(){重み付きグラフ (weighted graph)}と呼びます。重みつきグラフには、有向重みつきグラフと無向重みつきグラフの二つに分類されます。
実際に問題を扱うときは、ほとんどが重みつきグラフです。

#image(graph3.gif)
図3.重みつきグラフ

上のグラフのエッジについている数字がコストです。このコストは、あるノードからあるノードまでの
かかる時間や距離を表していることが多いです。
例えば上のグラフでの数字はかかる時間(単位:分)だとします。
s(スタート)からg(ゴール)まで一番時間のかからない経路は
s→a→b→c→g
であり、かかる時間は７分ですね。


***グラフをデータとして扱うには？

ICPCの問題では、問題文が与えられて最短経路を求めなければならない問題があります。
このような問題を解くときこのグラフをどのようにデータとして扱うかが問題となります。
データとして扱う方法は２つあります。

一つ目は、n*nの&bold(){隣接行列(adjacency matrix)}に保持する方法です。
隣接行列はあるノードとあるノードがつながっているときそのエッジのコストを書きます。
本来の隣接行列はつながっていないノード間の要素は,0と書きますが、ここでは無限大(∞:infinity)とします。
無限大ということはあるノードからあるノードへつながっているエッジがないこと意味します。
また同じノード間(図3でいうとs-s間,a-a間)はコストを0とします。

以下が図3の重みつきグラフを行列で表したものです。
|   | s　| a　| b　| c　| g　|
| s | 0  | 1  | ∞ | ∞ | ∞ |
| a | 1  | 0  | 2  | ∞ | ∞ |
| b | ∞ | 2  | 0  | 3  | 6  |
| c | ∞ | ∞ | 3  | 0  | 1  |
| g | ∞ | ∞ | 6  | 1  | 0  |

無向グラフであれば必ず対称な行列となります。
上の行列を実際に扱うときは、二次元配列を使います。またC/C++では無限大という数は扱えないので
とても大きい数をいれます(100000とか),#define INF 1000000とするといいと思います。

しかしこの方法には大きな欠点があります。もしグラフが疎の場合(つまりノードの数の割にエッジが少ない場合)
と無駄が多くなります。ノードの数をnとするとエッジの数にかかわらずn*nの行列となるため、
ノード数が多い場合(数千個)くらいになると二次元配列で領域を確保できなくなり、
コンピュータ上でグラフを表現できなくなります。


グラフをデータとして扱う二つ目の方法が&bold(){隣接リスト}です。隣接リストではあるノードがどのノードにつながっているか
の情報だけを保持します(コストがある場合はコストも保持する)

図3の重みつきグラフの例でいくとsはaとつながっている、aはs,bとつながっているという情報を保持します。
以下が図3の重みつきグラフを隣接リストで表したものです。
s => a
a => s,b
b => a,c,g
c => b,g
g => b,c
こちらの方が保持するデータ量が少なくなります。そのためこちらでコーディングすることが多いです。

それでは具体的にデータとして扱う方法について考えます。
図3.重みつきグラフについてノードがa,b,cとアルファベットでは扱いにくいので、
ノードも番号(数字)として扱います。

#image(graph4.gif)
図4.ノードを番号にした重みつきグラフ

&bold(){あるノードがどのノードとつながっているか、つながっているノードとのエッジのコストがいくらか}
の２つの情報があれば問題なさそうです。
構造体を使って
 struct Node{
 	vector<int> to;		//どのノードとつながっているか
  	vector<int> cost;	//エッジのコスト 
 };
 //構造体の宣言
 struct Node node[100];//100はノードの数
としましょう。構造体が分からない人はググってください。vectorについては[[vectorの使い方]]を見てください。
図4のグラフにおいてノード番号2をこの構造体で表すと
|                                 |node[2].to[0]  |node[2].to[1]  |node[2].to[2]  |
|ノード2とつながっているノード番号| 1             | 3             | 4             |
|                                 |node[2].cost[0]|node[2].cost[1]|node[2].cost[2]|
|ノード2とノード?のエッジのコスト | 2             | 6             | 3             |


では実際にこのようにデータを入れることのできる関数を作ってみます。
例えばノードuからノードvにエッジを追加するとします。
 //エッジを追加する関数
 void addEdge(int v, int u, int weight, struct Node *node){
 	//ノードuはノードvとつながっている情報を入れる	
 	node[ u ].to.push_back( v );
 	//ノードuとノードvのエッジの重みを入れる
 	node[ u ].cost.push_back( weight );
 
 	//有向グラフならここから下の処理が不要
 	
 	//ノードvはノードuとつながっている情報を入れる
 	node[ v ].to.push_back( u );
 	//ノードvとノードuのエッジの重みを入れる
  	node[ v ].cost.push_back( weight );
 }
この関数にノード番号u,v,コスト(重み)weight,ノードの構造体を渡すことで新しくエッジが追加できます。
図4を例にとると
 addEdge( 2 , 4 , 3 , node );
とするとノード２とノード４にコスト３のエッジが追加されます。


これでグラフをデータとして扱えるようになりました。
実際にICPCの問題ではこのグラフのあるノードからあるノードまでの最短経路を調べたりします。

グラフの最短経路を求める有名なアルゴリズムには
[[ダイクストラ法]](２点間の最短経路を求める:負のコストがあると使えない)
[[ベルマン・フォード法]](２点間の最短経路を求める:負のコストがあっても使える)
[[フロイド・ワーシャル法]](すべての２点間の組の最短経路を求める:負のコストがあると使えない)
などがあります。
























...