幅優先探索 (BFS) と辞書でつながりのグラフを写し取る

1 つの節から届くグラフを、節を 1 回ずつだけ写して、つながりごと写し取ります。元の節と写した節の対応を辞書に持ち、初めて見た節だけを写して列に並べる練習です。

海外で定番の問題リスト 4 本には入っていません

問題

社内の連絡網を、新しいシステムへ写します。古いシステムでは、人に 0 からの番号が付いていて、adj[i] が i 番の人と直接つながっている人の番号の並びです。つながりは両向きで、i 番の並びに j があれば、j 番の並びにも i があります。

新しいシステムへは、start 番の人から連絡網をたどって届く人だけを写します。写した人には、新しい番号を次の決まりで 0 から振ります。

start 番の人を新しい 0 番にします
そこから幅優先探索 (BFS) で人をたどります。ある人の隣を見る順は、adj の並びの順です。初めて見た人に、次の新しい番号を振ります

写したあとの連絡網を、同じ形 (新しい番号の i 番の隣を、新しい番号で、元と同じ順に並べた並びの並び) で返す関数を書いてください。

人の数は 1 以上 100 以下です。自分自身とのつながりや、同じ 2 人の 2 重のつながりはありません
start は 0 以上、人の数より小さい整数です

入力と出力の例

例 1

0、1、3、2 が輪につながっています。3 番から始めると、3 が新しい 0、隣の 1 と 2 が新しい 1 と 2、最後に見つかる 0 が新しい 3 です。

adj = [[1, 2], [0, 3], [0, 3], [1, 2]] start = 3

[[1, 2], [3, 0], [3, 0], [1, 2]]

例 2

人が 1 人で、つながりがありません。

adj = [[]] start = 0

[[]]

例 3

0 と 1、2 と 3 が別々のまとまりです。2 番から届くのは 2 と 3 だけなので、2 人だけを写します。

adj = [[1], [0], [3], [2]] start = 2

[[1], [0]]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「無向グラフの 1 つの節が渡されます。グラフ全体を深く写して (ディープコピーして) 返してください」
節はクラス (値と、隣の節の並び) で渡され、写した節を返す形が多いです。ここでは頁で値を受け渡すため、節を番号で表し、写した節に振る新しい番号でつながりを返す形にしています。どちらも「元の節から写した節への対応を辞書に持つ」所が同じです
書き終えると「輪があっても止まりますか？」「同じ節を 2 回写していませんか？」と聞かれます

つながりが両向きか、輪があるか、離れたまとまりも写すかを最初に確かめておくと、たどり方が決まります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「グラフ探索と幅優先探索」に、この型の要点を表とコードでまとめています。

グラフ探索は、つながりを近い順か奥からたどります。迷路、最短の手数、講座を受ける順のような問題が同じ形です。

まず考える手順

段 1

隣をたどっては写す、を素直に繰り返すと、輪がある所で同じ人に何度も戻り、止まらなくなります。例 1 では 3、1、0、2、3 と回り続けます。「この人はもう写したか」を覚えておく必要があります。

段 2

元の番号から新しい番号への辞書を持ちます。辞書に入っている人は写し済みです。人を見つけたとき、辞書に無ければ新しい番号を振って写し (新しい連絡網に空の並びを 1 つ足し)、列の後ろに並べます。辞書にあれば、その番号を使うだけです。この「無ければ写す、あればそれを使う」が、グラフを写すときの芯です。

段 3

列の前から人を取り出し、その人の元の隣を順に見ます。隣ごとに段 2 の手順で新しい番号を得て、取り出した人の新しい並びに足します。列が空になれば、start から届く人を全部写し終えています。列を使う幅優先なので、新しい番号は問題の決まりの通りに振られます。

段 4

start から届かない人は、列に一度も並ばないので写りません。例 3 のように、返す並びの長さは元より短くなることがあります。

解答

Python

from collections import deque


def clone_graph(adj, start):
    ids = {}
    out = []
    q = deque()

    def visit(u):
        # 初めて見た人だけを写す
        if u not in ids:
            ids[u] = len(out)
            out.append([])
            q.append(u)
        return ids[u]

    visit(start)
    while q:
        v = q.popleft()
        row = out[ids[v]]
        for u in adj[v]:
            row.append(visit(u))
    return out

JavaScript

function cloneGraph(
  adj, start,
) {
  const ids = new Map();
  const out = [];
  const q = [];
  // 初めて見た人だけを写す
  const visit = (u) => {
    if (!ids.has(u)) {
      ids.set(u, out.length);
      out.push([]);
      q.push(u);
    }
    return ids.get(u);
  };
  visit(start);
  for (const v of q) {
    const row = out[ids.get(v)];
    for (const u of adj[v]) {
      row.push(visit(u));
    }
  }
  return out;
}

Go

func cloneGraph(
	adj [][]int, start int,
) [][]int {
	ids := map[int]int{}
	out := [][]int{}
	q := []int{}
	// 初めて見た人だけを写す
	visit := func(u int) int {
		id, ok := ids[u]
		if !ok {
			id = len(out)
			ids[u] = id
			out = append(out, []int{})
			q = append(q, u)
		}
		return id
	}
	visit(start)
	for i := 0; i < len(q); i++ {
		v := q[i]
		me := ids[v]
		for _, u := range adj[v] {
			id := visit(u)
			out[me] = append(
				out[me], id)
		}
	}
	return out
}

JavaScript は for...of で、Go は番号 i で、列を前から読み進めています。配列の頭を shift で外すと、1 回で全体をずらすので遅くなるためです。JavaScript の for...of は、読み進めるあいだに後ろへ足した人も読みます。Go で隣を足すときに out[me] を毎回引き直しているのは、visit の中の append で out が作り直されることがあるためです。

計算量

時間は O(V + E) です。V は写す人の数、E はつながりの数です。どの人も列に 1 回並び、どのつながりも両側から 1 回ずつ見ます
使う記憶は O(V + E) です。写した連絡網そのものと、辞書と列です

よくある間違い

写したかどうかを覚えない。輪のあるグラフで止まらなくなるか、同じ人を何回も写します
列に並べるときではなく、取り出すときに辞書に入れる。列の中に同じ人が 2 回並び、新しい番号が 2 つ振られて、つながりの番号がずれます。番号は見つけたときに振ります
隣の順を並べ替える。新しい番号の振り方が決まりと変わり、答えが 1 つに決まらなくなります。adj の順のまま見ます
元の番号のまま返す。写したことにならず、例 1 の番号が全部ずれます。返す並びの中身は、全部新しい番号です

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def clone_graph(adj: list[list[int]], start: int) -> list[list[int]]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(clone_graph([[1, 2], [0, 3], [0, 3], [1, 2]], 3))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します