深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。 ---《维基百科》
树的DFS：
算法实现
/* * 树的深度优先搜索 * 省去了初始化树的部分 */ // 树的结点类型 struct Node { int self; // 结点值 Node *left; // 左结点 Node *right; // 右结点 }; int target = 5; // 要查找的值 const int TREE_SIZE = 9; // 树的结点个数 std::stack<Node *> unvisited; // 未访问过的树结点指针 Node nodes[TREE_SIZE]; // 树的结点数组 Node *current; // 当前指向的结点指针 void dfs(){ unvisited.push(&nodes[0]); // 根节点入栈 while (!unvisited.empty()) { current = unvisited.top(); unvisited.pop(); if(current->self==target){ // do something return ; } if (current->right != NULL) unvisited.push(current->right); // 右结点入栈 if (current->left != NULL) unvisited.push(current->left); // 左结点入栈 } }
图的DFS：
算法实现
/* * 图的深度优先搜索 * 省去了初始化图的部分 */ int target = 5; // 目标值 const int maxn = 100; // 图的最大结点数 bool vis[maxn][maxn]; // 访问标记 int G[maxn][maxn]; // 图的数据 int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; // 方向向量，(x,y)周围的四个方向 bool checkEdge(int x, int y) { if (!vis[x][y]) // 未被访问过 return true; else // 被访问过 return false; } void dfs(int x, int y) { vis[x][y] = 1; // 标记该节点被访问过 if (G[x][y] == target) { // 找到目标值 // do something return ; } for (int i = 0; i < 4; i++) { if (checkEdge(x + dir[i][0], y + dir[i][1])) // 按照规则生成下一个节点 dfs(x + dir[i][0], y + dir[i][1]); } return ; // 没有下层搜索节点，回溯 }
原文：https://www.cnblogs.com/nkqlhqc/p/10878643.html