競プロで、ロジックの勉強してるときに、分からなくて色々調べたら、 タイトルにある、DFS関数にたどり着いた。
深さ優先探索 というワードの意味が、いまいちピンとこなくて、他のないのかな〜って思うけど、そこが味噌ではないから、まあ、ええかと。。。
調べると、C系言語で書かれた例が見つかった。ただ、自分はPHPを勉強しているのと、C系言語が理解できないので、Chat GPTさんに、php に置換してもらった。それが以下のコード。あと、課金したGPTさんの返答なんで、アプデ前のだとどう返ってくるかは知らん。
あと、このコードに対して、分かりやすく解説して！って投げたら、解説してくれました笑 流石！
<?php
$seen = [];
function dfs($G, $v) {
global $seen;
$seen[$v] = true;
foreach ($G[$v] as $next_v) {
if ($seen[$next_v]) continue;
dfs($G, $next_v);
}
}
// Read number of vertices and edges
fscanf(STDIN, "%d %d", $N, $M);
$G = array_fill(0, $N, []);
for ($i = 0; $i < $M; $i++) {
fscanf(STDIN, "%d %d", $a, $b);
$a--; $b--; // Assuming that vertices are 1-indexed in the input
$G[$a][] = $b;
$G[$b][] = $a;
}
$seen = array_fill(0, $N, false);
dfs($G, 0);
「エッジ数」ってのが、分からなくて再度質問したら、
「頂点と頂点をつなぐ線」って回答してくれた。んで、理解できた！
もちろんです、以下に詳細な説明を行います：
1. `$seen = [];` ここで訪問済みの頂点を追跡するための配列 `$seen` を定義します。この配列の各要素は頂点の番号に対応し、その頂点が訪問済みの場合は `true` 、そうでない場合は `false` を格納します。
2. `function dfs($G, $v) {...}` ここで深さ優先探索 (DFS) を行うための関数を定義します。この関数はグラフ `$G` と開始頂点 `$v` を引数にとります。
3. `$seen[$v] = true;` 関数の始めに現在の頂点 `$v` を訪問済みにします。
4. `foreach ($G[$v] as $next_v) {...}` このループは現在の頂点 `$v` から辿れるすべての頂点 `$next_v` を繰り返し処理します。
5. `if ($seen[$next_v]) continue;` ここで `$next_v` がすでに訪問済みの場合は、その頂点をスキップします。
6. `dfs($G, $next_v);` `$next_v` がまだ訪問されていない場合は、その頂点から再帰的に DFS を開始します。
7. `fscanf(STDIN, "%d %d", $N, $M);` ここで標準入力から頂点数 `$N` とエッジ数 `$M` を読み取ります。
8. `$G = array_fill(0, $N, []);` これで頂点数 `$N` 分の空の配列を持つ配列 `$G` を初期化します。これはグラフのアジャセンシーリスト（各頂点から辿れる頂点のリスト）を表します。
9. `for ($i = 0; $i < $M; $i++) {...}` このループは `$M` 回実行され、各エッジの情報を読み取ります。
10. `fscanf(STDIN, "%d %d", $a, $b);` ここでエッジの両端を表す 2 つの頂点 `$a` と `$b` を読み取ります。
11. `$a--; $b--;` ここでは、頂点の番号が 1-indexed と想定して、頂点の番号を 1 減らしています。これは PHP が 0-indexed であるためです。
12. `$G[$a][] = $b; $G[$b][] = $a;` これでエッジをアジャセンシーリストに追加します。無向グラフを扱っているため、頂点 `$a` から
`$b` へのエッジと、頂点 `$b` から `$a` へのエッジの両方を追加します。
13. `$seen = array_fill(0, $N, false);` ここで全ての頂点を未訪問（`false`）に設定します。
14. `dfs($G, 0);` 最後に、頂点 0 から DFS を開始します。
このスクリプトは、DFS の基本的な実装を示しています。DFS は、各頂点を訪問し、訪問済みの頂点を再訪しないようにするための一般的な方法です。これにより、グラフ内の全ての頂点を効率的に探索することが可能となります。
ほな、あとは実践で試して行って自分の血肉にしていこうかと！！！
p.s.もはやググるんじゃなくて、チャットするが主流になるのかな〜なんて思ってきた。
