質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

2回答

3179閲覧

幅優先探索のアルゴリズムについて

Gatmaster

総合スコア13

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2017/03/18 15:34

深さ優先探索は再帰関数を利用して行うことができます。
幅優先探索においては再帰関数を利用することはできるのでしょうか??
(javaもしくはC、C++)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

再帰関数で全く作れないというわけではないようです。

なぜ Haskell ではキューが軽んじられているか? - あどけない話

上記記事では幅優先探索を再帰関数で実装しています(そもそもHaskellにはループ構文がないので再帰で書くしかないのですが)。キューの代わりに木を使ってそれを探索するようにしているようです。(細かい所は追ってないので私も詳しくは説明できないです)

ただ、この実装は余再帰というものを使っています。遅延評価であるHaskellでは問題ないようですが、正格評価であるC/C++ではスタックオーバーフローを起こす場合があるため、使えないと思われます(末尾再帰最適化すらできないJavaは論外)。

投稿2017/03/18 23:23

編集2017/03/18 23:25
raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

こんにちは。

幅優先探索はキューを使います。キューをスタックに変えると深さ優先探索になります。
そして、再帰処理はスタックを使って処理しますが、再帰処理をキューで実装するのは無理です。

投稿2017/03/18 15:46

編集2017/03/18 15:46
Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Gatmaster

2017/03/18 15:51

早い回答ありがとうございます。わかりやすかったのでベストアンサーにさせていただきます。 実はスタックとキューを理解しておらず、深さ優先探索を再帰関数を用いて行っていました。そのため、幅優先探索も再帰関数を用いてなんとかできないかという考えに至ったわけでして、、、。 とりあえずキューとスタックを勉強してみます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問