V - Researchmap

THE UNIVERSITY OF TOKYO
数理情報工学演習第一Ｃ
プログラミング演習 (第7回 )
2014/05/26
DEPARTMENT OF MATHEMATICAL INFORMATICS
1
THE UNIVERSITY OF TOKYO
今日の内容:
 グラフの表現，探索
 スタック，キュー
 再帰呼び出し
 深さ優先探索，幅優先探索
 課題：グラフ探索
2
THE UNIVERSITY OF TOKYO
グラフ
• グラフ G = (V, E)
– V: 頂点 (節点) 集合 {1,2,…,n}
– E: 枝集合, E  V  V = {(u,v) | u, v  V}
• 無向グラフ
– 枝は両方向にたどれる
15
2
50
30
20
10
1
• 有向グラフ
4
5
80
– 枝 (u,v) は u から v の方向のみたどれる
3
15
– 注: 無向グラフは有向グラフで表現できる (枝数を倍にする)
• 枝には重み(長さ)がついていることもある
– なければ全て長さ 1 とみなす
3
THE UNIVERSITY OF TOKYO
有向グラフのデータ構造
• 各節点 u ごとに，そこから出ている枝 (u,v) をリストに格納する
• u は共通なので v だけリストに入れる
• 枝に重み w がついているときは (v, w) をリストに入れる
typedef struct {
int n; // 節点数
int m; // 枝数
dlist **E; // 枝リストの配列
typedef struct dlobj_{
struct dlobj_ *next;
struct dlobj_ *prev;
int v;
double w;
} dlobj;
} graph;
4
THE UNIVERSITY OF TOKYO
15
2
50
30
20
10
1
5
80
E
1
2
3
4
5
5
4
3
v
2
3
4
5
重み
50
20
10
30
15
3
4
5
80
15
15
THE UNIVERSITY OF TOKYO
グラフ探索
• 点 s から点 t へのパス (path) を求める
• パス: s = v0, v1, v2, …, vn-1, vn= t
– (vi, vi+1)  E
– vi は全て異なる
– 長さ n
15
2
50
4
30
20
10
1
5
80
3
15
– パスの重みは枝の重みの和
• 点 s から点 t への最短パス (shortest path) を求める
– 重み最小のパス
• グラフの連結成分，強連結成分を求める等
6
THE UNIVERSITY OF TOKYO
グラフのデータ構造
• 点 u の枝リストの中身は，(v, w)
– v は枝 (u,v) の終点
– w は枝の重み (長さ)
• graph *graph_input(char *filename);
typedef struct {
int n; // 節点数
int m; // 枝数
dlist **E; // 枝リストの配列
} graph;
– グラフをファイルから読み込む
• dlobj *graph_firstedge(graph *G, int i);
– 点 i から出ている枝のうち最初の1本を返す
– 枝が1本も出ていなければ NULL を返す
• dlobj *graph_nextedge(graph *G, int i, dlobj *e);
– 点 i から出ている枝で e の次のものを返す
7
– e が最後の枝なら NULL を返す
THE UNIVERSITY OF TOKYO
グラフのファイル構造
15
2
50
4
30
20
10
1
5
80
3
15
5 7 //節点数，枝数
2 50 3 80 -1 // 点 1 から出ている枝
3 20 4 15 -1 // 点 2 から出ている枝
4 10 5 15 -1
5 30 -1
-1
// 点 5 から出ている枝は無い
8
THE UNIVERSITY OF TOKYO
スタックとキュー
動的集合，挿入と削除をサポートする
スタック (stack) では，deleteでは最後に挿入された要素が取り除かれる
後入れ先出し (last-in, first-out; LIFO) という
キュー (queue) では，最初に挿入された要素が取り除かれる
先入れ先出し (first-in, first-out; FIFO) という
9
THE UNIVERSITY OF TOKYO
スタック (Stack)
insert, deleteの代わりにpush, popと呼ぶ
push(S,x): 集合 S に要素 x を加える．
pop(S): S から最後に push された要素を削除し，その要素を返す
push(S,15)
pop(S)
10
15
692
9
2
6
15
THE UNIVERSITY OF TOKYO
配列によるスタックの実装
最大 MAX 要素を格納できるスタックを実装
スタックを表す構造体
top: 最後に挿入された要素の格納場所(= 要素数)
S: 要素を格納するサイズMAXの配列(へのポインタ)
MAX: 配列 S のサイズ
要素は S[1..top] に格納される
S[1]: スタックの底
S[top]: スタックの最上部
top  MAX
11
typedef int data;
typedef struct {
int top;
int MAX;
data *S;
} stack;
THE UNIVERSITY OF TOKYO
実装例
• push(S,x)
– topを1増やし，x を配列に
入れる
– topがMAXを超えたらエラー
– O(1) 時間
void push(stack *s,data x)
{
if (s->top == s->MAX) {
printf("オーバーフロー\n");
exit(1);
}
s->top = s->top + 1;
s->S[s->top] = x;
12}
• pop(S)
– スタックが空ならエラー
– サイズを1減らし，最上部
の要素を返す
– O(1) 時間
data pop(stack *s)
{
if (STACK_EMPTY(s)) {
printf("アンダーフロー\n");
exit(1);
}
s->top = s->top - 1;
return s->S[s->top + 1];
}
THE UNIVERSITY OF TOKYO
その他の関数
• stack_empty(S)
– スタックが空なら1を返す
– O(1) 時間
int stack_empty(stack *S)
{
if (S->top == 0) return 1;
else return 0;
}
13
• stack_new(size)
– 最大サイズ size のスタッ
クを作成する
stack *stack_new(int size)
{
stack *s;
data *S;
s = malloc(sizeof(stack));
S = malloc((size+1)*sizeof(data));
s->top = 0;
s->MAX = size;
s->S = S;
return s;
}
THE UNIVERSITY OF TOKYO
キュー (Queue)
INSERT, DELETEの代わりにENQUEUE, DEQUEUEと呼ぶ
人の並んだ列と同じ
ENQUEUEでは列の最後に追加
DEQUEUEでは列の先頭を取り出す
DEQUEUE(Q)
Q
15
14
6
2
ENQUEUE(Q,x)
9
THE UNIVERSITY OF TOKYO
配列によるキューの実装
最大 MAX1 要素を格納できるキュー
キューを表す構造体
typedef struct {
int head;
int tail;
int MAX;
data *Q;
} queue;
Q: 要素を格納する配列
MAX: 配列 Q のサイズ
head: キューの先頭の位置
tail: 次に追加される位置
1
15
2
3
4
5
6
7
8
9 10 11 12
15
6
9
head
8
4
tail
THE UNIVERSITY OF TOKYO
環状バッファ (Ring Buffer)
配列 Q の右端と左端はつながって輪になっていると考える
Q[MAX] の右は Q[1] だとみなす
要素は Q[head..MAX] Q[1..tail1] に格納される
DEQUEUEの際に全要素を左にずらす必要がない
16
1
2
3
5
3
tail
4
5
6
7
8
9 10 11 12
15
6
9
head
8
4
17
THE UNIVERSITY OF TOKYO
空のキューの作成
queue_new(size)
size 個の要素を格納できる空のキューを作成
17
queue *queue_new(int size)
{
queue *q;
data *Q;
size = size+1;
q = (queue *)malloc(sizeof(queue));
Q = (data *)malloc((size+1)*sizeof(data));
q->head = 1;
q->tail = 1;
q->MAX = size;
q->Q = Q;
return q;
}
THE UNIVERSITY OF TOKYO
実装例
• ENQUEUE(Q,x)
– x をQ[tail]に入れる
– tailを1増やす
– O(1) 時間
void enqueue(queue *q,data x)
{
q->Q[q->tail] = x;
if (q->tail == q->MAX)
q->tail = 1;
else q->tail = q->tail + 1;
}
注: オーバーフロー, アンダーフロー
処理は省略してある
18
• DEQUEUE(Q)
– Q[head]を取り出す
– headを1増やす
– O(1) 時間
data dequeue(queue *q)
{
data x;
x = q->Q[q->head];
if (q->head == q->MAX)
q->head = 1;
else q->head = q->head + 1;
return x;
}
THE UNIVERSITY OF TOKYO
配列を用いたスタック，キューの問題点
•
最大要素数を初めに決める必要がある
•
任意の数を格納できるようにするには？
1. 配列がいっぱいになったら，より大きい配列を用意する
•
p = realloc(p, (新しいサイズ));
•
p のアドレスは変わることがあるので注意
2. 配列の代わりにリストを用いる
19
•
キューではリストの末尾に追加する
•
スタックではリストの先頭に追加する
THE UNIVERSITY OF TOKYO
再帰呼び出し
• 関数が，自分自身を呼び出すこと (recursive call, recursion)
• 再帰を使ってアルゴリズムを設計すると，簡単になることが多い
• 関数内部で宣言される変数は，CPUのスタック上に確保される
• 逆に，スタックを明示的に使って再帰呼び出しを無くすこともできる
int factorial(int n)
{
int x;
if (n == 0) return 1;
x = factorial(n-1);
return n * x;
}
20
THE UNIVERSITY OF TOKYO
深さ優先探索，幅優先探索
• 木やグラフの探索法
• 深さ優先探索 (depth-first search, DFS)
– 行き止まりになるまで先に進む
• 幅優先探索 (breadth-first search, BFS)
– 全体を同時に探索する
• DFSはスタック(再帰)，BFSはキューで実現できる
1
2
3
21
1
2
5
4
DFS
6
4
3
5
6
BFS
THE UNIVERSITY OF TOKYO
課題1: スタック(再帰)を用いて s-t パスを求める
• dlist *graph_findpath(graph *G, int s, int t);
– 点 s から点 t へのパスを 1 つ求める
– 答えはリストで返す
– リストの要素はグラフで用いているものと同じでよい
(keyは節点番号，valueは使わない)
– パスが無ければ NULL を返す
22
THE UNIVERSITY OF TOKYO
アルゴリズムの方針
• s から t へのパスを求めるには
– s の隣接点の1つを v とする
– v == t ならば s-t パスが見つかったのでそれを返す
– v から t のパス P を再帰的に求める
– 存在すれば，P の先頭に s を追加すれば答えが求まる
– 存在しなければ，s の次の隣接点に対し同様に探す
– s の全ての隣接点を試してパスが見つからなければ s-t パスは存在しない
• これをそのままプログラムにすればよい
• 注: v を過去に訪れている場合は2回目以降は訪れないようにする
– 訪れたかどうかを整数配列に記憶しておく visited[v] =1; // 訪れた
23
THE UNIVERSITY OF TOKYO
• graph_findpath(graph *G, int s, int t) を再帰関数にするのではなく，
その内部で別の再帰関数を呼ぶようにする
dlist *graph_findpath(graph *G, int s, int t)
{
int *visited;
dlist *path;
int i;
mymalloc(visited, G->n);
for (i=0; i<G->n; i++) visited[i] = 0;
path = findpath_sub(G, s, t, visited);
free(visited);
return path;
}
• 再帰関数のデバッグをするときは，関数の最初にprintfで変数を表示する
と良い．もしくはデバッガ (gdb) を使ってステップ実行する．
24
THE UNIVERSITY OF TOKYO
課題2: キューを用いて s-t 間距離を求める
• 注: 今回は枝の長さは使わない (全て 1 とみなす)
• キューは前々回の双方向リストをそのまま用いても良い
• s の隣接点全てをキュー Q1 に入れる
• Q1 の要素は，s からの距離が 1 の点全て
• Q1 の各要素 u に対し，u の隣接点をキュー Q2 に入れる
– u が過去に訪れた (キューに入れられた) 点なら Q2 には入れない
• Q2 の要素は，s からの距離が丁度 2 の点全て
• Q2 が求まったら，Q1 は free する
• Qd に t が入れば，s から t の最短距離は d
25
– 実際のパスは求めなくてもいい
THE UNIVERSITY OF TOKYO
• プログラムのソースコードと，動作確認に使ったグラフのファイルを提出
• 5/30(金) の正午までに提出
• 宛先：[email protected]
26
THE UNIVERSITY OF TOKYO

Download Report