深度优先搜索(DFS, Depth-First Search)是搜索的手段之一。
1.算法思想
深度优先搜索思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
2.算法特点
深度优先搜索是一个递归的过程。首先,选定一个出发点后进行遍历,如果有邻接的未被访问过的节点则继续前进。若不能继续前进,则回退一步再前进,若回退一步仍然不能前进,则连续回退至可以前进的位置为止。重复此过程,直到所有与选定点相通的所有顶点都被遍历。
深度优先搜索是递归过程,带有回退操作,因此需要使用栈存储访问的路径信息。当访问到的当前顶点没有可以前进的邻接顶点时,需要进行出栈操作,将当前位置回退至出栈元素位置。
3.算法过程
3.1 无向图的深度优先搜索
以下图所示的无向图为例来说明无向图的深度优先搜索遍历过程:
- 首先选取顶点A为起始点,输出A顶点信息,且将A入栈,并标记A为已访问顶点。
- A的邻接顶点有C、D、F,从中任意选取一个顶点前进。这里我们选取C顶点为前进位置顶点。输出C顶点信息,将C入栈,并标记C为已访问顶点。当前位置指向顶点C。
- 顶点C的邻接顶点有A、D和B,此时A已经标记为已访问顶点,因此不能继续访问。从B或者D中选取一个顶点前进,这里我们选取B顶点为前进位置顶点。输出B顶点信息,将B入栈,标记B顶点为已访问顶点。当前位置指向顶点B。
- 顶点B的邻接顶点只有C、E,C已被标记,不能继续访问,因此选取E为前进位置顶点,输出E顶点信息,将E入栈,标记E顶点,当前位置指向E。
- 顶点E的邻接顶点均已被标记,此时无法继续前进,则需要进行回退。将当前位置回退至顶点B,回退的同时将E出栈。
- 顶点B的邻接顶点也均被标记,需要继续回退,当前位置回退至C,回退同时将B出栈。
- 顶点C可以前进的顶点位置为D,则输出D顶点信息,将D入栈,并标记D顶点。当前位置指向顶点D。
- 顶点D没有前进的顶点位置,因此需要回退操作。将当前位置回退至顶点C,回退同时将D出栈。
- 顶点C没有前进的顶点位置,继续回退,将当前位置回退至顶点A,回退同时将C出栈。
- 顶点A前进的顶点位置为F,输出F顶点信息,将F入栈,并标记F。将当前位置指向顶点F。
- 顶点F的前进顶点位置为G,输出G顶点信息,将G入栈,并标记G。将当前位置指向顶点G。
- 顶点G没有前进顶点位置,回退至F。当前位置指向F,回退同时将G出栈。
- 顶点F没有前进顶点位置,回退至A,当前位置指向A,回退同时将F出栈。
- 顶点A没有前进顶点位置,继续回退,栈为空,则以A为起始的遍历结束。若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程。直至所有顶点均被访问。
- 采用深度优先搜索遍历顺序为A->C->B->E->D->F->G。
3.2 有向图的深度优先搜索
以下图所示的有向图为例来说明有向图深度优先搜索遍历过程:
- 以顶点A为起始点,输出A,将A入栈,并标记A。当前位置指向A。
- 以A为尾的边只有1条,且边的头为顶点B,则前进位置为顶点B,输出B,将B入栈,标记B。当前位置指向B。
- 顶点B可以前进的位置有C与F,选取F为前进位置,输出F,将F入栈,并标记F。当前位置指向F。
- 顶点F的前进位置为G,输出G,将G入栈,并标记G。当前位置指向G。
- 顶点G没有可以前进的位置,则回退至F,将F出栈。当前位置指向F。
- 顶点F没有可以前进的位置,继续回退至B,将F出栈。当前位置指向B。
- 顶点B可以前进位置为C和E,选取E,输出E,将E入栈,并标记E。当前位置指向E。
- 顶点E的前进位置为D,输出D,将D入栈,并标记D。当前位置指向D。
- 顶点D的前进位置为C,输出C,将C入栈,并标记C。当前位置指向C。
- 顶点C没有前进位置,进行回退至D,回退同时将C出栈。
- 继续执行此过程,直至栈为空,以A为起始点的遍历过程结束。若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程。直至所有顶点均被访问。
4.经典例题
这里就先放上一道洛谷的 N 皇后题目吧。
再放一个我好久之前写的AC代码吧。(写的不好轻喷(o>ω<o) )
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
using namespace std;
vector<vector<int> > result;//用来记录结果
vector<int> pos;//存放当前结果
int cnt = 0;
bool check(int key, int value);
void DFS(int begin, int end);
int main()
{
int n;
while (cin >> n)
{
result.clear();
cnt = 0;
pos.resize(n+1);//分配 n 个空间来判断
DFS(1, n);//第一个空间是不用的
for (int i = 0; i < 3; i++)
{
for (int j = 1; j <= n; j++)
{
cout << result[i][j];
if (j != n)
cout << " ";
}
cout << endl;
}
cout << cnt << endl;
}
}
void DFS(int begin,int end)
{
if (begin > end)//所有位置都确定了
{
if (cnt < 3)
result.push_back(pos);
cnt++;
return;
}
for (int i = 1; i <= end; i++)
{//循环 end 次来确定所有皇后的位置
if (check(begin, i))
{//如果该皇后可以放在位置 i 上
pos[begin] = i;//第 begin 个皇后就在位置 i 上
DFS(begin + 1, end);//继续搜索
}
}
return;
}
bool check(int key,int value)
{//每一个皇后的八个方向都不能有皇后,所以需要这个check函数判断是否符合标准
for (int i = 1; i < key; i++)
{
if (pos[i] == value || abs(pos[i] - value) == abs(i - key))
return false;
}
return true;
}
再贴一份一位大佬写的位运算解法(等我哪天理解了再考虑写个详细点的解释吧QAQ):
#include<cstdio>
int upperlim,n,ans,tot,plan[15];
void dfs(int i,int c,int ld,int rd)//变量含义:第i行(只是用来记录方案,如果不输出方案,可以去掉),c是行影响,ld、rd分别是左右对角线
{
if(c==upperlim)//很好理解,如果是一个可行解的话自然所有列上都有棋子,如果不是可行解,看下面
{
if(++ans<=3)
{
for(int i=1;i<n;i++)
printf("%d ",plan[i]);
printf("%d\n",plan[n]);
}
return;
}
int mask=upperlim&~(ld|rd|c);//mask指的是留下来能用的位置,受到行、左右对角线的影响。用upperlim & 则是要舍掉高位上多出来的1
while(mask)//尽管是穷举位,但是不用判断,因为如果不可行的话mask上没有能放的位置,根本到达不了最终状态就退出,位运算解法天然剪枝的高效、简洁是别的解法永远也追不上的
{
int p=mask&(-mask);//技巧,表示mask末尾的第一个1,也就是穷举能放的位置
mask-=p;//
plan[i]=__builtin_ffs(p);//__builtin_ffs(p)指的是p的末尾第一个1的位置,竞赛能不能用我不知道,但是据说有人WinterCamp用了AC
dfs(i+1,c|p,(ld|p)<<1,(rd|p)>>1);//状态转移,c|p是行上影响,ld:对角线上首先增加了p的影响很好理解,左移则是对角线向下一行的自然延伸,rd同理
}
}
//尽管注释很详细,但是还是自己敲2,3遍才能理解
int main()
{
scanf("%d",&n);
upperlim=(1<<n)-1;//目标状态
ans=0;
dfs(1,0,0,0);
printf("%d\n",ans);
return 0;
}
//小吴师兄写的文章里还有个算法分析,等我把图完全弄懂后再补上吧。
参考文章:
《算法竞赛入门经典》
小小吴师兄的文章