## DFS算法 原

jit-hakase

#DFS算法 ##DFS ###排列数 问题: 生成1~n的排列 思路: 穷举所有可能 在生成结果数组前把重复的去掉 python code

``````A = [None for i in range(10)]
N = 3

def dfs(cur):
if cur == N:
print(A[:N])
else:
for i in range(1, N+1):
if i not in A[:cur]:
A[cur] = i
dfs(cur+1)

dfs(0)
``````

``````#include <iostream>
#include <algorithm>
using namespace std;

int A[10];
int N = 3;

int main()
{
for (int i = 0; i < N; i++)
A[i] = i+1;

do {
for (int i = 0; i < n; i++)
cout << A[i];
cout << endl;
} while(next_permutation(A, A+N));
return 0;
}
``````

###素数环 问题: 数字1~n围成一个n个节点的环, 不允许数字重复, 任意2个相邻数字相加, 结果均为素数, 打印所有素数环的组合. 思路: 同排列数, 多了素数判断. python code

``````A = [None for i in range(0, 10)]
N = 6

def is_prime(n):
for i in range(2, n//2+1):
if n%i == 0:
return False
return True

def dfs(cur):
if cur == N:
if is_prime(A[0]+A[N-1]):
print(A[:N])
else:
for i in range(1, N+1):
if i not in A[:cur]:
if cur == 0 or is_prime(i+A[cur-1]):
A[cur] = i
dfs(cur+1)

dfs(0)
``````

###八皇后 问题: 8×8的国际象棋棋盘上摆放八个皇后,使其不能互相攻击到,有多少种解. 思路: 结果数组存放每个棋子的x坐标, 直到没有冲突放完八个棋子. 解决冲突: 1. 不可能行冲突 2. 列冲突解决同排列数 解决斜线冲突, 利用y-x的特性找出关系. 3. cur-Q[cur] == j-Q[j]

4. cur+Q[cur] == j+Q[j] python code

``````Q = [None for i in range(0, 8)]
CNT = 0
N = 8

def dfs(cur):
if cur == N:
global CNT
CNT += 1
else:
for i in range(0, N):
Q[cur] = i
ok = True
for j in range(0, cur):
if Q[cur]==Q[j] or cur-Q[cur]==j-Q[j] or cur+Q[cur]==j+Q[j]:
ok = False
if ok:
dfs(cur+1)

dfs(0)
print('ans = ' + str(CNT))
``````

##回溯法 探索到某一步发现原先选择达不到目标, 就退回一步重新选择. 效率比普通DFS高. 可以优化排列数和素数环的程序

``````A = [None for i in range(0, 10)]
V = [False for i in range(0, 10)]
N = 4

def dfs(cur):
if cur == N:
print(A[:N])
else:
for i in range(1, N+1):
if not V[i]:
V[i] = True
A[cur] = i
dfs(cur+1)
V[i] = False

dfs(0)
``````

python code

``````A = [None for i in range(0, 10)]
V = [False for i in range(0, 10)]
N = 6
def is_prime(n):
for i in range(2, n//2+1):
if n%i == 0:
return False
return True

def dfs(cur):
if cur == N:
if is_prime(A[0]+A[N-1]):
print(A[:N])
else:
for i in range(1, N+1):
if not V[i]:
if cur == 0 or is_prime(i+A[cur-1]):
V[i] = True
A[cur] = i
dfs(cur+1)
V[i] = False

dfs(0)
``````

``````Q = [None for i in range(0, 8)]

VM = [False for i in range(0, 8)]
VL = [False for i in range(0, 16)]
VR = [False for i in range(0, 16)]

CNT = 0
N = 8

def dfs(cur):
if cur == N:
global CNT
CNT += 1
else:
for i in range(0, N):
if not VM[i] and not VL[cur+i] and not VR[cur-i+N]:
VM[i] = VL[cur+i] = VR[cur-i+N] = True
Q[cur] = i
dfs(cur+1)
VM[i] = VL[cur+i] = VR[cur-i+N] = False

dfs(0)
print('ans = ' + str(CNT))
``````

##二维DFS搜索 二维搜索使用BFS的效率更高且附带最短路径, 用DFS编写扫雷核心算法. 核心算法: 点击到一个空白区域, 可以向四面八方展开空白块和数字. DFS算法的代码更容易编写(BFS当然也可以完成) python code

``````'''
dfs(x-1, y)
dfs(x+1, y)

dfs(x, y-1)
dfs(x, y+1)

dfs(x-1, y+1)
dfs(x+1, y-1)

dfs(x-1, y-1)
dfs(x+1, y+1)
'''
# serach 8 directions

dx = [-1,  1,  0,  0, -1,  1, -1,  1]
dy = [ 0,  0, -1,  1,  1, -1, -1,  1]

def pour(x, y):
if M[x][y] == 0:
show_empty(x, y)
for i in range(0, 8):
pour(x+dx[i], y+dy[i])
elif M[x][y] > 0:
show_num(x, y)
``````

### jit-hakase

07/26
0
0
Kosaraju算法的分析和证明

Kosaraju算法是求解有向图强连通分量（strong connected component）的三个著名算法之一，能在线性时间求解出一个图的强分量。用Sedgewick爷爷的话说，就是“现代算法设计的胜利”。 什么是强...

liangtee
2013/03/30
362
0

sunhaiyu
2017/11/11
0
0

Kukucao
2018/08/21
0
0
DFS算法

DFS算法 三个经典例子 1 排列数 问题: 生成1~n的排列 思路: 一颗N层的树 每层节点为n^n个 在生成结果数组前把重复的去掉 DFS出口: 遍历到排列结果数组长度 DFS实现: 尝试安排数字给结果数组 ...

hakase
2016/10/27
127
0

222

MrPei
23分钟前
1
0
［译］Android Activity 和 Fragment 状态保存与恢复的最佳实践

https://blog.csdn.net/growing_tree/article/details/53759564 https://blog.csdn.net/u013588712/article/details/54691791...

shzwork
23分钟前
1
0

30分钟前
3
0
java Poi 操作执行excel 文件中函数问题

poi 读取excel 文件，当excel 有函数时，poi直接读取返回的是excel 函数，并不能返回函数计算结果: 解决步骤： sheet.setForceFormulaRecalculation(true); 判断该列格式是否为...

38分钟前
4
0
js模拟实现输入框input事件

39分钟前
3
0