～ 根付き木 ～ チートシート

目次

実装
深さ優先探索
幅優先探索

はじめに

チートシートの扱いついてはここを読んでください

実装

classを使うのに不安を覚える雑魚 用のコード

tree.py

N = int(input())

child = [[] for i in range(N+1)] # 子ノードを格納する配列
parent = [0]*(N+1) # 親ノードを格納する配列
depth = [0]*(N+1) # ノードの深さを格納する配列

for i in range(N-1):
  A,B = map(int,input().split())
  child[A].append(B)
  child[B].append(A)

check = [1] # 根の番号
while True:
  if check == []:
    break
  now = check.pop(-1)
  for i in reversed(range(len(child[now]))):
    if depth[child[now][i]] == 0 and child[now][i] != 1:
      parent[child[now][i]] = now
      depth[child[now][i]] = depth[now] + 1
      check.append(child[now][i])
    else:
      child[now].pop(i)

詳しい人のコードをちゃんと調べたりとかはしてないので今後大きく書き替える可能性が高いですが、無いよりはマシなのでとりあえずページを作ってこのコード例を貼っています（他の人にはあまり見せられないコード）

深さ優先探索

tree.py

N = int(input())

child = [[] for i in range(N+1)] # 子ノードを格納する配列
parent = [0]*(N+1) # 親ノードを格納する配列
depth = [0]*(N+1) # ノードの深さを格納する配列

for i in range(N-1):
  A,B = map(int,input().split())
  child[A].append(B)
  child[B].append(A)

check = [1] # 根の番号
while True:
  if check == []:
    break
  now = check.pop(-1)
  for i in reversed(range(len(child[now]))):
    if depth[child[now][i]] == 0 and child[now][i] != 1:
      parent[child[now][i]] = now
      depth[child[now][i]] = depth[now] + 1
      check.append(child[now][i])
    else:
      child[now].pop(i)

passed = [0]*(N+1) # これまでに通過したノードの情報を格納する配列
next_child = [0]*(N+1) # 次に確認する子ノードの情報を格納する配列
now = 1
while True:
  #print(now)
  passed[now] = 1
  if now == 0:
    break
  if next_child[now] == len(child[now]):
    now = parent[now]
  else:
    next_child[now] += 1
    now = child[now][next_child[now]-1]

行き詰まったら親ノードに戻る必要がある場合の実装例

幅優先探索

tree.py

N = int(input())

child = [[] for i in range(N+1)] # 子ノードを格納する配列
parent = [0]*(N+1) # 親ノードを格納する配列
depth = [0]*(N+1) # ノードの深さを格納する配列

for i in range(N-1):
  A,B = map(int,input().split())
  child[A].append(B)
  child[B].append(A)

check = [1] # 根の番号
while True:
  if check == []:
    break
  now = check.pop(-1)
  for i in reversed(range(len(child[now]))):
    if depth[child[now][i]] == 0 and child[now][i] != 1:
      parent[child[now][i]] = now
      depth[child[now][i]] = depth[now] + 1
      check.append(child[now][i])
    else:
      child[now].pop(i)