深度优先搜索

    xiaoxiao2021-03-25  48

    深度优先搜索算法(DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能的搜索树的分支。当节点v所在的边都已经被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择一个作为源节点并重复以上过程,整个进程反复进行直到所有节点被访问到位置。属于盲目搜索。

    DFS可以产生目标图的相应拓扑排序表,利用拓扑排序表可以解决一些图论问题,比如最大路径问题。

    算法实现:利用函数栈来保存当前搜索路径中每个节点的状态,没搜索一个新节点,就标记此节点被使用并递归调用一次dfs函数,确定此节点在本路径中无法到达终点,则return上一级函数,更换下一节点。

    DFS模板

    //DFS模板题 HDU 1181 #include <iostream> #include <string.h> #include <queue> #include <string> using namespace std; string str[300]; int vis[300],i;//标记数组,在一条路径中,被查找过的节点不能被再次查找,不然就会使路径出现循环 int flag = 0;//用于判定搜索是否查找到路径 void dfs(string use) { char last = use[use.length() - 1]; if (flag == 1)//如果已经找到了就直接结束,减少不必要的搜索过程 return; for (int k = 0;k<i;k++)//如果视当前use字符串为当前节点,那么for循环就应该遍历下一层的所有可能节点 { if (vis[k] == 0&& str[k][0] == last)//如果未被访问,且其首字符合本节点末字符匹配,就可以作为搜索树的分支节点 { vis[k] = 1;//每确定路径中的一个节点,就标记起来 if (str[k][str[k].length() - 1] == 'm')//满足搜索的结束条件就设置flag并退出 { flag = 1; return; } else dfs(str[k]);//否则继续向下搜索 //vis[k]=0 //大部分DFS在一条路径搜索失败后都需要回溯到上一状态 //通常需要把从本节点后产生的标记都重置 //实际上是否需要重置标记,应该看路径来源是否会对节点能否到达出口产生影响 //在本题中。如果str[k]是到所求路径中的一个节点,不管从什么途径搜索到了str[k],都不影响他到达终点。 } } } int main() { while (cin >> str[i]) { if (str[i] == "0") { memset(vis, 0, sizeof(vis)); flag = 0; for (int j = 0;j<i;j++) { if (str[j][0] == 'b')//如果满足起始条件就进入搜索过程 { vis[j] = 1; dfs(str[j]); } } i = 0;//有多组测试样例,每完成一组,重置i if (flag == 1) cout << "Yes." << endl; else cout << "No." << endl; } else i++; } return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-50125.html

    最新回复(0)