第15回では，以下の項目に関して学ぶ．

  1. グラフとその表現
  2. グラフに対する深さ優先探索と幅優先探索

課題のソースコードのテンプレート:

課題1: グラフの表現

対象とそれらの関係を抽象的に表現するのに適したデータ構造にグラフ(graph)がある．グラフは，頂点(vertex)の集合と頂点を結ぶ辺(edge)の集合で構成される．辺に方向がない場合を無向グラフ(undirected graph)，辺に方向がある場合を有向グラフ(directed graph)と呼ぶ．それぞれのグラフを図15.1に示す．


図15.1: (a) 無向グラフ と (b) 有向グラフ の例

ここでは，頂点の集合 V と辺の集合 E で構成される有向グラフ G = (V, E) を考える．2つの頂点 v ∈ V と u ∈ V に対して，それらを結ぶ辺を e = (v, u) ∈ E とおく．このとき，v と u は隣接する(adjacent)という．特に，有向グラフのとき，v を始点(source)，u を終点 (destination) と呼ぶ．

グラフの実現方法には，隣接行列(adjacenct matrix)と隣接リスト(adjacency list)がある．

隣接行列では，頂点 v と 頂点 u に(有向)辺がある場合に，行例の(v, u) 要素の値を 1，(有向)辺がない場合に 0 とする．図15.1(b)の有向グラフの隣接行列による表現を図15.2(a)に示す．行列を2次元配列 matrix[][] で実現した場合，matrix[v][u] の値が 1 か 0 となる．

一方，隣接リストでは，頂点 v に対して，最大|V|個の隣接頂点 u をリストで実現する．図15.1(b)の有向グラフの隣接リストによる表現を図15.2(b)に示す．


図15.2: (a) 隣接行列による表現と (b) 隣接リストによる表現 の例

グラフの頂点を graph-common.h で定義されている以下の構造体で実現する．

struct vertex {
    int no;
    char label;
    struct adjacence *adj;
};
no は頂点の識別番号，label は頂点のラベル(頂点に格納するデータ)，adj は隣接リストの先頭のポインタを指す．隣接頂点が存在しない場合は，adj を NULL とする．

struct adjacence は，以下のように定義されている． 

struct adjacence {
    int no;
    struct adjacence *next;
};
no は頂点の識別番号，next は隣接頂点の識別番号を格納する構造体オブジェクトへのポインタを指す．

いま，グラフを実現するために，graph-check.c に，以下に示す3つの関数を用意した．

(1) 空のグラフ(頂点と辺を持たない)を生成する．
struct graph *create_graph();
(2) graph の隣接行列を画面に表示する．
void print_matrix(struct graph *graph);
(3) graph の隣接リストを画面に表示する．
void print_list(struct graph *graph);

ここでは，有向グラフに対して，以下に示す4つの関数を持つ prog15-1.c を作成する．

(1) ラベルの値 label を格納した頂点を生成し，graph に追加する．生成した頂点へのポインタを返す．
struct vertex *add_vertex(struct graph *graph, char label);
(2) 頂点 src と を結ぶ辺を生成し，graph に追加する．
void add_edge(struct graph *graph, struct vertex *src, struct vertex *dst);
(3) graph に含まれる頂点の総数を取得する．
int get_vertex_num(struct graph *graph);
(4) graph に含まれる辺の総数を取得する．
int get_edge_num(struct graph *graph);

これらの関数を作成する際には，graph-common.h をインクルードし，graph-check.o をリンクすること．


上記の4つの関数とテストコードを含む prog15-1.c を作成せよ．

本課題では，図15.1(b)の有向グラフを構築し，隣接行列と隣接リストの正しさを確認するテスト関数 test1() を作成せよ．さらに，図15.1(b)以外の有向グラフを構築するテスト関数を追加せよ．
Go to Top