第三章 搜索与图论（一）

(据说y总讲蓝桥杯dfs很好)

0. dfs & bfs 概述

以搜索树方式进行思考

• dfs: 执着, 不撞南墙不回头。思路比较奇怪的用dfs。首先考虑挖深的顺序/递归拓延点。
• bfs: 稳重, 层层推进。最小、最短等用bfs。

1. dfs

path 路径变量

全排列问题

842. 排列数字

n = int(input())
unused = [True] * n
path = [0] * n

def dfs(u):
    if u == n: print(' '.join(path))
    for i in range(n):
        if unused[i]:
            path[u] = str(i + 1)
            unused[i] = False
            dfs(u + 1)
            unused[i] = True

dfs(0)

n皇后问题

843. n-皇后问题
技巧点：坐标(x, y), 对角线为 n + x - y, 反对角线为 x + y

方法1. 迭代每行，枚举该行点所在的列。检查列和正反对角线是否被占用，提前剪枝。

n = int(input())
dg, ndg, is_new_col, row = [True] * (n<<1) , [True] * (n<<1), [True] * n, [-1] * n

def dfs(x):
    if x == n:
        [print('.'*i + 'Q' + '.' * (n - i - 1)) for i in row] + [print('')]
        return 

    for y in range(n):
        if is_new_col[y] and dg[x + y] and ndg[n + x - y]:
            row[x] = y
            is_new_col[y] = dg[x + y] = ndg[n + x - y] = False
            dfs(x + 1)
            is_new_col[i] = dg[x + y] = ndg[n + x - y] = True

dfs(0)

方法2. 枚举每一个格子是否可以放皇后。

技巧点：对已经放置的皇后计数，超标后剪枝。
python 实现会TLE.

n = int(input())
g = [['.'] * n for _ in range(n)]
dg, ndg = [True] * (n<<1) , [True] * (n<<1)
is_new_row, is_new_col = [True] * n, [True] * n

def dfs(x, y, cnt):
    if y == n: y, x = 0, x + 1
    if x == n:
        if cnt == n:
            [print(''.join(gi)) for gi in g] + [print('')]
        return
    dfs(x, y + 1, cnt)

    if is_new_row[x] and is_new_col[y] and dg[x + y] and ndg[n + x - y]:
        g[x][y] = 'Q'
        is_new_row[x] = is_new_col[y] = dg[x + y] = ndg[n + x - y] = False
        dfs(x + 1, 0, cnt + 1) # speed up
        is_new_row[x] = is_new_col[y] = dg[x + y] = ndg[n + x - y] = True
        g[x][y] = '.'

dfs(0, 0, 0)

2. bfs

bfs 模板

queue <- 初始点
while queue not empty:
    取队头结点，进行相关处理
    将队头结点的扩展结点加入队列

夹带私货

• 当路径权值都为1时，bfs可以用于计算最短路
• DP 可以转化为特殊的最短路问题，无环图的最短路
• 输入超100万用scanf

走迷宫问题

844. 走迷宫

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
que = [(0, 0)]
st = set(que)

cnt = 0
while que:
    cnt += 1
    nq = []
    for (a, b) in que:
        for di, dj in zip(dx, dy):
            na, nb = a + di, b + dj
            if na < 0 or na >= n or nb < 0 or nb >= m or g[na][nb]:
                continue
            if na + 1 == n and nb + 1 == m:
                print(cnt)
                exit(0)
            if (na, nb) not in st:
                st.add((na, nb))
                nq.append((na, nb))
    que = nq

带路径记录

n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
d = [[0] * m for _ in range(n)]
prev = [[0] * m for _ in range(n)]

dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
que = [(0, 0)]
hh = tt = 0

st = set(que)

cnt = 0
while hh <= tt:
    a, b = que[hh]
    hh += 1
    for di, dj in zip(dx, dy):
        na, nb = a + di, b + dj
        if na < 0 or na >= n or nb < 0 or nb >= m or g[na][nb]:
            continue
        # if na + 1 == n and nb + 1 == m:
        #     print(cnt)
        #     exit(0)
        if (na, nb) not in st:
            st.add((na, nb))
            que.append((na, nb))
            d[na][nb] = d[a][b] + 1
            prev[na][nb] = (a, b)
            tt += 1

print(d[n - 1][m - 1])

# x, y = n - 1, m - 1
# while x or y:
#     print((x, y))
#     x, y = prev[x][y]

3. 树、图存储

树->图
无向图->有向图

有向图存储方法：

• 邻接矩阵: O(n^2), 位图表示每条边
• 邻接表: O(E), 每个结点对应一个链表，常用压缩静态链+头插法实现

图构建模板代码

int h[N], e[M], ne[M], idx;

void add(a, b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

846. 树的重心

n = int(input())
N = n * 2 + 10
h, e, ne, idx = [-1] * (n + 1), [0] * N, [0] * N, 0
unvisited = [True] * N

ans = float('inf')

def add(a, b):
    global idx
    ne[idx], e[idx] = h[a], b
    h[a] = idx
    idx += 1

def dfs(u):
    global ans
    max_v = 0
    unvisited[u] = False
    chd_sum = 0

    i = h[u]
    while i != -1:
        j = e[i]
        if unvisited[j]:
            chd_cnt = dfs(j)
            max_v = max(max_v, chd_cnt)
            chd_sum += chd_cnt
        i = ne[i]
    max_v = max(max_v, n - 1 - chd_sum)
    ans = min(ans, max_v)
    return chd_sum + 1

for i in range(n - 1):
    a, b = map(int, input().split())
    add(a, b)
    add(b, a)

dfs(1)

print(ans)

4. 拓扑序列

伪代码

que <- 所有入度为0的点

while que not empty:
    t <- 队头
    枚举t的所有出边 t->j, d[j] --
    if d[j] == 0:
        que.append(j)

848. 有向图的拓扑序列

n, m = map(int, input().split())

h, e, ne, idx = [-1] * (n + 1), [0] * (m + 1), [0] * (m + 1), 0

que = []
d = [0] * (n + 1)

def add(a, b):
    global idx
    ne[idx], e[idx] = h[a], b
    h[a] = idx
    idx += 1

def topsort():
    hh = tt = 0
    for i in range(1, n + 1):
        if d[i] == 0:
            que.append(i)
            tt += 1

    while hh < tt:
        t = que[hh]
        hh += 1
        i = h[t]
        while i != -1:
            j = e[i]
            d[j] -= 1
            if d[j] == 0:
                que.append(j)
                tt += 1
            i = ne[i]
    if tt == n: return ' '.join(str(i) for i in que)
    else: return -1


for _ in range(m):
    a, b = map(int, input().split())
    add(a, b)
    d[b] += 1

print(topsort())