Objective-C实现深度优先搜索

相信很多同学都听过深度优先搜索的大名，这是一种基于递归的搜索方法。记得自己第一次学习深度优先搜索的时候想了半天也没有搞明白实现原理，总是感觉理解的很不到位。最后为了应付考试不得不将伪代码死记硬背下来。在这里，我想通过这篇文章简单的介绍一下这种经常被用到的搜索方法。

1，有趣的卡片

相信很多同学在高中阶段都见过这样的数学题：手中有3张卡片和三个盒子，那么有多少种方法让每个盒子里有且只有一张卡片。对于这样的题目大家的第一反应这就是一个简单的全排列。那么，我们应该如何用代码去实现这个全排列呢？

(1), 确定当前盒子应放的卡片

要想将卡片放入当前的盒子里，首先要满足两个条件。第一，当前的盒子里没有卡片。第二，将要放入当前盒子的卡片是没有用过的。
因此我们可以建立当前盒子放入卡片的伪代码：

int book[10];//用来标记已经使用过的卡片
int boxes[10];//用来储存卡片的盒子
int step;//用来标记盒子的号码

//测试每一张卡片能否放入盒子中
- (void) dfs {
for (int i = 0; i < book.size();i ++) {
//测试当前卡片是否用过
    if(book[i]==0){
        //标记用过的卡片
        book[i] = 1;
        //将卡片放入盒子中
        boxes[step] = i;
     }
  }
}

(2),确定下一个盒子应该放入的卡片

这时候我们就要使用递归的思想了，因为每一个盒子放入的卡片判定条件都是相同的。因此我们可以用递归的方式去判定下一个盒子是否能放入卡片。伪代码如下：

int book[10];//用来标记已经使用过的卡片
int boxes[10];//用来储存卡片的盒子
int step;//用来标记盒子的号码

//测试每一张卡片能否放入盒子中
- (void) dfs: (int) step {
for (int i = 0; i < book.size();i ++) {
//测试当前卡片是否用过
    if(book[i]==0){
        //标记用过的卡片
        book[i] = 1;
        //将卡片放入盒子中
        boxes[step] = i;
        //使用递归将卡片放入下一个盒子
        dfs(step+1);
        //一定要将已经放入的卡片拿出来
        book[i] = 0;
     }
  }
}

2, Objective－C代码实现

- (instancetype) initWithNumbers:(NSInteger)numbers {
    self = [super init];
    
    if (self) {
        _numbers = numbers;
        _book = [NSMutableArray arrayWithCapacity:numbers];
        for (NSInteger i = 0; i < self.numbers; i++) {
            _book[i] = [NSNumber numberWithInteger:0];
        }
        
        _boxs = [NSMutableArray arrayWithCapacity:self.numbers];
    }
    
    return self;
}


- (void) depthFirstSearching:(NSInteger) steps {
    
    if (steps == self.numbers) {
        for (NSInteger i = 0; i < self.numbers; i++) {
            NSLog(@"%.0f",[self.boxs[i] floatValue]);
        }
        NSLog(@"//////////////////");
        
        return;
    }
    
    for (NSInteger i = 0; i < self.numbers; i ++) {
        if ([self.book[i] integerValue] == 0) {
            self.book[i] = [NSNumber numberWithInteger:1];
            self.boxs[steps] = [NSNumber numberWithInteger:i];
            [self depthFirstSearching:steps+1];
            self.book[i] = [NSNumber numberWithInteger:0];
        }
    }
    
}

特别感谢《啊哈！算法》