dfs(depth-first search)

/

dfs(depth-first search)について

タグ

  • 深さ優先探索
  • カスタマイズすることでノードがつながった数のカウント等にも使える
  • 四畳半で使われる畳(一畳と半畳の畳)で床を敷き詰めるパターンの全探索等
  • ネットワーク中の閉路の数を求める

具体的なサンプルコード

  • i -> 初期ノード
  • arg -> 何らかの挙動のオプションや累積値
  • vis -> すでに訪れたところをスキップするオプション

テンプレート1(再帰あり)

import sys; sys.setrecursionlimit(10**9)

vis = set()
def dfs(i, arg):
    if i in vis:
        return
    vis.add(i)
    for j in G[i]:
        dfs(j, arg)

テンプレート2(再帰なし, 再帰なしのほうが早い)

def dfs(i, arg):
    que = collections.deque([(i, arg)])
    while que:
        i, arg = que.pop()
        if i in vis:
            continue
        vis.add(i)
        for j in G[i]:
            que.append( (j, arg) )

例; 具体的な例題とその回答

例; AtCoder Typical Contest 001; A - 深さ優先探索

問題

解説

  • 典型的なdfsによるソリューション

解答

例; dfsを適応するとテンプレート的に解ける問題

問題

解答

例; 畳の埋めるパターンをdfsを用いて全探索する

問題

解答

例; queでは解くことができなく再帰でのみ解くことが可能な例

問題

解説

  • 状態を記述するデータを次の処理に渡す必要があるが、処理が終わったら戻す必要がある(バックトラック法の一種)
  • このデータが大きいとき、queでは参照後リセットを行うというプロセスが記述できないので、必ず再帰として書く必要がある
  • 木dpの一種のようにも思える

解答

例; 閉路の検出

問題

解説

  • 閉路を含む = 一つのノードに複数個の参照がある, と読み替えることができる
  • たどったかどうかを保存するテーブルを工夫し、一つのノードにどれくらい参照があったかをカウントすることで実現できる

解答

例; 探索のパターンの全列挙

解説

  • グローバルなvisitedのような変数でたどってきた経路を管理するのではなく、queにたどってきた経路を入れ込むことで、ユニークな経路を列挙することができる

解答

import collections
import itertools
import copy
N,M=map(int,input().split())

G=collections.defaultdict(list)
for _ in range(M):
    a,b = map(int,input().split())
    a-=1;b-=1
    G[a].append(b)
    G[b].append(a)

que = collections.deque([[0, []]])

ans = 0
while que:
    i, memo = que.pop()
    if i in memo:
        continue
    memo.append(i)
    if len(memo) == N:
        ans += 1
        continue
    for j in G[i]:
        que.append( (j, copy.copy(memo)) )
print(ans)

例; 距離が偶数か奇数かで塗り分ける

問題

解説

  • ２点(a,b)の頂点の距離はある任意の点xからの距離dがある時, da + db - 2dxになる
  • この距離の声質を利用して任意の点からのdfsでの距離を記録しておき、偶数か、奇数かで塗り分ける

解答

import sys; sys.setrecursionlimit(10**9)

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    u,v,w=map(int,input().split())
    u-=1; v-=1
    G[u].append( (v,w) )
    G[v].append( (u,w) )

vis = set()
mem = dict()
def dfs(i, acc):
    if i in vis:
        return
    vis.add(i)
    mem[i] = acc
    for j, w in G[i]:
        dfs(j, acc+w)
dfs(0, 0)

for i in range(N):
    if mem[i]%2 == 0:
        print(0)
    else:
        print(1)

例; 接続したノードの数のカウントアルゴリズム

擬似コード

擬似結果