点の数: 7
辺行列:E=| 0 3 2 4 6 1 2 0 0 4 2 |
| 1 1 4 3 3 4 3 4 5 5 6 |
コンピュータでグラフGを利用する場合,辺行列をファイルに記述しておき,ファイル入出力関数を利用して読み込むことが多い.
Graph1.txt
_______________
7
0 1
3 1
2 4
4 3
6 3
1 4
2 3
0 4
0 5
4 5
2 6
_______________
1 行目:点の数
2 行目~最終行: 辺情報
【1】
graph1.txt にて表現される無向グラフに対し,2 次元配列adjacent[N_MAX][N_MAX]を利用して隣接行列を格納するようなプログラムを作成せよ.
作成の条件:
(1) graph1.txtを作成し,fscanfなどのファイル入力関数を利用して情報を読み込むこと.
(2) 点の数と辺の数を記憶する変数(N, M)を準備しておくこと.
(3) N_MAXは100とすること.
(4) graph1.txtからの読み込みが正常に行われたかどうかを確認するため,adjacent配列をprintfなどにより画面表示すること.
【2】
【1】では配列をあらかじめ100×100 として用意しているが,点の数は7 しかなく,実際に利用されるのは7×7 の領域のみとなり無駄が多い.そこで【1】で利用する2次元配列を2次元ポインタ変数( int **adjacent; )として定義し,graph1.txt の1 行目を読み込んでから必要な配列をmallocするようにプログラムを修正せよ.
【3】
graph1.txtにて表現される無向グラフに対し,隣接行列を格納する2 次元ポインタ変数adjacentを利用して,すべての点の次数とグラフの平均次数を算出して表示するプログラムを作成せよ.【2】で作成したプログラムを利用(拡張)すること.
【4】
graph1.txtにて表現される無向グラフに対し,点v0からスタートして点v6に到着するまで隣接する点にランダムに移動を行った場合の経路(閉路を含んでもよい)を表示するプログラムを作成せよ.
・現在の点をpos,移動後の点をnextとし,乱数を利用してnextを決定する.pos の初期値は0.
・extを決定する際,接続関係がわかるように隣接行列を利用する.
・extが6 になれば終了.そうでなければpos←nextとして上の処理を繰り返す.
・rand48()関数を使うことで,0 以上1 未満の倍精度実数乱数を作成することができる.例えば,0 以上s(整数)未満の乱数を発生させたい場合には,次式のようにする.
r = drand48() * s;
・乱数の初期化には,srand48()関数を使う.引数に乱数の種(正整数)を入れる.この値を変化させることで,異なる乱数系列が発生する.例: srand48( 4 );
・乱数の種にtime()関数などを用いてはいけない.コンピュータシミュレーションでは,同じ環境で再実験できることが重要であるので,乱数の種は自分で決めた定数を使うこと