グラフの s,t パス　💡DFS

Posted at 2026-02-27

今回は paiza の「グラフの s,t パス」の問題に挑戦！

🧩 問題概要

■ グラフの設定

頂点は 1〜n
無向グラフ
自己ループなし
多重辺なし
隣接リスト形式で与えられる

■ 与えられるもの

n：頂点数
s：始点
t：終点
各頂点 i について：
- 隣接頂点の数 v_i
- 隣接頂点の番号（昇順）

■ やること

頂点 s から頂点 t へ行く
「パス」を求める

■ パスの定義

頂点の重複は禁止
辺の重複も禁止
つまり、同じ頂点を2回通れない

■ 求めるもの

s から t へのパスのうち
頂点数が最も少ないもの（＝最短パス）を1つ
複数ある場合はどれでもOK
出力形式：
- s から t までの頂点を、順に半角スペース区切りの1行で出力

入力例:

出力例:

1 5 4

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [n, s, t] = lines[0].split(' ').map(Number);
    
    const graph = [];
    
    // 隣接リスト作成
    for (let i = 2; i <= n * 2; i++) {
        if (i % 2 === 0) {
            graph.push(lines[i].split(' ').map(Number));
        }
    }
    
    const visit = new Array(n + 1).fill(false);
    const arr = [];
    
    function dfs(v, path = []) {
        visit[v] = true;
        
        for (const next of graph[v - 1]) {
            if (!visit[next]) {
                path.push(next);
                
                if (next === t) {
                    arr.push([...path]); // ←コピー保存
                } else {
                    dfs(next, path);
                }
                
                path.pop();
            }
        }
        
        visit[v] = false; 
    }
    
    // スタートを含める
    dfs(s, [s]);
    
    let ans;
    let min = Infinity;
    
    for (const a of arr) {
        if (a.length < min) {
            min = a.length;
            ans = a.join(' ');
        }
    }
    
    console.log(ans);
});

🔍 コードの流れ

readlineで入力を受け取る
すべての行を lines 配列に保存する
1行目から
- 頂点数 n
- 始点 s
- 終点 t
  を取得する

隣接リスト作成

偶数行だけ取り出す
それを数値配列に変換
graph に格納
graph[i] が「頂点 i+1 の隣接頂点」になる

訪問管理の準備

visit 配列を作る（全頂点 false）
arr を用意（見つかった全パスを保存する配列）

DFS開始

dfs(s, [s]) を呼び出す
→ スタート地点から探索開始

dfs関数の流れ

今の頂点 v を訪問済みにする
v の隣接頂点を1つずつ調べる
- まだ訪問していない頂点だけ進む
- path に next を追加
- next が t なら
  → パスをコピーして保存
- next が t でなければ
  → さらに dfs を呼び出して奥へ進む
- 探索が終わったら
  → path の末尾を削除（元に戻す）
すべての探索が終わったら
→ v を未訪問に戻す

DFS終了後

arr に s → t の全パスが入っている
その中から、長さが最小のパスを探す
最短のものを出力する

📝まとめ

s から t までのパスは、

今いる頂点の隣接頂点の中から訪問済みではない隣接頂点を選んで、その頂点に移動して訪問済みにする

という操作を s から始めて、 t に到着するまで繰り返すことで求めることができる

これは再帰関数を用いて実装できる。

🔁 再帰DFSの流れまとめ

① やっていること

今いる頂点から
行ける頂点を1つ選び
ゴールなら記録
ゴールでなければさらに奥へ進む
終わったら元に戻す

② 処理の基本形

頂点 i を path に追加
i がゴールなら記録
ゴールでなければ dfs(i, path) を呼ぶ
処理が終わったら path の末尾を削除（←重要）

③ なぜ削除するのか？

次の分岐を調べるため
前の状態に戻すため

④ 戻るときに起きていること

再帰は：

一番奥まで進む
終わる
1段戻る
その段の「残りの処理（削除）」を実行
また戻る
また削除

という動きをする

⑤ A→B→C→D の例

進むとき：

[A]
[A,B]
[A,B,C]
[A,B,C,D]

戻るとき：

D削除 → [A,B,C]
C削除 → [A,B]
B削除 → [A]

各階層で1回ずつ削除される

⑥ ポイント

削除(pop)は「内側のif文が終わった後」に実行される
再帰は「途中の場所を覚えていて戻ってくる」
だから削除が連続して起こる

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

グラフの s,t パス 💡DFS