スポンサーリンク

幅優先探索をc言語で実装

隣接リスト

隣接リストで、上記の経路を表現します。
深さ優先探索の時と経路は同じにしています。
参考:[c言語]隣接リストで深さ優先探索を実装

通過予定経路を管理するために、下記配列を初期化して用意します。

下記が、深さ優先探索のサンプルコードになります。
キューの関数についても実装しています。
下段にサンプルコードとして載せています。
下記で紹介したキューの実装とは少々変えています。
pop()時に値をreturnするようにしたのと、isEmpty()も追加しています。
参考:キューのデータ構造をC言語で実装

引数のstartは探索の開始位置、targetは探索ターゲット位置になります。

スポンサーリンク

サンプルコード

下記がサンプルコードになります。

下記が実行結果になります。
Route:Xが、実際に通過した経路になります。
targetが探索されるとFound targetと表示しています。

スポンサーリンク