深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 这个算法会尽可能深的搜索树的分支。 当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。 这一过程一直进行到已发现从源节点可达的所有节点为止。

1
2
3
4
5
6
7
8
9

深度优先搜索的步骤:

  1. 将迷宫中的的路口和路的数据保存在g中
  2. 准备一个本子,记录去过的顶点
  3. 每到一个路口,立即将它记录下来
  4. 然后检查这个路口能直接到达的其他路口,选择一个没有记过的进去探索
  5. 重复3、4步骤,直到找到终点

C++代码

#include <iostream>
#include <vector>
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 5
1 2
2 4
4 3
1 5
5 6
*/

/* 测试输出数据
1 2 4 3 5 6 
*/

看漫画也能学C++?没错!编程玩家俱乐部新推出系列课程《看漫画学C++》,带你用轻松看漫画的方式来学习C++,本课程面向零基础学员,只要坚持学习并多思考和多练习,相信你一定会成为C++的编程高手!如果喜欢本课程,就收藏一下哦,转发给你的小伙伴们,大家一起来学习!

img