深度优先搜索及讲解【新手易懂】

一、深度优先搜索概念

DFS（Depth-First Search）：深度优先搜索属于图算法的一种，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

深度优先遍历图的方法是，从图中某顶点v出发：

1. 访问顶点v；
2. 依次从v的未被访问的邻接点出发，对图进行DFS；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行DFS，直到图中所有顶点均被访问过为止。

深度优先遍历使用的数据结构是栈（Stack），将访问过的节点标记后，并压入栈中，再遍历此时跟栈顶元素相关联的节点，将其中未标记的节点标记，并压入栈中……以此类推，当该栈顶的元素相关联的节点都被访问过了，则该元素弹出栈……直到栈空，遍历完成。

二、深度优先搜索算法举例

​
给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边：graph[i]中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

​

该题即利用栈，从某一个节点按顺序出发，如果未标记，则压栈并标记，栈非空时，则出栈并将关联的节点继续压栈，直到栈空为止，再下一个节点……

#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
int m,n,a[10010]={0},b[10010]={0};
void d(int k)
{
	for(int i=a[k-1];i<=m;i++)
	{
		if(b[i]==0)
		{
			b[i]=1;    //赋值
			a[k]=i;
			if(k==n)
			{
				for(int j=1;j<=k;j++)
				{
					cout<<setw(3)<<a[j];
				}
				cout<<endl;
			}
			else	d(k+1);    //返回
			b[i]=0;    //每当执行完都要为下一条做准备初始化
			a[k]=0;    
		}
	}
}
int main()
{
	cin>>m>>n;
	a[0]=1;
	d(1);
	return 0;
}

​

上面这题通过自己手动创建栈来维护了深度遍历的结构，下面再看一题利用递归的方式来做的：

【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n(1≤n≤100)，表示迷宫的规模是n×n的。接下来是一个n×n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha,la,hb,lb全部是从0开始计数的。

【输出】
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
【输出样例】
YES
NO

代码：

​
#include<iostream>
#include<cstdio>
using namespace std;
int t,n,m1,n1,m2,n2,bz=0;
char a[1010][1010];
int dx[5]={0,0,0,1,-1};       //横坐标，只有四个方向，加上中心点
int dy[5]={0,-1,1,0,0};        //纵坐标，只有四个方向，加上中心点
void d(int x,int y)
{
	if(bz==1)	return;    //省空间，只要能走到终点就直接停止函数
	for(int i=1;i<=4;i++)
	{
		if(x+dx[i]>=0&&x+dx[i]<n&&y+dy[i]>=0&&y+dy[i]<n&&a[x+dx[i]][y+dy[i]]=='.')//导航
		{
			a[x+dx[i]][y+dy[i]]='#';    //把之前走过的路口封住
			if(x+dx[i]==m2&&y+dy[i]==n2)    //到达终点
			{
				bz=1;
			}    
			else	d(x+dx[i],y+dy[i]);    //返回
			//a[x+dx[i]][y+dy[i]]='.';
		}
	}
}
int main()
{
	cin>>t;
	for(int p=1;p<=t;p++)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>a[i][j];
			}
		}
		cin>>m1>>n1>>m2>>n2;
		if(a[m1][n1]=='#'||a[m2][n2]=='#')    //如果起点是障碍物，那就走不了，只能输出NO，然后继续
		{
			cout<<"NO";
			cout<<endl;
			continue;    //continue就是继续执行
		}
		a[m1][n1]='#';    //起点可以走了，先初始化
		bz=0; 
		d(m1,n1);
		if(bz==0)
		{
			cout<<"NO"<<endl;
		}
		else
		{
			cout<<"YES"<<endl;
		}
	}
	return 0;
}

​

三、深度优先搜索算法公式

使用栈的公式：【转载】

public boolean dfsStack(int[][] graph) {
    createFlagArray();                         // 创建标记数组
    for (……){                                  // 按序遍历所有点
        if (!flag) {                           // 是否未标记
            createAndPushStack();              // 创栈并入栈，放入第一个启动值
            flag();                            // 同时做好标记
            while (!stack.isEmpty()) {         // 栈不空时一直循环
                nodes = findRelationNode();    // 栈顶弹出，并找栈顶元素的关联节点值
                for (node : nodes) {           // 遍历关联节点
                    if (!flag) {               // 关联节点未标记
                        pushStack();           // 关联节点入栈
                        flag();                // 同时做好标记
                    } else if (flag) {         // 关联节点已标记
                        return false;          // 判断终止条件做处理
                    }

                }
            }
        }
    }
    return true;
}

使用递归的公式：

public int dfsRecursion(char[][] grid) {
    for (……){                           // 按序遍历所有点       
        if (……){                        // 额外的一些统计
            count++;
        }
        helper(i, j, grid);             // 开始递归遍历，指定起点
    }
    return count;                       // 返回结果
}

private void helper(int row, int col, char[][] grid) {
    checkValid();                       // 检查是否无效，或已标记（即终止条件）
    flag();                             // 正常标记
    helper(row + 1, col, grid);         // 递归遍历所有
    helper(row, col + 1, grid);
    helper(row - 1, col, grid);
    helper(row, col - 1, grid);
}