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

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

新規登録して質問してみよう
ただいま回答率
86.12%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

受付中

幅優先検索の疑問点について

jaogjig
jaogjig

総合スコア16

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0リアクション

1クリップ

325閲覧

投稿2022/09/06 09:35

編集2022/09/06 10:37

前提

入力として Nは頂点数6M辺数7とする
A[100009]配列
B[100009]配列
この二つは隣接しているリストとする
「vector<int> G[100009];」のGは頂点の番号を表している。
このようにA[i]B[i]に以下のように入力例とする
G1:{2,3}
G2:{1,4,5}
G3{1,4}
G4{2,3,6}
G5{2,6}
G6{5,4}
2列3行の四角形になります。

手順としては
手順1.全ての頂点を白色で塗る。
手順2.キューQに頂点1を追加する。dist[1]=0とし、頂点1を灰色で塗る。
手順3.キューQが空になるまで、以下の操作を繰り返す。
Qの先頭の要素posを調べる。
Qの先頭の要素を取り出す。
頂点posに隣接し白色で塗られている頂点nexについて、dist[nex]をdist[pos]+1
に更新し、Qにnexを追加する。キューに頂点を追加する際には、その頂点を灰色に塗る。
出力としては
頂点1から各頂点までの最短経路長を求める

発生している問題・エラーメッセージ

// 幅優先探索 while (!Q.empty()) { int pos = Q.front(); // Q の先頭を調べる(操作 2) Q.pop(); // Q の先頭を取り出す(操作 3) for (int i = 0; i < (int)G[pos].size(); i++) { int nex = G[pos][i]; cout<<G[pos][i]<<":"<<endl; if (dist[nex] == -1) { dist[nex] = dist[pos] + 1; cout<<dist[nex]<<"@"<<endl; Q.push(nex); // Q に nex を追加(操作 1) } } }

わからないところが2つあります。
1つ目は
「cout<<G[pos][i]<<":"<<endl;」の部分の出力を出力
2: ...*14と続いているのですが[pos][i]と二つの配列があるのに一つの数字しか出力されません。理由が分かりません。

2つ目は
.size()はG[]配列では[123456]と6要素しかないはずなのに14回for文が回っています。A[]B[]の合計が14個あるので14回回ると考えていますが、配列が具体的にどうなるのかイメージがつきません。
ご教授お願いします。

該当のソースコード

#include <iostream> #include <vector> #include <queue> using namespace std; int N, M, A[100009], B[100009]; int dist[100009]; vector<int> G[100009]; int main() { // 入力 cin >> N >> M; for (int i = 1; i <= M; i++) { cin >> A[i] >> B[i]; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } // 幅優先探索の初期化(dist[i]=-1 のとき、未到達の白色頂点である) for (int i = 1; i <= N; i++) dist[i] = -1; queue<int> Q; // キュー Q を定義する Q.push(1); dist[1] = 0; // Q に 1 を追加(操作 1) // 幅優先探索 while (!Q.empty()) { int pos = Q.front(); // Q の先頭を調べる(操作 2) Q.pop(); // Q の先頭を取り出す(操作 3) for (int i = 0; i < (int)G[pos].size(); i++) { int nex = G[pos][i]; if (dist[nex] == -1) { dist[nex] = dist[pos] + 1; Q.push(nex); // Q に nex を追加(操作 1) } } } // 頂点 1 から各頂点までの最短距離を出力 for (int i = 1; i <= N; i++) cout << dist[i] << endl; return 0; }

試したこと

// 幅優先探索 while (!Q.empty()) { int pos = Q.front(); // Q の先頭を調べる(操作 2) Q.pop(); // Q の先頭を取り出す(操作 3) for (int i = 0; i < (int)G[pos].size(); i++) { int nex = G[pos][i];// cout<<G[pos][i]<<":"<<endl;//ここを出力してどこがわからないか試した

test

入力 6 7 1 2 1 3 2 5 3 4 4 2 4 6 5 6 6 4 出力 2: 3: 1: 5: 4: 1: 4: 2: 6: 3: 2: 6: 4: 5: 0 1 1 2 2

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
86.12%

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

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

質問する

関連した質問

同じタグがついた質問を見る

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。