深度优先算法-DFS(算法篇)

算法之深度优先算法

深度优先算法(DFS)

概念：

• 深度优先算法(DFS)跟BFS算法一样是用于遍历图的算法，但是DFS并不像BFS算法一样，它搜索出来的路径不具有最短性，并且dfs算法类似于枚举，因此DFS算法一般用于求出问题的所有路径(例如全排列)。

• 深度优先算法就是从起点出发，选择与其邻接的一条路径进行搜索，将该路径搜索完(没有路了或者是个回路)，再进行回退，重新选择其他路径搜索。这样就需要使用递归实现，而判断是否访问过顶点就需要一个bool类型的数组vis进行记录。

• 对于非强连通图，那么可能在某个节点开始的深度优先搜索可能访问不了所有的节点，在这种情况，我们选取某个未被访问的节点开始，再执行深度优先搜索。

• dfs中最重要的算法思想是回溯和剪枝，dfs+回溯+剪枝也可以用于求解最短路径，但是BFS的时间复杂度更低。

  1. 回溯是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
  2. 剪枝，就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。形象地看，就好像剪掉了搜索树的枝条，故称之为“剪枝”

具体操作：

• 在访问图中某一起始点v后，由v出发，访问它的任一邻接点w1;
• 再从w1出发，访问与w1邻接但还未被访问过的顶点w2；
• 然后再从w2出发，进行类似的访问…
• 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。
• 接着，退回一步，退到前一次刚访问过的顶点，看是否还有其他没有被访问的邻接顶点。
• 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
• 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

实现代码：

邻接矩阵表示图的算法实现

bool vis[g.vexnum];   //记录顶点访问信息，需要初始化为false

//图g为邻接矩阵类型，v为访问顶点
void dfs(Graph g,int v){
    cout<<v;
    vis[v]=true;
    //依次检查邻接矩阵v所在行。
    for(int w=0;w<g.vexnum;w++){
        //w是v的邻接点，如果w未访问，则递归调用dfs
        if(g.arcs[v][w]!=0&&!vis[w]){
            dfs(g,w);
        }
    }
}

邻接表表示图的算法实现

void DFS(int v){
        cout<<v;
        an[v].flag= true;
        listnode* p=an[v].next;
        while (p!= nullptr){
            if(!an[p->data].flag){
                DFS(p->data);
            }
            p=p->next;
        }
    }

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms