深さ優先検索疑問点について

Question

前提

入力として Nは頂点数６M辺数７とする
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}
２列３行の四角形になります。

bool visited[100009]; visited[pos]=false のとき頂点 x が白色、true のとき灰色
とします。

手順としては

『手順1.全ての頂点を白色で塗る
手順2.一番最初に頂点1を訪問し、頂点１を灰色で塗る
手順3.その後、以下の操作を繰り返す。頂点１で以下のaが当てはまったら検索終了。
a. 隣接する頂点がすべて灰色である場合、一歩だけ戻る。
b. そうでは無い場合、隣接する白色頂点のうち番号が最小の頂点を訪問する。新たに頂点を訪問する際には、その頂点を灰色で塗る。
手順4.最終的にすべての頂点が灰色で塗られた場合、グラフは連結する。』
引用：問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 単行本（ソフトカバー） – 2021/12/25
米田 優峻 (著)

出力としてはこのグラフが連結であるかどうかを求めるプログラムです

発生している問題

void dfs(int pos) {
	visited[pos] = true;
	// for (int i : G[pos]) のような書き方を「範囲 for 文」といいます。（APG4b 2.01 節）
	for (int i : G[pos]) {
		if (visited[i] == false) dfs(i);
	}
}

この部分で
最初にint pos で定義したのにvisited[pos] = true;とposがbool型になるのは問題ないのですか

void dfs(int pos) {
	visited[pos] = true;// 手順2.一番最初に頂点1を訪問し、頂点１を灰色で塗る
	// for (int i : G[pos]) のような書き方を「範囲 for 文」といいます。（APG4b 2.01 節）
	for (int i : G[pos]) {
		if (visited[i] == false) dfs(i);
	}
}

上記の部分は手順で言うと下記と対応していると思います。
『手順2.一番最初に頂点1を訪問し、頂点１を灰色で塗るvisited[pos] = true;このプログラムと対応している。
手順3.その後、以下の操作を繰り返す。頂点１で以下のaが当てはまったら検索終了。
a. 隣接する頂点がすべて灰色である場合、一歩だけ戻る。
b. そうでは無い場合、隣接する白色頂点のうち番号が最小の頂点を訪問する。新たに頂点を訪問する際には、その頂点を灰色で塗る。』
で

for (int i : G[pos]) {
		if (visited[i] == false) dfs(i);
	}
}

この上記のプログラムでは
手順3.その後、以下の操作を繰り返す。頂点１で以下のaが当てはまったら検索終了。
a. 隣接する頂点がすべて灰色である場合、一歩だけ戻る。
b. そうでは無い場合、隣接する白色頂点のうち番号が最小の頂点を訪問する。新たに頂点を訪問する際には、その頂点を灰色で塗る。
と対応していると思いますが
隣接する頂点がすべて灰色である場合、一歩だけ戻るとプログラムで記述されているようには思えません。
また、最小の頂点を訪問しているとプログラムで記述されているようには思えません。どのように動いているのかご教授お願いできませんか

該当のソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, A[100009], B[100009];
vector<int> G[100009];
bool visited[100009]; // visited[pos]=false のとき頂点 x が白色、true のとき灰色

void dfs(int pos) {
	visited[pos] = true;
	// for (int i : G[pos]) のような書き方を「範囲 for 文」といいます。（APG4b 2.01 節）
	for (int i : G[pos]) {
		if (visited[i] == false) dfs(i);
	}
}

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]);
	}

	// 深さ優先探索
	dfs(1);

	// 連結かどうかの判定（Answer=true のとき連結）
	bool Answer = true;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) Answer = false;
	}
	if (Answer == true) cout << "The graph is connected." << endl;
	else cout << "The graph is not connected." << endl;
	return 0;
}

補足情報（FW/ツールのバージョンなど）

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 単行本（ソフトカバー） – 2021/12/25
米田 優峻 (著)
4.5.6深さ優先検索P１７０〜１７２

Comments

[Crimson_Tide]

[そうでは無い場合、隣接する白色頂点のうち番号が最小の頂点を訪問する。]には注記があります。
>注 4.5.4 ここでは説明の都合上このようにしていますが、番号が最小の頂点でなくても、 隣接する白色頂点の中から適当に1つ選べばアルゴリズムは正しく動作します。
引用元:米田 優峻. 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 (p.352). 株式会社技術評論社. Kindle 版.
入力データ次第で最小の頂点を訪問するようになるだけの話なので、「最小の頂点を訪問する処理になっている」かどうかを考える必要はありません。

[fana]

> この部分で
> 最初にint pos で定義したのにvisited[pos] = true;とposがbool型になるのは問題ないのですか

↑この文章の意味が全くわからないのですが．

[Crimson_Tide]

一連の質問者さんの質問を見る限り基本的なプログラミング、C++の基礎知識がないように見受けられます。
visited[pos] = trueが posにtrueが代入されて型が変わっているように見える、とかかと想像。
例えるなら算数すっ飛ばして中学数学に取り組もうとしている小学生が、習ったことのない掛け算を勝手に解釈しているようなものかと・・・

1. 3. 3 　 前提 と なる 知識
また、 本書 では いくつ かの ソース コード を 掲載 し て いる ため、 プログラミング に 触れ た こと が あり、 1 つ 以上 の プログラミング 言語 で 基礎的 な 文法 を 習得 し て いる こと が 望ましい です。
米田 優峻. 問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 (p.25). 株式会社技術評論社. Kindle 版.
質問者さんはまずC++の基礎を学習されるべきです。

[jaogjig]

了解しました。C++の基礎をやってみます。

[jaogjig]

基礎学習をしました。
visited[pos] はデータ配列の空の変数が入っているだけで
= trueが posにtrueが代入されて型が変わっているように見える、
のではなくて
bool visit[ここの数字が整数の（posのint）型１]{0,1,2,3...100008}
1番目にtrueを入れているだけである。
ってことで合っていますか
自分はintとboolの型が外の配列をbool visit[１]と決めたら変えられないと思っていました。
中の数字にもデータ型を決められることが分かりませんでした。

Answer 1

動作のイメージ確認用にcoutによる状態出力を追加してみました。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, A[100009], B[100009];
vector<int> G[100009];
bool visited[100009]; // visited[pos]=false のとき頂点 x が白色、true のとき灰色

void dfs(int pos) {
    cout << "starting dfs(" << pos << ")" << endl;
	visited[pos] = true;
	// for (int i : G[pos]) のような書き方を「範囲 for 文」といいます。（APG4b 2.01 節）
	for (int i : G[pos]) {
        cout << "in dfs(" << pos << ") for loop" << endl;
        cout << "  i = " << i << endl;
		if (visited[i] == false) dfs(i);
	}
    cout << "exiting dfs(" << pos << ")" << endl;
}

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]);
	}

	// 深さ優先探索
	dfs(1);

	// 連結かどうかの判定（Answer=true のとき連結）
	bool Answer = true;
	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) Answer = false;
	}
	if (Answer == true) cout << "The graph is connected." << endl;
	else cout << "The graph is not connected." << endl;
	return 0;
}

この状態でプログラムを実行すると以下のようなログになります。
ログを読んでいくと以下のようなことが分かります

• dfs(6)が呼び出されるのは、dfs(5)のforループの中から
• dfs(6)内で6に隣接するノード5, 4をチェックするが、訪問済(visited[i] == true)なので、ここからdfs(5), dfs(4)を呼び出すことはない
• dfs(6)終了後、dfs(5)のforループに戻って実行を続けている

// グラフ情報の入力
6 7
1 3
1 2
5 6
2 4
2 5
3 4
4 6

// プログラムからの出力
starting dfs(1)
in dfs(1) for loop
  i = 3
starting dfs(3)
in dfs(3) for loop
  i = 1
in dfs(3) for loop
  i = 4
starting dfs(4)
in dfs(4) for loop
  i = 2
starting dfs(2)
in dfs(2) for loop
  i = 1
in dfs(2) for loop
  i = 4
in dfs(2) for loop
  i = 5
starting dfs(5)
in dfs(5) for loop
  i = 6
starting dfs(6)
in dfs(6) for loop
  i = 5
in dfs(6) for loop
  i = 4
exiting dfs(6)
in dfs(5) for loop
  i = 2
exiting dfs(5)
exiting dfs(2)
in dfs(4) for loop
  i = 3
in dfs(4) for loop
  i = 6
exiting dfs(4)
exiting dfs(3)
in dfs(1) for loop
  i = 2
exiting dfs(1)
The graph is connected.

---

ご質問にある本は持っていないのですが、a, bの説明を以下のように少し変更して読んでみてはいかがでしょうか。

a. 隣接する頂点がすべて灰色である場合、(dfs関数を抜けることで)一歩だけ戻る。
b. そうでは無い場合、現在のノードposに隣接する頂点(G[pos])を順番に見ていき、最初に白色になっている頂点を訪問する(dfs(i)を呼び出すことで一歩進む)。新たに頂点を訪問する際には、その頂点を灰色で塗る。

これで、下記のようなグラフ情報が与えられたとします。

6 7
1 3
1 2
5 6
2 4
2 5
3 4
4 6

この場合、dfs(1) -> dfs(3) -> dfs(4) -> dfs(2) -> dfs(5) -> dfs(6) と次々にdfs()関数を呼び出して一歩ずつ順調に進んでいきます。しかし、dfs(6)まできたところで「隣接する頂点が全て灰色」になります。
次のdfs()関数を呼び出すことができないので、そのままforループを抜けてdfs(6)を終了し、一歩戻ってdfs(5)関数に返ってきます。
dfs(5)でもaの条件が発生するので一歩戻ってdfs(2)に返ります。
同じことが続いて dfs(4) -> dfs(3) -> dfs(1) と一歩ずつ戻ってきて、最終的にmain()へ戻ります。

Comments

[jaogjig]

回答ありがとうございます。
＜そのままforループを抜けてdfs(6)を終了し、一歩戻ってdfs(5)関数に返ってきます。
dfs関数を抜けることでと書いてありますがなぜdfs関数を抜けると一歩戻ってdfs関数がまた使われるのかが分かりません。

[退会済みユーザー]

長くなるので解答にサンプルコードを追記しました。

[jaogjig]

回答ありがとうございます。
どうやって動いているのかはすごく分かりやすくなりました。
＜dfs(6)終了後、dfs(5)のforループに戻って実行を続けている
と書いてありますが、何が働いてdfs(５)のforループに戻って実行を続けているのですか

自分はdfs(6)終了後、”void dfs(int pos) {”の部分が働いてdfs(５)のforループに戻って実行を続けていると思いましたが違うようでした。

[退会済みユーザー]

「何が働いて」というのが、どのような粒度での答えを想定しているのか不明ですが、
たとえば現在のプログラムでは、main関数からdfs(1)を呼びだすと、main関数での処理を一旦中断してdfs(1)内でいろいろな処理を行ないますよね。このdfs(1)での処理が終了した後、main関数に戻ってきて残りの処理を続けてグラフが連結かどうかを表示します。
これと同じで dfs(5)からdfs(6)を呼び出すと、dfs(5)のforループ内での処理を一旦中断してdfs(6)でいろいろな処理を行ないます。dfs(6)が終了すると、dfs(5)に戻ってきてdfs(6)を呼び出した直後の部分から処理を再開します。

[jaogjig]

回答ありがとうございます。
dfs(1) -> dfs(3) -> dfs(4) -> dfs(2) -> dfs(5) -> dfs(6) と続いて各関数がループの途中だったからdfs(1) <- dfs(3) <-dfs(4) <-dfs(2) <-dfs(5)と処理が続行するということですか

[退会済みユーザー]

そうですね。ログ出力のstarting... や exiting...を読むとどのような順番で開始/終了したか分かります。グラフの頂点や辺の設定をいろいろと変えて納得いくまで動かしてみると良いと思います。