アルゴリズム論
∼レポート１ グラフ∼
e055717
金城佑典
目 次
1
はじめに
2
2
深さ優先探索木 (Depth First Search Tree)
3
2.1
node
構造体 . . . .
3
2.2
getNodeID
と getNodeName . . . .
3
2.3
隣接リスト表現 . . . .
4
2.4
深さ優先探索の実装（再帰） . . . .
5
2.4.1
間接点 (articulation point) の発見 . . . .
6
2.4.2
連結成分 (connection component) の発見 . . . .
7
2.5
スタック (FILO) の実装 . . . .
7
2.6
深さ優先探索の実装（スタック） . . . .
8
3
幅優先探索木 (Breadth First Search Tree)
9
3.1
キュー (FIFO) の実装
. . . 10
3.2
幅優先探索の実装 . . . 11
4
最小木 (Minimum Tree) ー 順位優先探索 (Priority First Search)
ー
12
4.1
順位付きキュー . . . 12
4.2
順位優先探索の実装
. . . 14
5
合併-発見木 (Union-Find Tree)
15
5.1
find
関数 . . . 15
6
最小木 (Minimum Tree) ー Kruskal 法 ー
17
6.1
edge
構造体 . . . 17
6.2
Kruskal
法の実装 . . . 17
7
最短経路木 (Shotest Path Tree)
18
7.1
最短経路探索の実装
. . . 18
1
はじめに
• ソースコードの全文は掲載していません。
• ソースコード中のコメントも省略してあります。
• レポート中では下図のグラフを使用します。（右はプログラムに入力す
るファイル）
A B C G D E F H I J K M L図 1: 無向グラフ (グラフ１)
A-G A-B A-C L-M J-M J-L J-K E-D F-D H-I F-E A-F G-E A B C G D E F H I J K M L図 2: 2 重連結でない無向グラフ (グラ
フ２)
A-G A-B A-C L-M J-M J-L J-K E-D F-D H-I F-E A-F G-E G-C G-H j-G L-G D F 6 2 A 2 E G H I J K M L 1 2 1 1 2 3 1 3 5 2 4 1 4 B C 1 4 2 1 2 1図 3: 重み付き無向グラフ (グラフ３)
A-B:1 A-F:2 A-G:6 B-C:1 B-D:2 B-E:4 C-E:4 D-E:2 D-F:1 E-F:2 E-G:1 E-L:4 F-L:2 G-H:3 G-J:1 G-L:5 H-I:2 I-K:1 J-K:1 J-L:3 J-M:2 L-M:12
深さ優先探索木
(Depth First Search Tree)
「頂点に隣接しておりかつまだ訪問していない点を訪問する、その点を
新たな頂点としてこれを繰り返す。」というアルゴリズム。時間計算量は
O(
|V | + |E|)、隣接行列を用いると実行時間は |V |
2に比例する。
（以降、V は
ノードの数、E は辺の数。）
図 4: 深さ優先探索のイメージ（wikipwdia より）
連結成分をみつけるのにも役立つ（後述）
2.1
node
構造体
node
構造体にはグラフのノード（節や葉）の情報を記憶させるもの、後述
する隣接リストに使用するものなのでそれぞれのノードには次のノードへの
ポインタを持たせることにする。
struct node{
int v;//node
struct node *next;//次 node へのポインタ
};
構造体なので v はもちろん char 型にして直接ノード名を入れておくことも
できるが、ノード番号 v は配列 val（これも後述する）にも使うので今回は
int
型にしておく。
2.2
getNodeID
と getNodeName
隣接リストについて説明するまえに、getNodeID 関数と getNodeName 関
数の内容を示しておく。
//文字コードを ID に変換int getNodeID(char *nodeName){ return (int)(nodeName-’A’+1); }
//IDを文字コードに直す int getNodeName(int nodeID){
return (int)(nodeID+’A’-1); }
見てもわかるとおり、
「入力された文字-A(ASCII コードで 65)+1」という
式で文字を数字に変換する関数と、その逆をする関数である。今後グラフの
ノードの情報を配列に入れる際にはこの ID の位置に入れることになる、よっ
てグラフに使用できる文字は「アルファベットの大文字でなければならない」
「ABC... とアルファベット順に使わなければならない（たとえばノード名と
して Z をつかうなら A から Y も使わなければならない）」という制約が生じ
てしまっている。
この制限は今回のプログラム特有の制限でアルゴリズム自体とは関係ない
ので、プログラムを改良することによってどんな文字でも扱えるようにでき
るが、今回は省略する。ともかく、今回のプログラムを使用する際にはグラフ
の定義の際に以下の制約に気をつけなければならない、もしやぶるとエラー
が出たり、正確に演算できなくなったりする恐れがある。
• グラフのノード名はアルファベットの大文字でなければならない
• グラフのノード名は A から順番に使われなければならない
2.3
隣接リスト表現
隣接リストというのは「A は B と繋がっていて、B は C と繋がっている」
というようなグラフの表現方法で、たとえば以下の用な有向グラフなら
A->B<->C
隣接リスト表現は下のようになる
A->B
B->C
C->B
今回は無向グラフなので以下のようなコードで実装できる、ここで「glaph-file」には「A-B」のような形式でグラフを表現したファイルのパスが入って
いる。
//隣接リスト (adj) の生成 //adj[]は node 型 adjlist(char* glaphfile){ FILE *fp; char v1,v2,row[3]; //ファイルを開くfp=fopen(glaphfile,"r"); if(!fp){
printf("can not open %s",glaphfile); exit(1);
}
//番兵を用意
z=(struct node *)malloc(sizeof(*z)); z->next = z; for(j=1; j<=V; j++) adj[j]=z; for(j=1; j<=E; j++){ //ファイルを一行読み込み fgets((char*)row,6,fp); sscanf(row,"%c-%c",&v1,&v2); x=getNodeID(v1); y=getNodeID(v2);
t=(struct node *)malloc(sizeof(*t)); t->v = x;
t->next = adj[y];//今の adj[y] は新しい adj[y] の next adj[y]=t;
t=(struct node *)malloc(sizeof(*t)); t->v = y; t->next = adj[x]; adj[x]=t; } }
これにより「A-B」
「B-C」の順でデータが入力された場合以下のような隣
接リストが生成される。
A->B
B->C->A
C->B
2.4
深さ優先探索の実装（再帰）
深さ優先探索のプログラムは以下のようになる。
//深さ優先探索 (DFS) listdfs(){ int k; for(k=1; k<=V; k++) val[k]=0;//初期化 for(k=1; k<=V; k++) if(val[k]==0) visit(k); } visit(int k){ struct node *t; val[k] = ++id; printf("visit %c \n",getNodeName(k)); //繋がっている頂点をしらべる for(t=adj[k]; t!=z; t=t->next) if(val[t->v]==0){printf(" %c call -> ",getNodeName(k)); visit(t->v); } }
深さ優先探索はスタックを用いて実装することもできるが、今回は再帰処
理を用いた実装にした。
これによって、グラフ１で実行すると以下のような実行結果が得られる。
visit A
A call -> visit F
F call -> visit E
E call -> visit G
E call -> visit D
A call -> visit C
A call -> visit B
visit H
H call -> visit I
visit J
J call -> visit K
J call -> visit L
L call -> visit M
A B C G D E F H I J K M L図 5: 深さ優先探索木
2.4.1
間接点 (articulation point) の発見
深さ優先探索の visit 関数を以下のように改造することで間接点を発見する
ことができるようになる。
（頂点 k が根かどうかはべつのところでテストされ
ている）
int visit(int k){ int m,min; struct node *t; val[k] = ++id; min=id; for(t=adj[k]; t!=z; t=t->next) if(val[t->v]==0){ m=visit(t->v); if(m < min) min = m;if(m >= val[k]) printf(" %c is articulation point \n",getNodeName(k)); }
return min; }
グラフ１を入力すると以下のような結果が得られる。その頂点を除去する
と連結成分が m 個増えるなら、その頂点は m 回出力される。
Find Articulation Point
--E is articulation point
E is articulation point
F is articulation point
A is articulation point
A is articulation point
A is articulation point
H is articulation point
J is articulation point
L is articulation point
J is articulation point
ちなみに、間節点を持たないグラフを「二重連結 (biconnected)」であると
いい、二重連結でないグラフ（つまり間節点のあるグラフ）はいくつかの「二
重連結成分 (biconnected component)」つまり２つの異なる道によって往来
できる頂点の部分集合に分割できる。
2.4.2
連結成分 (connection component) の発見
深さ優先探索の listdfs 関数と visit 関数を改造すると連結成分を調べるこ
とができる。
//深さ優先探索 (DFS) を改造した連結成分への分解 listdfs(){ int k; for(k=1; k<=V; k++) val[k]=0;//初期化 for(k=1; k<=V; k++) if(val[k]==0){ printf("}\n\n {"); visit(k); } printf("}\n"); } visit(int k){ struct node *t; val[k] = ++id;for(t=adj[k]; t!=z; t=t->next) if(val[t->v]==0) visit(t->v); printf(" %c ",getNodeName(k));
}
グラフ１を入力すると以下のような結果が得られる。
find connection component
--{ G
D
E
F
C
B
A }
{ I
H }
{ K
M
L
J }
2.5
スタック (FILO) の実装
struct stack {
int data;
struct stack *next;
};
static struct stack *first;
次にスタックの先頭へのデータの追加を実装。
push(int data){
struct stack *my = (struct stack *)malloc(sizeof(first)); my->data = data; //今の先頭を自分の次にする my->next = first; //自分を先頭にする first = my; }
そして取り出し。
int pop(){struct stack *lp = first; int data; if(lp==NULL){ /* データがキューにない */ return -1; } //dataを取り出す data = lp->data; //次のやつをあたらしい先頭にする lp = lp->next; free(first); first=lp; return data; }
最後にスタックが空かどうかを調べる（空なら１を返す）。
int stackempty(){struct stack *lp = first; if(lp==NULL) return 1; return 0; }
2.6
深さ優先探索の実装（スタック）
深さ優先探索（再帰）の visit 関数を以下と置き換えればいい。
visit(int k){ struct node *t; push(k);if(debug_flag==1) printf("visit %c \n",getNodeName(k));
while(!stackempty()){ k=pop();
val[k]=++id; //繋がっている頂点を調べる
for(t=adj[k]; t!=z; t=t->next) if(val[t->v]==0){
printf(" %c call -> %c \n",getNodeName(k),getNodeName(t->v)); push(t->v); //スタックに追加したので負 val[t->v]=-1; } } printf("-- end --\n"); }
A call -> F
A call -> C
A call -> B
A call -> G
G call -> E
E call -> D
end
--H call -> I
end
--J call -> K
J call -> L
J call -> M
end
--A B C G D E F H I J K M L図 6: 深さ優先探索木 (スタック)
3
幅優先探索木
(Breadth First Search Tree)
「頂点に隣接しておりかつまだ訪問していない点を＜すべて＞訪問する、
次に訪れた点を頂点として同様に繰り返す。」というアルゴリズム。時間計算
量は O(
|V | + |E|)
3.1
キュー (FIFO) の実装
幅優先探索にはキューを用いるので、まずはキューを実装する。最初にキュー
用の構造体を定義する。
struct queue {
int data;
struct queue *next;
};
static struct queue *first;
今回は data に入るのはノードの ID なので data は int 型にした。
次にキューで使う３つの関数を定義する。まずは data をキューに入れる
put
関数である、この関数により入力データ data をキューの最後尾に追加
する。
put(int data){
struct queue *lp=first; //キューの最後尾を探して領域確保
if(lp!=NULL){
while(lp->next!=NULL){ lp=lp->next; }
lp = lp->next = (struct queue *)malloc(sizeof(first)); }else{
lp = first=(struct queue *)malloc(sizeof(first)); } //dataを登録 lp->data = data; lp->next = NULL; }
次にキューの先頭データを取得する get 関数を定義する。先頭データ first
を返し、first の次のデータを first に代入している。
int get(){struct queue *lp = first; int data; if(lp==NULL){ /* データがキューにない */ return -1; } //dataをとりだす data = lp->data; //先頭の次のものを新しい先頭になる lp = lp->next; free(first); first=lp; return data; }
最後に、キューが空かどうか調べる関数を実装する。この関数ではキュー
が空なら 1 を返す。
int queueempty(){
struct queue *lp = first;
if(lp==NULL) return 1; return 0; }
3.2
幅優先探索の実装
キューを用いた幅優先探索は次のように実装した。
//幅優先探索 (BFS) listbfs(){ int k; for(k=1; k<=V; k++) val[k]=0;//初期化（すべて未訪問） //一つの木に繋がってるとは限らないfor(k=1; k<=V; k++) if(val[k]==0) visit(k); }
visit(int k){ struct node *t; put(k);
if(debug_flag==1) printf("visit %c \n",getNodeName(k));
while(!queueempty()){ k=get(); val[k]=++id; //繋がってる頂点を調べる for(t=adj[k]; t!=z; t=t->next) if(val[t->v]==0){
printf(" %c call -> %c \n",getNodeName(k),getNodeName(t->v)); put(t->v); //スタックに入れたので負 val[t->v]=-1; } } printf("-- end --\n"); }
実行すると例えば次のような結果が得られる。
A call -> F
A call -> C
A call -> B
A call -> G
F call -> E
F call -> D
end
--H call -> I
end
--J call -> K
J call -> L
J call -> M
end
--A B C G D E F H I J K M L図 8: 幅優先探索木
4
最小木
(Minimum Tree)
ー 順位優先探索
(Pri-ority First Search)
ー
順位優先探索は各々の辺に重みがある「重み付きグラフ」を用いられる。
その名の通り辺の重みによって優先度 (priority) を決定する。今回は最小木
なので重みが小さい方が priority が小さい（つまり優先度が高い）
4.1
順位付きキュー
構造体は前述のキューに pruority を追加した物を用いる。
struct pqueue {
int data;
int priority;
struct pqueue *next;
};
ここで、
「priority の値が小さいほど優先度は高い」ということに注意して
キューにデータを追加する部分を順位付きキュー用に書き換える
pqinsert(int data,int priority){ struct pqueue *lp=first; struct pqueue *my;
_Bool flag=0;
// 領域確保（新しい節を作成
if((my = (struct pqueue *)malloc(sizeof(struct pqueue))) == NULL){ printf("error : Can not allocate memory\n");
exit(1); } my->data = data; my->priority = priority; my->next = NULL; //priorityが小さいのが最初にくるように挿入 if(lp!=NULL){
struct pqueue *dadqueue = first;
while( lp->next!=NULL ){//キューの最後にたどりつくまで
if( (lp->priority) > priority){//もし自分の priority のほうがちいさかったら if(lp==first){//lp=firstなら //現在の先頭を自分の次につなげる my->next=lp; //自分を先頭にする first=my; flag=1; break; }else{ //自分の次につなげる my->next=lp; //lpの親に自分をつなげる dadqueue->next=my;
flag=1; break; } } //親を覚えておく dadqueue=lp; lp=lp->next;//次のキュー } if(flag!=1) lp->next=my;//途中に挿入しなかったなら最後に追加 }else{//キューが空なら //自分を先頭にする
first= (struct pqueue *)malloc(sizeof(struct pqueue)); first=my;
} }
また、順位優先探索では優先度の更新も行われるので、キューをアップデー
トする関数も定義する。この pqupdate 関数は「data が存在して、かつ priority
が新しい priority より大きいなら優先度を更新して１を返す」「data が存在
しないなら insert して 1 を返す」
「どちらでもないなら何もせずに 0 を返す」
関数である。
int pqupdate(int data,int priority){ struct pqueue *lp=first;
if(lp!=NULL){
while(lp->next!=NULL){
//もし現在登録されている priority より新しい priority のほうが小さかったら if((lp->data == data) && (lp->priority > priority) ){
pqchenge(data,priority);//priorityを更新 return 1;
//もし現在登録されている priority より新しい priority のほうが大きかったら }else if(lp->data == data && lp->priority <= priority){
return 0; } lp=lp->next; } //同じデータが格納されてなかったら pqinsert(data,priority); return 1; } }
使用されている pqchenge 関数は優先度を変更する関数だが、今回は「該当
データを削除」ー＞「新しくデータを insert」する関数にした。ただし、data
がキュー内に存在するかどうかは判定していない（pqupdate のほうで判定で
きているはず）
pqchenge(int data,int newpriority){ struct pqueue *lp=first;
struct pqueue *dadqueue=first;
if(lp!=NULL){
if(lp->data == data){//priorityを更新したいデータが見つかったら //とりあえずそのデータを削除 dadqueue->next = lp->next; //もう一度あたらしい priority で登録しなおす pqinsert(data,newpriority); break; } //親を覚えとく dadqueue = lp; //次を調べる lp=lp->next; } } }
取り出し方はキューのときと同じ。
4.2
順位優先探索の実装
順位優先探索は優先度が高いノードを優先的に探索するアルゴリズムであ
る、今回は node 型に新たに重み w を追加し、優先度の指標として用いる。
struct node{
int v;//node
int w;//weght
struct node *next;//次 node へのポインタ
};
最少木を作りたいので重みが小さい方が優先度が高い、よって前述の順序
付きキューの priority にはこの重み w を入れてある。（注：隣接リストを生
成する際にノードの情報に重みを入れるのを忘れないようにすること。）
//順位優先探索 (Priority-First Search) listpfs(){ int k; for(k=1; k<=V; k++) val[k]=-unseen;//初期化 //木が２つな可能性もあるfor(k=1; k<=V; k++) if(val[k]==-unseen) visit(k); for(k=1; k<= E; k++)
if(dad[k]!=0) printf("%c -> %c \n",getNodeName(dad[k]),getNodeName(k)); }
visit
関数は以下のようになる。
visit(int k){ struct node *t;
if(debug_flag==1) printf("[debug:visit] visit %c : \n",getNodeName(k));
//rootを登録
if( pqupdate(k,unseen) != 0) dad[k]=0; //順序付きキューの中身が存在する間
while(!pqueueempty()){ id++;
k=pqremove();//順序付きキューの中身を取得
val[k]=-val[k];//縁頂点（見つけてはあるけど使ってはいない頂点）は負の値
//ルートなら 0
if(val[k] = -unseen) val[k]=0; //繋がってる頂点を調べる
for(t=adj[k]; t!=z; t=t->next){ if(val[t->v]<0){//未訪問なら
if(pqupdate(t->v, t->w)){//順序付きキューに登録 or 更新されたら
if(debug_flag==1) printf("[debug:visit]check %c - %c \n",getNodeName(k),getNodeName(t->v)); val[t->v]=-(t->w);//縁頂点は負の値 : -(優先度) dad[t->v]=k;//親を覚えておく } } } } }
グラフ３を入力すると実行結果は以下のようになる。
A -> B
B -> C
B -> D
D -> E
D -> F
E -> G
I -> H
K -> I
G -> J
J -> K
F -> L
L -> M
D F A 2 E G H I J K M L 1 2 1 1 1 2 1 B C 1 2 1 1図 9: 順位優先探索を用いた最小木
5
合併
-
発見木
(Union-Find Tree)
グラフの２つのノード間にパスがあるかどうか調べる問題を「Union-FInd
問題」というが、それを解くにはグラフのノード情報から出発し、それぞれ
のノードの親を記録していけばいい、ノード A とノード B の親が同一なら
ノード A とノード B は繋がっていることになる。
5.1
find
関数
ノードの親を調べるには以下の find 関数を用いればよい。
この関数では「重さ均衡法 (weight balancing)：子孫の数が多い方を根と
する」と「道短縮法 (compression)：調べた頂点の指す先をすべて根にする」
を使って頂点から根までの距離が短くなるようにしている。
//doit = 1 なら合併する
int find(int x, int y, int doit){ int t, i=x, j=y;
//xの属する木の根を探す while(dad[i] > 0) i=dad[i]; //yの属する木の根を探す while(dad[j] > 0) j=dad[j]; while(dad[x]>0){ t=x; x=dad[x]; dad[t]=i; } //道短縮法 (compression) while(dad[y]>0){ t=y; y=dad[y]; dad[t]=j; } //重さ均衡法 (weight balancing) //doitが 1 なら合併
if( (doit != 0) && (i != j) ){ if(dad[j] < dad[i]){ dad[j] += (dad[i]-1); dad[i]=j; }else{ dad[i] += (dad[j]-1); dad[j]=i; } } return (i != j);; }
上記の find 関数は「重さ均衡法 (Weight Balancing)」を使っているので木
の出力の際には重さ均衡法（根の親には -(子孫の数) が入っている）を考慮
しなければならない。
printf("-- view Union Find Tree --\n"); for(count=1; count<=V; count++){
if(dad[count] < 0) dad[count]=count;
printf("%c -> %c \n",getNodeName( dad[count] ),getNodeName(count)); }
A -> A
A -> B
A -> C
E -> D
A -> E
E -> F
A -> G
A -> H
H -> I
L -> J
L -> K
A -> L
L -> M
D E F J K M L A B C G H I図 10: 合併-発見木
ちなみに、道短縮法と重さ均衡法のほかには「高さ均衡法 (height
balanc-ing)」「分離法 (splitting)」「半減法 (halving)」などがある。
6
最小木
(Minimum Tree)
ー
Kruskal
法 ー
Kruskal
法はノードではなく辺の情報を用いる方法である、
「辺 e を重みの
小さい順に最小木の辺に採用する（ただし、e を採用することでヘ閉路がで
きないなら）」というアルゴリズムで、順位付きキューと find 関数を用いる
ことで実装することができる。
6.1
edge
構造体
Kruskal
法では辺の情報を用いるので、node 構造体ではなく edge 構造体
を用いる。edge 構造体では辺の両端のノード名と辺の重みを保存する。
struct edge{
char v1;//node v1
char v2;//node v2
int w;//wait
};
6.2
Kruskal
法の実装
まず辺の情報を保存した配列を用意する。
for(j=1; j<=E; j++){ //ファイルを一行読み込み fgets((char*)row,10,fp); sscanf(row,"%c-%c:%d",&e[j].v1,&e[j].v2,&e[j].w);printf("set e[%d] : %c <-> %c : %d \n",j,e[j].v1,e[j].v2,e[j].w); }
次に、それを順位付きキューに登録する。Kruskal 法では優先度の更新は
必要ないので pqupdate 関数と pqchenge 関数は必要ない。
pqconstruct(){ for(j=1; j<=E; j++){ pqinsert(j,e[j].w); if(debug_flag==1) pqdump(); } }ここまで用意できれば、あとはキューに登録されている辺を閉路ができな
いように注意しながら順番に取り出すだけ。
//クルスカル (Kruscal) 法for(pqconstruct(), i=0; pqueueempty()!=1;){ m=pqremove();
if( find( getNodeID(e[m].v1),getNodeID(e[m].v2),1 ) ){//閉路ができないなら printf("e[%2d] : %c - %c \n",m,e[m].v1,e[m].v2); i++; } }
グラフ３で実行すると以下のような結果が得られる。
e[ 1] : A - B
e[ 4] : B - C
e[ 9] : D - F
e[11] : E - G
e[15] : G - J
e[18] : I - K
e[19] : J - K
e[22] : L - M
e[ 2] : A - F
e[ 8] : D - E
e[13] : F - L
e[17] : H - I
D F A 2 E G H I J K M L 1 2 1 1 1 2 1 B C 1 1 2 1図 11: Kruskal 法を用いた最小木
7
最短経路木
(Shotest Path Tree)
最短経路木はその名の通り、根から各ノードへの最短経路を示す木である。
7.1
最短経路探索の実装
順位優先探索の visit 関数を改造することで容易に実装できる。ちなみに最
小木との違いは優先度を辺の重みではなく根から頂点までの重みの合計にし
ているところ。
visit(int k){ struct node *t;
if( pqupdate(k,unseen) != 0) dad[k]=0; while(!pqueueempty()){
id++;
k=pqremove(); val[k]=-val[k]; //親なら 0
if(val[k] = -unseen) val[k]=0;
for(t=adj[k]; t!=z; t=t->next){ if(val[t->v]<0){
if( pqupdate(t->v, (t->w)+val[k]) ){ //縁頂点は負 val[t->v]=-((t->w)+val[k]); dad[t->v]=k; } } } } }
