Report for Chap. 6

演習問題第6回グラフの探索(巡回): 横型探索(2016、2018年度)

■ 学籍番号による問題設定
・学籍番号の最下位桁の値によって指定された問題を各自の演習問題とします
◆前半グループ
・頂点数: 12
・全ての頂点について、次数(2 ≦ d ≦ 8)
・開始頂点: 1(末尾が偶数)、　2(末尾が基数)
・航路については、旅客／貨物、限定はしません。
番号　　頂点の意味　　　　　　　　　　辺　　　　　　次数制限
　　0: 　東日本の駅名　　　　　　　鉄道路線　次数5以上の頂点の総数4以上
　　1: 　東日本の駅名　　　　　　　鉄道路線　次数5以上の頂点の総数4以上
　　2: 　西日本の駅名　　　　　　　鉄道路線　次数5以上の頂点の総数4以上
　　3: 　西日本の駅名　　　　　　　鉄道路線　次数5以上の頂点の総数4以上
　　4: 　神奈川県のバス停　　　　バス路線　次数4以上の頂点の総数4以上
　　5: 　神奈川県のバス停　　　　バス路線　次数4以上の頂点の総数4以上
　　6: 　神奈川県のバス停　　　　バス路線　次数4以上の頂点の総数4以上
　　7: 　日本国内の空港都市名　航空路線　次数5以上の頂点の総数4以上
　　8: 　日本国内の空港都市名　航空路線　次数5以上の頂点の総数4以上
　　9: 　日本国内の空港都市名　航空路線　次数5以上の頂点の総数4以上
◆後半のグループ
　　0: 　　　　ヨーロッパの駅名、辺: 鉄道路線　　　　　次数5以上の頂点の総数3以上

　　1: 　　　　ヨーロッパの駅名、辺: 鉄道路線　　　　　次数5以上の頂点の総数3以上
　　2: 　　　　北アメリカの駅名、辺: 鉄道路線　　　　　次数5以上の頂点の総数3以上
　　3: 　　　　北アメリカの駅名、辺: 鉄道路線　　　　　次数5以上の頂点の総数3以上
　　4: 　　　　アフリカの空港都市名、辺: 航空路線　　次数5以上の頂点の総数3以上
　　5: 　　　　アフリカの空港都市名、辺: 航空路線　　次数5以上の頂点の総数3以上
　　6: 　　　　ヨーロッパの空港都市名、辺: 航空路線　次数5以上の頂点の総数4以上
　　7: 　　　　ヨーロッパの空港都市名、辺: 航空路線　次数5以上の頂点の総数4以上
　　8: 　　　　アジアの港湾都市名、辺: 航路　　　　　　　次数5以上の頂点の総数4以上
　　9: 　　　　アジアの港湾都市名、辺: 航路　　　　　　　次数5以上の頂点の総数4以上
・誤った問題番号、誤った設定値でレポートを提出、また複数の問題に対してレポート提出は受理されません。

6a 頂点オブジェクトの追加と縦型探索(巡回)の拡張
　現実世界の構造をグラフとしてモデル化する。その具体例として、鉄道路線、バス路線、航空航路を採り挙げる。これらの場合、それぞれでは頂点を、駅、バス停、空港とし、辺を、鉄道路線、バス路線、航空航路とするグラフとして表現できる。
　上記の問題設定に基づき、検索エンジンで実際の鉄道路線、航空航路、航路を調べ、描画ソフト(MS Paint、その他)でグラフを作成する。その際、グラフの頂点には、頂点番号だけでなく、名称を記述する。このグラフ(画像)を、レポートにはりつける(MS WORDファイルに画像を挿入する)。当該グラフに対する隣接リスト(アルゴリズム論Ⅰ第13回参照)を生成するためのデータを、ファイルでは無くプログラムの中で整数値の二次元配列として設定する。例えば、図6.8のデータの2次元配列のプログラム中での宣言の例は下記にようになる。
　　　int graph_array[5][5] = {
　　　　　　　　　　　　　　　　　{4, , , ,},
　　　　　　　　　　　　　　　　　{1, 3, 2, 3, 4},
　　　　　　　　　　　　　　　　　{2, 2, 1, 4, ,},
　　　　　　　　　　　　　　　　　{3, 2, 1, 4, ,},
　　　　　　　　　　　　　　　　　{4, 3, 1, 2, 3},
　　　　　　　　　　　　　　　　} ;
　出発頂点についても、変数に代入する。
上記の配列から隣接リストを生成できるように6.4節以下に記述されているプログラムを変更し、下記の2つの操作を実行する。
　(a) 上記配列の頂点番号、頂点各(駅名または都市名)とを出力する
　(b) 縦型探索(だけ)
レポートには13ページの出力画面に示されるような、訪問した順に頂点番号のリストを掲載すること。元のグラフからいくつかを辺を削除したグラフを上と同様に配列に格納し、縦型探索プログラムを稼動し、訪問頂点の順序の変化を明らかにし、その順序が正しいかどうか記載し、当該課題に対し様々な観点から考察せよ。

◆演習問題プログラム作成における注意事項

下記の要件を必ず満たすようにプログラムを作成せよ。

　(1) 最初に読み込むファイル名は絶対パスとしてmainプログラム中で記述し、コマンドライン上の引数による指定、およびリダイレクトによる入力指定はしないこと。

　　　例. char infile[80] = "/home/algorithm_data/texte.dat" ;

　(2) 比較回数、実行時間等、測定結果をプログラムの最後に出力する。