漫画学算法：深度优先搜索算法
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的**搜索**树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
深度优先搜索的步骤：
1. 将迷宫中的的路口和路的数据保存在g中
2. 准备一个本子，记录去过的顶点
3. 每到一个路口，立即将它记录下来
4. 然后检查这个路口能直接到达的其他路口，选择一个没有记过的进去探索
5. 重复3、4步骤，直到找到终点
C++代码如下，我们仍然使用邻接表来保存图的数据：
using namespace std;void dfs(int s, vector<int> g[], bool visited[], int n) {// 到达s点，将它记下visited[s] = true;cout << s + 1 << ' ';// 检查s点能到达的其他点，找第一个没去过的进去探索for (int i=0; i<g[s].size(); i++) {if (!visited[g[s][i]]) {dfs(g[s][i], g, visited, n);}}}int main() {// n个顶点（或称结点）int n; cin >> n;// m条边int m; cin >> m;// 创建一个vector<int>数组，即每个成员是一个vector，一共有n个成员// g[i]表示顶点i能够直接到达的其他顶点的列表// 如果是有权图，则可以使用一个结构体的vector，结构体里设置顶点编号和权值vector<int> g[n];// 读入m条边数据，每个数据由2个顶点编号u，v组成，表示u到v的一条边（因为是无向图，同时也是v到u的一条边）for (int i=0; i<m; i++) {int u, v;cin >> u >> v;g[u-1].push_back(v-1);g[v-1].push_back(u-1);}// 创建一个数组记录路口是否来过bool visited[n];for (int i=0; i<n; i++) {visited[i] = false;}// 从第1个路口（下标为0）开始探索dfs(0, g, visited, n);return 0;}/* 测试输入数据7 51 22 44 31 55 6*//* 测试输出数据1 2 4 3 5 6*/
看漫画也能学C++？没错！编程玩家俱乐部新推出系列课程《看漫画学C++》，带你用轻松看漫画的方式来学习C++，本课程面向零基础学员，只要坚持学习并多思考和多练习，相信你一定会成为C++的编程高手！如果喜欢本课程，就收藏一下哦，转发给你的小伙伴们，大家一起来学习！