データ構造論講義ノート（４章）

第４章
　

　グラフ表現とマトリックス
　

　グラフを表現する方法とグラフを構成する要素を辿る方法について説明する。

　４．１　グラフ表現

　グラフは木構造を利用して定義することもできるが、ここではマトリックスを利用してグラフを表現する。

○グラフ

　グラフは、頂点(vertex)（あるいは節点(node)）と辺(edge)（あるいは枝(branch)）の集合として定義される。

　　　　Ｇ＝（Ｖ，Ｅ）

ただし、Ｖ＝{v_ｉ}：頂点の集合、Ｅ＝{(v_ｉ,v_ｊ)| v_ｉ,v_ｊ∈Ｖ}：辺の集合である。

・グラフには、無向グラフと有向グラフがある

　　無向グラフ：辺に方向がなく、どちら向きにでも辿れるグラフ

　　有向グラフ：辺に方向があり、一方向にのみ辿れるグラフ

　　　　　　　　この場合には、辺をアーク（arc）とも呼ぶ

　　　　　　　　v_１　　　v_２　　　　　　　　　　　　 v_１　　　v_２

　　　　　　　　○　　　○　　　　　　　　　　　　 ○　　　○

　　　　　　　　　　　　　e=(v_２,v_３)　　　　　　　　　　　　　e=(v_２,v_３)

　　　　　　　　　　　　　　 v_２, v_３は　　　　　　　　　　　　アーク e

　　　　　　　　○　　　○　　辺 e の端点　　　　 ○　　　○

　　　　　v_５　　v_４　　　v_３　　　　　　　　　 v_５　　v_４　　　v_３

　　　　　○　　　　　　　　　　　　　　　　 ○

○路（path）、道

　頂点を辿る順を表現する路は、頂点の順列として定義される。

　　　　Ｐ＝v_１v_２・・・v_ｋ

　ただし、(v_ｉ,v_ｉ＋１)∈Ｅ, i=1,2,...,k-1 である。

　　　　　　　　v_１　　　v_２

　　　　　　　　○　　　○

　　　　　　　　　　　　　　 v_１v_３v_４v_５は路である

　　　　　　　　○　　　○

　　　　　v_５　　v_４　　　v_３

　　　　　○

○グラフの表現

　グラフをマトリックスで表現する場合には、辺に着目する表現と頂点に着目する表現という２つの表現方法がある。

・接続行列（incidence matrix）

　行を頂点、列を辺として、頂点と辺の関係を記述する

　　　　　　　　　1　　頂点 i から辺 j が出る

　　　　(i, j)＝　0　　頂点 i から辺 j が出ない

　　　　　　　　 -1　　頂点 i へ辺 j が入る（有向グラフの場合）

　　　　　　　　v_１　e_１　v_２　　　　　 e_１ e_２ e_３ e_４ e_５ e_６

　　　　　　　　○　　　○　　　 v_１　1　1　1　0　0　0

　　　　　　　e_３　　e_２　 e_４　　　v_２　1　0　0　1　0　0

　　　　　　　　　　　　　　　　 v_３　0　1　0　1　1　0　（無向グラフ）

　　　　　　e_６　○　　　○　　　 v_４　0　0　1　0　1　1

　　　　　v_５　　v_４　e_５　v_３　　　 v_５　0　0　0　0　0　1

　　　　　○

　各辺は２つの端点を持つため、各列には２つの 1 が存在する。

　　　　　　　　v_１　e_１　v_２　　　　　 e_１ e_２ e_３ e_４ e_５ e_６

　　　　　　　　○　　　○　　　 v_１　1 -1　1　0　0　0

　　　　　　　e_３　　e_２　 e_４　　　v_２ -1　0　0　1　0　0

　　　　　　　　　　　　　　　　 v_３　0　1　0 -1 -1　0　（有向グラフ）

　　　　　　e_６　○　　　○　　　 v_４　0　0 -1　0　1　1

　　　　　v_５　　v_４　e_５　v_３　　　 v_５　0　0　0　0　0 -1

　　　　　○

　各辺は始点と終点を持つため、各列には 1 と -1 が１つずつ存在する。

・隣接行列（adjacency matrix）

　行も列も頂点として、頂点間に辺が存在するかどうかを記述する

　　　　　　　　　1　　辺 (i, j) が存在する

　　　　(i, j)＝

　　　　　　　　　0　　辺 (i, j) が存在しない

　　　　　　　　v_１　　　v_２　　　　　 v_１ v_２ v_３ v_４ v_５

　　　　　　　　○　　　○　　　 v_１　0　1　1　1　0

　　　　　　　　　　　　　　　　 v_２　1　0　1　0　0

　　　　　　　　　　　　　　　　 v_３　1　1　0　1　0　（無向グラフ）

　　　　　　　　○　　　○　　　 v_４　1　0　1　0　1

　　　　　v_５　　v_４　　　v_３　　　 v_５　0　0　0　1　0

　　　　　○

　辺はすべて双方向のため、対称行列となる。

　　　　　　　　v_１　　　v_２　　　　　 v_１ v_２ v_３ v_４ v_５

　　　　　　　　○　　　○　　　 v_１　0　1　0　1　0

　　　　　　　　　　　　　　　　 v_２　0　0　1　0　0

　　　　　　　　　　　　　　　　 v_３　1　0　0　0　0　（有向グラフ）

　　　　　　　　○　　　○　　　 v_４　0　0　1　0　1

　　　　　v_５　　v_４　　　v_３　　　 v_５　0　0　0　0　0

　　　　　○

　各辺に対して始点のみ記述するので、辺の数だけ 1 が存在する。

○記憶量

・頂点の数ｎ、辺の数ｍの場合

　　　　接続行列：Ｏ(ｎｍ)、隣接行列：Ｏ(ｎ^２)

・グラフが疎なときには無駄が多い→リストを用いる

　隣接リスト

　頂点　　　　隣接頂点のリスト　　　　　　　　インデックス　隣接頂点の配列

　　v_１

　　v_２

　　v_３

　　v_４

　　v_５
　

　　 1

　　 5

　　 8

　

　v_２　v_３　v_４
　

v_２

v_３

v_４

　　v_１

v_３

　　　　　　　v_２

　v_１　v_３
　

v_１

v_２

v_４

　　v_３

v_１

v_３

v_５

　　v_４

　v_１　v_２　v_４
　

v_４

　　　　　　　　　　　　v_５

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 12　隣接リストは、左上図のように配列とリストで表現するが、右図のように２つの配列で表現することも可能である。この場合には、１番目の配列に２番目の配列のインデックスを記述し、２番目の配列に隣接する頂点を記述する。　　　　　　　　　　　　 16　隣接リストでは、隣接頂点の総数は辺の総数と同じであるの

　v_１　v_３　v_５
　

　v_４
　

で、記憶量がＯ(ｎ＋ｍ) となる。

問 4.1.1　隣接行列と隣接リストについて、時間量の評価を行え。

　４．２　最短経路問題(shortest path problem)

○課題

地図が与えられたとき、指定された２都市間の最短経路を求めよ。
　

○外部仕様

　以下のような都市ファイルを読み込み、標準入力から入力された２都市に対する最短経路を標準出力へ出力する。都市ファイルでは、２都市間に経路が存在するときに、始点都市番号、終点都市番号、都市間距離でその経路を表現する。

　　　　　　都　市　フ　ァ　イ　ル

開始都市番号	終点都市番号	都市間距離
１　　　１　　　１　　　２　　　３　　　４	２　　　３　　　４　　　３　　　４　　　５	２　　　４　　　８　　　３　　　３　　　４

　　　　　 ①　2　 ②

　　　　　 8　 4　　3

　　　　　 ④　3　 ③　　　　4　　 ⑤
　

○概要設計

　１．都市間距離データを距離マトリックスに読み込む

　２．標準入力から入力された都市番号間の最短経路を求める

　３．最短経路を標準出力に出力する

　距離マトリックスは、隣接行列と同様に行・列ともに頂点を指定するが、(i, j) 要素の値は 1/0 ではなく、都市 i, j 間の距離とする。

　　　　距離マトリックス

　　　　１　　２　　３　　４　　５

０　　２　　４　　８　　∞ ２　　０　　３　　∞　　∞ ４　　３　　０　　３　　∞ ８　　∞　　３　　０　　４ ∞　　∞　　∞　　４　　０
　

　　距離マトリックスは、隣接行列と同様に　行・列ともに頂点を指定するが、(i, j)　要素の値は 1/0 ではなく都市 i, j 間の　距離である

　

○詳細設計

　●アクセス関数

　ａ．距離マトリックスの生成

　G=CREATE(F)：都市ファイル F から都市データを読み込み、距離マトリックス G を生成する。

　ｂ．最短経路

　P=SHORTEST(G, from, to)：距離マトリックス G において、都市 from から都市 to への最短経路 P を返す。

　●データ構造

　ａ．グラフレコード

typedef struct {

　　　int distance[MAX_CITY][MAX_CITY]; /* 距離マトリックス */

　　　int max;　　　　　　　　　　　　　/* 都市番号最大値 */

} GraphRec, *Graph;

GraphRec g_rec;　　　　　　　　　　　　 /* 静的割り当て */

　ｂ．経路レコード

typedef struct {

　　　int path[MAX_CITY];　　　　　　　 /* 最短経路 */

　　　int size;　　　　　　　　　　　　 /* 経路長 */

} PathRec, *Path;

　●グラフ用アクセス関数

　グラフレコード用のアクセス関数を定義する。

　ａ．隣接都市の参照

　　w=FIND(G, v)：都市 v の隣接都市を返す

　ｂ．都市間距離

　　d=DISTANCE(G, v, w)：都市 v と都市 w 間の直接距離 d を返す

　ｃ．経路の出力

　　PRINT(P)：経路 P の内容を標準出力に出力する

○コーディング

【CREATE操作】

#define MAX_CITY 10 /* 都市の最大数 */

#define INFINITY (-1) /* 無限の距離 */

Graph CREATE(char *F)

{

FILE *stream;

int from, to, distance, n;

if((stream=fopen(F, "r"))==NULL) {

fprintf(stderr, "ファイル %s は読めません\n", F);

exit(1);

}

for(from=0; from<MAX_CITY; ++from)

　　for(to=0; to<MAX_CITY; ++to)

g_rec.distance[from][to]=INFINITY; /* 無限の距離 */

n=0;

while(fscanf(stream, "%d %d %d", &from, &to, &distance)!=EOF) {

g_rec.distance[from][to]

=g_rec.distance[to][from]=distance;

if(from>n) n=from; /* n を都市番号の */

if(to>n) n=to; /* 　最大値にする */

}

g_rec.max=n;

return(&g_rec);

}

（注）距離マトリックスでは、FIND操作のために、同一都市間の距離を０ではなく無限にした。これにより同一都市間には辺がないと解釈される。

【FIND操作】

int FIND(Graph G, int v)

{

static int city= -1, w;

if(v!=city) {

city=v; /* 新しい都市 */

w=0; /* 探索開始都市 */

}

for(; w<=G->max; ++w)

if(DISTANCE(G, v, w)!=INFINITY) return(w++);

city= -1;

return(-1); /* 隣接都市はない */

}

【DISTANCE操作】

int DISTANCE(Graph G, int v, int w)

{

return(G->distance[v][w]);

}

【PRINT操作】

void PRINT(Path P)

{

int i;

for(i=0; i<P->size; ++i)

printf(" %d", P->path[i]);

printf("\n");

}

【main関数】

　City> のプロンプトの後に、最短距離を求めたい都市番号を２つ入力すると、最短経路を出力する。

void main(int argc, char **argv)

{

Graph G;

int from, to, d;

int from, to;

if(argc!=2) {

fprintf(stderr, "使用法： %s ファイル名\n", argv[0]);

exit(1);

}

G=CREATE(argv[1]);

for(;;) {

printf("City> ");

if(scanf("%d %d", &from, &to)==EOF) break;

PRINT(SHORTEST(G, from, to, &d));

printf("Distance=%d\n", d);

PRINT(SHORTEST(G, from, to));

}

問 4.2.1　都市間距離ではなく、都市の座標位置によって記述された都市ファイルを対象とする場合、どのようなデータ構造とアクセス関数を準備すればよいか考えよ。

問 4.2.2　都市番号ではなく、都市名によって記述された都市ファイルを対象とする場合、どのようなデータ構造とアクセス関数を準備すればよいか考えよ。

問 4.2.3　隣接行列の変形ではなく、隣接リストの変形として距離マトリックスを構成する場合のデータ構造を考えよ。

問 4.2.4　最短経路以外に最短距離も出力するためにはどのようなアクセス関数を準備すればよいか考えよ。

問 4.2.5　最短経路が複数存在する場合に対応するためには、どのようなアクセス関数を準備すればよいか考えよ。

　４．３　逐次反復法

《概要》辺を１つ辿る場合の最短距離、２つ辿る場合の最短距離というように、辺の数を増やしながら最短経路を求める。

○詳細

　頂点 s から頂点 t への最短経路を求めることを考える。頂点 s から頂点 v までの最短経路長を f(v) とすれば、

　　　　f(s)=min{0, min{f(u)+d(u, s)|(u, s)∈Ｅ}

　　　　f(v)=min{f(u)+d(u, v)|(u, v)∈Ｅ} (v≠s)

　　　　ただし、d(u, v) は頂点 u と頂点 v 間の辺のコスト（負でもよい）である。

が成立する。　　　　　　　　　u

　　　　　　　　　s　　　　　 ○　　　　　v

　　　　　　　　　○　 f(u)　　　 d(u,v)　○

　したがって、頂点 s から頂点 v への辺数 k 以内の最短経路長を f_ｋ(v) とおくと、

　　　　f_０(s)=0

　　　　f_０(v)=∞ (v≠s)

　　　　f_ｋ(v)=min{f_ｋ－１(v), min{f_ｋ－１(u)+d(u, v)|(u, v)∈Ｅ}} (k=1,2,...,|Ｖ|)

が成立する。（|Ｖ|は集合Ｖの要素数）

例題4.3.1　逐次反復法により、課題となっている距離マトリックスに基づき、都市１から都市５までの最短経路を求めよ。

　　ｖ　１　　　　２　　　　３　　　　４　　　　５　　 ←都市ｖ

　ｋ

　０

　１

　２

　３

　４

　５
　

[2,3,4]　　[1,3]　　[1,2,4]　 [1,3,5]　　 [4]{2,4,8}　　{2,3}　　{4,3,3}　 {8,3,4}　　 {4}　０　　　　∞　　　　∞　　　　∞　　　　∞

(∞,∞,∞)　　(2,∞)　　(4,∞,∞)　 (8,∞,∞)　　 (∞)　０　　　　２　　　　４　　　　８　　　　∞

(4,8,16)　 (2,7)　　(4,5,11)　(8,7,∞)　　 (12)　０　　　　２　　　　４　　　　７　　　　12

(4,8,15)　 (2,7)　　(4,5,10)　(8,7,16)　　(11)　０　　　　２　　　　４　　　　７　　　　11

(4,8,15)　 (2,7)　　(4,5,10)　(8,7,15)　　(11)　０　　　　２　　　　４　　　　７　　　　11

←ｖへの辺を持つ都市ｗ←ｗ－ｖ間の距離　（辺のコスト）

←k 段階における　路「１,...,ｗ,ｖ」　の経路長

　

　ただし、表中の [ ] は各列に対応する都市ｖへの辺を持つ都市ｗのリスト、{ } は距離（辺のコスト）のリスト、( ) は k 時点における「都市１, ..., 都市ｗ, 都市ｖ」の経路長のリストである。

　最短経路は 1, 3, 4, 5、最短経路長は１１である。

○コーディング

【SHORTEST操作】

Path SHORTEST(Graph G, int from, int to, int *distance)

Path SHORTEST(Graph G, int from, int to)

{

int f[MAX_CITY][2], chain[MAX_CITY];

int _k_1=0, _k=1;

int k, v, w, d;

static PathRec p_rec;

for(v=0; v<=G->max; ++v)　　　 /* f_０(s)=0、f_０(v)=∞ (v≠s) */

f[v][0]=(from==v? 0 : INFINITY);

for(k=1; k<=G->max; ++k) {

for(v=0; v<=G->max; ++v)　　　 /* f_ｋ(v)=f_ｋ－１(v) */

　　f[v][_k]=f[v][_k_1];

for(v=0; v<=G->max; ++v)

　　while((w=FIND(G, v))>=0)　　/* 辺 (v,w) の処理 */

　　if(f[v][_k_1]!=INFINITY) {

d=f[v][_k_1]+DISTANCE(G, v, w);

　　　　　　　　　　　　　　　　　　　　　　　　/* f_ｋ－１(u)+d(u, v) */

if(f[w][_k]==INFINITY || f[w][_k]>d) {

f[w][_k]=d;　　 /* 最小値の設定 */

chain[w]=v;　　 /* １つ前の都市の記憶 */

}

_k=!_k; _k_1=!_k_1;　　　　　　 /* (0,1) or (1,0) */

}

　　　　MAKEPATH(G, from, to, chain, &p_rec);

*distance=f[to][_k_1];

return(&p_rec);

}

（注）k は 0 から n まで変化するが、１つ前の k-1 の状態が分かれば、k の状態を計算できるので、f_ｋ－１(v) と f_ｋ(v) のために、f[MAX_CITY][2] という２行の配列を用いている。使用する行を指定するために、(_k_1, _k) という変数を (0,1), (1,0) という組み合わせで変化させている。

【MAKEPATHサブ関数】

　最短経路を記憶するために、chain[i] に都市 i の一つ前の都市番号を記憶している。この配列 chain を利用して、①目的都市から出発都市まで逆方向に chain を辿り経由する都市の数を求め、②最短経路を返す路 P に逆方向から経路を設定している。

void MAKEPATH(Graph G, int from, int to, int *chain, Path P)

{

　　　　int i, v;

for(i=0, v=to; i<=G->max && v!=from; ++i, v=chain[v]);

P->size=i+1;　　　　　　　　　　　　　　/* 経由する都市数 */

for(v=to; i>=0 && v!=from; --i, v=chain[v])

P->path[i]=v;　　　　　　　　　 /* 路の構成 */

P->path[i]=v;

}

○時間量

　距離の計算（参照）回数を時間量とする。距離の計算は、ｋが１～ｎまで変化する間に、ｎ都市各々について行う。したがって、SHORTEST操作については道の総数をｍとすれば、

　　　　Ｔ_{ＳＨＯＲＴＥＳＴ}(n, m)＝「ｋの変化」*「都市数」*「１都市当たりの平均の道数」

　　　　　　　　　　　　＝ｎ*ｎ*(２ｍ/ｎ)＝２ｍｎ

　都市数がｎの時、１都市当たりの最大道数は n-1 であることを考慮すると、

　　　　　　　　　　　　≦ｎ^２(ｎ－１)

　FIND操作について考えれば、全都市に対して道があるかどうかを判定するので、

　　　　Ｔ_ＦＩＮＤ(n)＝「ｋの変化」*「都市数」*「都市数」

　　　　　　　　＝ｎ^３

　∴Ｔ_ｍａｘ(ｎ)＝Ｔ_{ＳＨＯＲＴＥＳＴ}(n, m)＋Ｔ_ＦＩＮＤ(n)≦ｎ^２(ｎ－１)＋ｎ^３＝２ｎ^３－ｎ^２

　　　　　　＝Ｏ(ｎ^３)

問 4.3.1　逐次反復法において、距離の計算回数を出力する処理を追加せよ。

問 4.3.2　逐次反復法においては、ある段階 k において全ての f_ｋ(v) の値が固定すれば、次段階の f_ｋ＋１(v) を計算する必要がない。この性質を加味したコーディングを行え。

問 4.3.3　問 4.2.3 のように距離マトリックスを隣接リストで表現したコーディングを行え。

問 4.3.4　以下の都市に関するグラフを都市ファイルに記述し、都市 a と都市 k 間の最短経路を求めよ。距離の計算回数は何回か。

　　　　　　　　　　b　　　　　　e　　　　　 h

　　　　　　　　　　　　　　5　　　　　 6

　　　　　　　　4　　　 5　　 3　　　3　　　 2　　4

　　　　　 a　　　　　　　d　　　3　　g　　3　i　2　　 k

　　　　　　　　 5　　　 3　　3　　 3　　　　　 3　 2

　　　　　　　　　　　　　 4　　　　　　　7

　　　　　　　　　　 c　　　　　f　　　　　　　 j

問 4.3.5　距離マトリックスを隣接リストで表現した時の時間量を評価せよ。

　４．４　ダイクストラ法(Dijkstra)

《概要》辺のコスト（距離）が非負であることを前提条件とする

　１．始点からの最短経路が定まった都市集合Ｓに始点を入れる

　２．集合Ｓに属さず、始点に最も近い都市を集合Ｓに加える

　３．終点が集合Ｓに入るまで、２．を繰り返す

○詳細

　頂点 s から頂点 t への最短経路を求めることを考える。頂点 s から頂点 v までの最短経路長を f(v) とすれば、アルゴリズムは以下のようになる。

　(1) Ｓ=φ

　(2) f_０(s)=0、f_０(v)=∞ (v≠s)

　(3) f_ｍｉｎ=0、v_ｍｉｎ=s

　(4) v_ｍｉｎ = t ならば、終了

　(5) Ｓ = 頂点集合Ｖならば、終了

　(6) Ｓ=Ｓ∪{v_ｍｉｎ}

　(7) Ｓに属さない全ての v に対して、

　　　　f_ｋ(v)=min{f_ｋ－１(v),f_ｍｉｎ+d(v_ｍｉｎ,v)} (k=1,2,...,n) を求める

　(8) Ｓに属さない全ての v に対して、

　　　　最小値 f_ｍｉｎ=min{f_ｋ(v)} (k=1,2,...,n) とその時の都市 v_ｍｉｎを求める

　(9) (4) へ

●解説

　集合Ｓに属さず、始点に最も近い都市を集合Ｓに加えることができる、すなわち、始点からその都市までの最短経路が定まることを示す。

　グラフに属する頂点の集合を以下のように分類する。

　①頂点 s からの最短経路が定まった頂点の集合Ｓ

　②それ以外の頂点の集合Ｔ

　　　　　　　　　Ｓ　　　　　　　　　Ｔ

ws	v_ｍｉｎ　　　　　　　　　 t　x

　上図のように、集合Ｔの中で都市 v_ｍｉｎが始点に最も近い都市であったとすれば、

　　　　任意の都市 v ∈ Ｔに対して、s-w-v_ｍｉｎの経路長 ≦ s-v の経路長

となる。ここで、経路 s-w-v_ｍｉｎが最短経路でないと仮定すると、集合Ｔに属する都市 x があり、都市 x から都市 v_ｍｉｎに進むという s-w-v_ｍｉｎより短い経路 Px が存在することになる。ところが、

　　　　s-w-v_ｍｉｎの経路長 ≦ s-x の経路長

　　　　　　　　　　　　　≦ s-x の経路長＋x-v_ｍｉｎの経路長

　　　　　　　　　　　　　　　　（∵ x-v_ｍｉｎの経路長≧0)

　　　　　　　　　　　　　＝ Px の経路長

となり、仮定と矛盾する。したがって、路 s-w-v_ｍｉｎは最短経路である。

例題4.4.1　ダイクストラ法により、課題となっている距離マトリックスに基づき、都市１から都市５までの最短経路を求めよ。

　　ｖ　１　　　　２　　　　３　　　　４　　　　５　　 ←都市ｖ

　ｋ

　０

　１

　２

　３

　４
　

[2,3,4]　　[1,3]　　[1,2,4]　 [1,3,5]　　 [4]{2,4,8}　　{2,3}　　{4,3,3}　 {8,3,4}　　 {4}　０　　　　∞　　　　∞　　　　∞　　　　∞

(2,4,8)　ｘ　　　　２　　　　４　　　　８　　　　∞

　　　　　 (x,3)　ｘ　　　　ｘ　　　　４　　　　８　　　　∞

　　　　　　　　　　(x,x,3)　ｘ　　　　ｘ　　　　ｘ　　　　７　　　　∞

　　　　　　　　　　　　　　　(x,x,4)　ｘ　　　　ｘ　　　　ｘ　　　　ｘ　　　　11
　

←ｖへの辺を持つ都市ｗ←ｗ－ｖ間の距離　（辺のコスト）

　

　ただし、表中の [ ] は各列に対応する都市ｖへの辺を持つ都市ｗのリスト、{ } は距離（辺のコスト）のリスト、( ) は最短の都市から出る辺のコストであり、x は集合Ｓに属する都市を除くことを示している。なお、太字は各段階における最短の都市である。

　最短経路は 1, 3, 4, 5、最短経路長は１１である。

○集合操作

　ダイクストラ法では、集合を利用するため集合操作用のアクセス関数を定義する。

●データ構造

　ここでは、要素が整数であるとし、その要素が集合に属すかどうかを１／０で表現する。

#define TABLE_SIZE　　　MAX_CITY/* 最大都市数 */

typedef struct {

　　　　char set[TABLE_SIZE];　 /* 整数 i が属する場合 set[i] が１ */

　　　　int size;

} SetRec, *Set;

SetRec set_rec;

●アクセス関数

　ａ．集合の生成

　　S=MAKE(N)：大きさ N の集合を生成する

　ｂ．要素を集合に入れる

　　SET(X, S)：集合 S に要素 X を入れる

　ｃ．メンバの判定

　int MEMBER(X, S)：要素 X が集合 S に属するかどうかを判定し、属す場合は１、属さない場合は０を返す

○コーディング

●集合用アクセス関数

【MAKE関数】

Set MAKE(int N)

{

　　　　set_rec.size=N;

　　　　return(&set_rec);

}

【SET関数】

void SET(int X, Set S)

{

　　　　S->set[X]=1;

}

【MEMBER関数】

int MEMBER(int X, Set S)

{

　　　　return(S->set[X]);

}

●アクセス関数

【SHORTEST 操作】

Path SHORTEST(Graph G, int from, int to, int *distance)

Path SHORTEST(Graph G, int from, int to)

{

int f[MAX_CITY], chain[MAX_CITY];

int f_min, v_min;

int k, v, d;

Set S;

static PathRec p_rec;

S=MAKE(G->max+1);

for(v=0; v<=G->max; ++v) /* f(s)=0、f(v)=∞ (v≠s) */

f[v]=(from==v? 0 : INFINITY);

f_min=0;

v_min=from;

for(k=1; k<=G->max; ++k) {

　　if(v_min==to) break; /* 終点に到着 */

　　SET(v_min, S);

　　while((v=FIND(G, v_min))>=0)

if(!MEMBER(v, S)) {

　　d=f_min+DISTANCE(G, v_min, v);

　　if(f[v]==INFINITY || f[v]>d) {

f[v]=d; /* 距離の更新 */

chain[v]=v_min;

　　} /* 一つ前の都市の記憶 */

}

　　f_min=INFINITY;

　　for(v=0; v<=G->max; ++v)　　/* 最短経路の都市を見つける */

if(f[v]!=INFINITY &&

　 !MEMBER(v, S) &&

　 (f_min==INFINITY || f_min>f[v])) {

f_min=f[v]; /* 最小値の設定 */

v_min=v; /* 都市の記憶 */

}

　　if(f_min==INFINITY) break; /* 経路が見つからない */

}

MAKEPATH(G, from, to, chain, &p_rec);

*distance=f[to];

return(&p_rec);

}

○時間量

　距離の計算回数を時間量とする。距離の計算は、SHORTEST操作では、

　　　　Ｔ_{ＳＨＯＲＴＥＳＴ}(n)＝「ｋの変化」*「１都市当たりの平均の道数」

　　　　　　　　　　　　＝ｎ*(２ｍ/ｎ)＝２ｍ

　都市数がｎの時、１都市当たりの最大道数は n-1 であることを考慮すると、

　　　　　　　　　　　　≦ｎ(ｎ－１)

　FIND操作について考えれば、全都市に対して道があるかどうかを判定するので、

　　　　Ｔ_ＦＩＮＤ(n)＝「ｋの変化」*「都市数」＝ｎ^２

　∴Ｔ_ｍａｘ(ｎ)＝Ｔ_{ＳＨＯＲＴＥＳＴ}(n, m)＋Ｔ_ＦＩＮＤ(n)≦ｎ(ｎ－１)＋ｎ^２＝２ｎ^２－ｎ

　　　　　　＝Ｏ(ｎ^２)

問 4.4.1　ダイクストラ法において、距離の計算回数を出力する処理を追加せよ。

問 4.4.2　問 4.2.3 のように距離マトリックスを隣接リストで表現したコーディングを行え。

問 4.4.3　問 4.3.4　のグラフを都市ファイルに記述し、都市 a と都市 k 間の最短経路を求めよ。距離の計算回数は何回か。

問 4.4.4　距離マトリックスを隣接リストで表現した時の時間量を評価せよ。