SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

翔泳社 新刊紹介(AD)

視覚的にイメージしにくいアルゴリズムを徹底的にイラストで表現するとこうなる

  • X ポスト
  • このエントリーをはてなブックマークに追加

幅優先探索――グラフ探索

 では、ここからアルゴリズムを紹介していきましょう。最初に紹介するのはグラフを探索するアルゴリズムの「幅優先探索」です。

 そもそもコンピューターサイエンスでいうグラフとは、複数個の頂点(ノード)が辺で結ばれたものをいいます。人間関係(ソーシャルグラフ)、路線図、コンピューターネットワークなど、様々なものをグラフで表現できます。

 これらのグラフを探索するためのアルゴリズムの一つである幅優先探索は、全貌のわからないグラフにおいて、始点から辺を辿りながら頂点を探索し、指定された頂点(ゴール)に辿り着けば目的達成です。端的には、頂点を探索する際、始点に近い頂点から優先的に探索していくアルゴリズムです。

リスト2-1

 まず、始点を定めましょう。今回はAです。ゴールとしてGを設定しますが、Gがどこにあるかは最初の時点ではわかりません。

リスト2-2

 Aから辿れる頂点B、C、Dが次に進む頂点の候補です。

リスト2-3

 候補の中から頂点を一つ選びます。選択の基準は、最も早く候補に追加されたものです(同じタイミングのときはどれでも構いません)。

リスト2-4

 今回はB、C、Dが同じタイミングで候補となったのでBを選択します。

リスト2-5

 Bに移動すると、Aが探索済みとなります。

リスト2-6

 Bから辿れるEとFを候補に追加しましょう。これで候補がC、D、E、Fとなりました。

リスト2-7

 C、D、E、Fのうち、最も早く候補になったのはCとDです。今回も左側のCを選択します。

リスト2-8

 Bから、選択したCに移動します。Bが探索済みとなります。

リスト2-9

 Cから辿れるHが新たに候補に加わります。現在の候補はD、E、F、Hです。

リスト2-10

 このように、ゴールに辿り着くか、すべての頂点を探索し終えるまで探索を繰り返します。

リスト2-11
リスト2-12
リスト2-13

 今回の例での選択順はA、B、C、D、E、F、H、I、J、K、そしてGとなりました。

 幅優先探索では文字どおり幅広く探索を行っていく特徴があります。当たり前のことですが、始点の近くにゴールがあるほうが探索が早く終了します。

 ちなみに、ここまで例として用いてきた連結して閉路のないグラフはと呼ばれています。また、始点と終点が同じ頂点である(閉路がある)グラフも同様に探索することができます。

次のページ
公開鍵暗号方式――セキュリティのアルゴリズム

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
翔泳社 新刊紹介連載記事一覧

もっと読む

この記事の著者

渡部 拓也(ワタナベ タクヤ)

 翔泳社マーケティング課。MarkeZine、CodeZine、EnterpriseZine、Biz/Zine、ほかにて翔泳社の本の紹介記事や著者インタビュー、たまにそれ以外も執筆しています。

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

【AD】本記事の内容は記事掲載開始時点のものです 企画・制作 株式会社翔泳社

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/10198 2017/06/13 07:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング