深度优先搜索
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止
深度优先搜索基本模型
void dfs(int step)
{
判定边界
尝试每一种可能 for(int i = 0;i <n;i++)
{
继续下一步 dfs（stp+1）
}
返回
}
理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步如何做”则与“当下该如何做”是一样的。
栗子一
求解：□□□ + □□□ = □□□ 将数字1-9分别填入9个□中，没个数字只能使用一次是的等式成立。
<pre>
let count:Int = 9
var book:[Int] = Array.init(repeatElement(0, count: count + 1))
var num:[Int] = Array.init(repeatElement(0, count: count + 1))
func dfs(step:Int) {
//输出一种排列
if step == (count + 1) {
if ((num[1]*100 + num[2]*10 + num[3] + num[4]*100 + num[5]*10 + num[6]) == (num[7]*100 + num[8]*10 + num[9])) {
print(num)
return
}
}
for i in 1...count {
if book[i] == 0 { //book[i] = 0 表示i没有使用，1表示已经用过了
num[step] = i
book[i] = 1
dfs(step: step+1) //通过函数的递归来实现
book[i] = 0 //回收
}
}
}
dfs(step: 1)
</pre>
栗子二
在迷宫中求解起点到某一终点的最短步数
<pre>
var sumStep:Int = 99999
let maze = [[0,0,1,0],
[0,0,0,0],
[0,0,1,0],
[0,1,0,0],
[0,0,0,1]]
var book = Array.init(repeatElement([0,0,0,0,], count: 5))
let endPoint = (2,3)
func dfs(point: (x:Int,y:Int),step:Int) {
if point == endPoint {
if step < sumStep {
sumStep = step
}
return
}
let next = [(0,1), //向右走
(1,0), //向下走
(0,-1), //向左走
(-1,0)] //向上走
for index in next.indices {
let newPoint = (point.x + next[index].0,point.y + next[index].1) //新坐标点
if (newPoint.0 < 0) || (newPoint.0 > 3) || (newPoint.1 < 0) || (newPoint.1 > 4) {
continue
}
if (maze[newPoint.1][newPoint.0] == 0) && (book[newPoint.1][newPoint.0] == 0){
book[newPoint.1][newPoint.0] = 1
dfs(point: newPoint, step: step + 1)
book[newPoint.1][newPoint.0] = 0
}
}
}
dfs(point: (0,0), step: 0)
print(sumStep) //7
</pre>
广度优先搜索
广度优先搜索是一种层层递进的算法，又译作宽度优先搜索或横向优先搜索，简称BFS，是一种图形搜索，是从根节点开始，沿着树的宽度遍历树的节点如果所有节点均被访问，则算法中止。广度优先搜索实现一般采用open-closed表。
上面深度优先搜索的栗子二换成广度优先搜索代码如下：
<pre>
let maze = [[0,0,1,0],
[0,0,0,0],
[0,0,1,0],
[0,1,0,0],
[0,0,0,1]]
var book = Array.init(repeatElement([0,0,0,0,], count: 5))
//链表节点
struct note {
var x:Int = 0
var y:Int = 0
var f:Int = 0
var step:Int = 0
}
func bfs(maze:[Array<Int>], startPoint: (x:Int,y:Int),endPoint: (x:Int,y:Int)) -> Int {
var que:[note] = Array.init(repeatElement(note(), count: 1000))
var head = 0
var tail = 0
let next = [(0,1), //向右走
(1,0), //向下走
(0,-1), //向左走
(-1,0)] //向上走
//往队列插入迷宫入口坐标
que[tail].x = startPoint.x
que[tail].y = startPoint.y
que[tail].f = 0
que[tail].step = 0
tail+=1
var flag = 0 //用来标记是都到达endPoint
while head < tail {
for index in next.indices {
let nextPoint = (que[head].x + next[index].0,que[head].y + next[index].1) //新坐标点
if (nextPoint.0 < 0) || (nextPoint.0 > 3) || (nextPoint.1 < 0) || (nextPoint.1 > 4) {
continue
}
if (maze[nextPoint.1][nextPoint.0] == 0) && (book[nextPoint.1][nextPoint.0] == 0){
book[nextPoint.1][nextPoint.0] = 1
que[tail].x = nextPoint.0
que[tail].y = nextPoint.1
que[tail].f = head
que[tail].step = que[head].step + 1
tail+=1
}
if nextPoint == endPoint {
flag = 1
break;
}
}
if flag == 1 {
break
}
head+=1
}
return que[tail-1].step
}
let step = bfs(maze: maze, startPoint: (0,0), endPoint: (2,3))
print(step) //7
</pre>
网友评论