有专门做检验的视频网站吗,移动网站转换,wordpress分类目录 菜单 页面,网站建设教程网页算法之深度优先算法
深度优先算法(DFS)
概念#xff1a; 深度优先算法(DFS)跟BFS算法一样是用于遍历图的算法#xff0c;但是DFS并不像BFS算法一样#xff0c;它搜索出来的路径不具有最短性#xff0c;并且dfs算法类似于枚举#xff0c;因此DFS算法一般用于求出问题的所…算法之深度优先算法
深度优先算法(DFS)
概念 深度优先算法(DFS)跟BFS算法一样是用于遍历图的算法但是DFS并不像BFS算法一样它搜索出来的路径不具有最短性并且dfs算法类似于枚举因此DFS算法一般用于求出问题的所有路径(例如全排列)。 深度优先算法就是从起点出发选择与其邻接的一条路径进行搜索将该路径搜索完(没有路了或者是个回路)再进行回退重新选择其他路径搜索。这样就需要使用递归实现而判断是否访问过顶点就需要一个bool类型的数组vis进行记录。 对于非强连通图那么可能在某个节点开始的深度优先搜索可能访问不了所有的节点在这种情况我们选取某个未被访问的节点开始再执行深度优先搜索。 dfs中最重要的算法思想是回溯和剪枝dfs回溯剪枝也可以用于求解最短路径但是BFS的时间复杂度更低。 回溯是一种选优搜索法又称为试探法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法而满足回溯条件的某个状态的点称为“回溯点”。剪枝就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看就好像剪掉了搜索树的枝条故称之为“剪枝”
具体操作
在访问图中某一起始点v后由v出发访问它的任一邻接点w1;再从w1出发访问与w1邻接但还未被访问过的顶点w2然后再从w2出发进行类似的访问…如此进行下去直至到达所有的邻接顶点都被访问过的顶点u为止。接着退回一步退到前一次刚访问过的顶点看是否还有其他没有被访问的邻接顶点。如果有则访问此顶点之后再从此顶点出发进行与前述类似的访问如果没有就再退回一步进行搜索。重复上述过程直到连通图中所有顶点都被访问过为止。
实现代码
邻接矩阵表示图的算法实现
bool vis[g.vexnum]; //记录顶点访问信息需要初始化为false//图g为邻接矩阵类型v为访问顶点
void dfs(Graph g,int v){coutv;vis[v]true;//依次检查邻接矩阵v所在行。for(int w0;wg.vexnum;w){//w是v的邻接点如果w未访问则递归调用dfsif(g.arcs[v][w]!0!vis[w]){dfs(g,w);}}
}邻接表表示图的算法实现
void DFS(int v){coutv;an[v].flag true;listnode* pan[v].next;while (p! nullptr){if(!an[p-data].flag){DFS(p-data);}pp-next;}}尾言
完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看或者在github库中自取(包含源代码) 博客1 codebooks.xyz博客2moonfordream.github.iogithub项目地址Data-Structure-and-Algorithms
