广搜与深搜

绝地灬酷狼 2024-01-08 13:19 19阅读 0赞

一、深搜

属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次；

深度优先遍历图的思想是，从图中某顶点v出发：  
（1）访问顶点v；  
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；  
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。  
例1对于以下一个树:  
1  
2 3  
4 5 6  
深度优先的策略是1->2->4->退后一步->5->退后一步->退后一步->3->6->结束  
而广度优先则是第一次:1->2->3第2次:4->5->6

![70][]

1.如果图是用邻接矩阵存储

typedef int boolean; /*boolean是布尔类型，其值是TRUE false*/
    boolean visited[MAX];
     
    /*邻接矩阵的深度优先递归算法*/
    void DFS(MGraph G,int i)
    {
        int j;
        visited[i]=TRUE;
        printf("%c ",G.vexs[i]);
        for(j=0;j<G.numVertexes;j++)
        {
            if(G.arc[i][j]==1&&!visited[j])
                DFS(G,j);
        }
    }
     
    /*邻接矩阵的深度遍历算法*/
    void DFSTraverse(MGraph G)
    {
        int i;
        for(i=0;i<G.numVertexes;i++)
            visited[i]=FALSE;//初始化 都未被标记
        for(i=0;i<G.numVertexes;i++)
        {
            if(!visited[j])//未被标记的调用DFS
                DFS(G,i);
        }
    }

如果图是用邻接表存储

/*邻接表的深度优先递归算法*/
    void DFS(GraphAdjList GL,int i)
    {
        EdgeNode *p;
        visited[i]=TRUE;
        printf("%c ",GL->adjList[i].data);
        p=GL->adjList[i].firstedge;
        while(p)
        {
            if(!visited[p->adjvex])
            {
                DFS(GL,p->adjvex);
            p=p->next;
            }
        }
    }
    /*邻接表的深度遍历算法*/
    void DFSTraverse(GraphAdjList GL)
    {
        int i;
        for(i=0;i<GL->numVertexes;i++)
            visited[i]=FALSE;//初始化 都未被标记
        for(i=0;i<GL->numVertexes;i++)
        {
            if(!visited[j])//未被标记的调用DFS
                DFS(G,i);
        }
    }

二、栈和递归思路

1. 使用栈来实现。相关算法实现总结为：

（1） 将初始节点压栈。

（2） While(栈非空) \{

（3） 取出栈顶点，暂时存储这个节点node\_t信息。

（4） 访问该节点，并且标示已访问。

（5） 将栈顶元素出站。

（6） For(遍历node\_t的相邻的未访问过的节点)\{

（7） 将其入栈。

2. 使用递归来实现。相关算法实现总结为：

（1） DFS（初始节点）

（2） Function DFS(一个节点) \{

（3） 访问该节点，并且标示已访问。

（4） For(遍历该节点的相邻的未访问过的节点) \{

（5） DFS（这个邻接节点）。

二、广搜

广搜，顾名思义，是多管齐下、广撒网的一种搜索方法  
　　如果广搜是一个人，那么她一定很贪心，而且喜新厌旧！她从一点出发去旅游，先把与起点相邻的地方全部游览一遍，然后再把与她刚游览过的景点相邻的景点全都游览一边……一直这样，直至所有的景点都游览一遍。  
　　广搜属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2…Vit，并均标记为已访问过，然后再按照Vi1、Vi2…Vit 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。

广搜优缺点

优点  
1、对于解决最短或最少问题特别有效，而且寻找深度小  
2、每个结点只访问一遍，结点总是以最短路径被访问，所以第二次路径确定不会比第一次短  
缺点  
1、内存耗费量大（需要开大量的数组单元用来存储状态）  
广搜模板

void BFS()  
\{ … …//初始化起点入队  
while(!q.empty()) //判断队是否为空  
\{ … …//获取队首元素  
if(... …)\{… …\}//判断是否是终点  
for(int i=0;i<4;i++)//四个方向  
\{  
k.x=p.x+dir\[i\]\[0\];  
k.y=p.y+dir\[i\]\[1\];  
//向各个方向走一步  
if(judge())//判断能不能走  
\{  
… …//各种处理  
vis\[k.x\]\[k.y\]=1; //标记  
q.push(k); //入队  
\}  
\}  
\}  
\}  
  
广搜打印路径：虽然它有多个后继结点，但前驱节点只有一个。所以可以逆向打印路径，即从终点出发找通向起点的路径

遍历四个方向 ↩︎

标记，标识已经走过的结点 ↩︎

取消标记 ↩︎

三、区别

一般来说，广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解"， 而深搜用于找多个解或者是"步数已知（好比3步就必需达到前提）"的标题，它的空间效率高，然则找到的不必定是最优解，必需记实并完成全数搜索，故一般情况下，深搜需要很是高效的剪枝（优化）.

像搜索最短路径这些的很显著若是用广搜，因为广搜的特征就是一层一层往下搜的，保证当前搜到的都是最优解，当然，最短路径只是一方面的操作，像什么起码状态转换也是可以操作的。  
深搜就是优先搜索一棵子树，然后是另一棵，它和广搜对比，有着内存需要相对较少的所长，八皇后标题就是典范楷模的操作，这类标题很显著是不能用广搜往解决的。或者像图论里面的找圈的算法，数的前序中序后序遍历等，都是深搜

深搜和广搜的分歧之处是在于搜索次序的分歧。

深搜的实现近似于栈，每次选择栈顶元素往外扩展，

广搜则是操作了队列，先被扩展的节点优先拿往外扩展。

搜索树的形态：深搜层数良多，广搜则是很宽。

深搜合适找出所有方案，广搜则用来找出最佳方案

深搜和广搜的分歧：

深搜并不能保证第一次碰着方针点就是最短路径，是以要搜索所有可能的路径，是以要回溯，标识表记标帜做了之后还要打消失踪，是以统一个点可能被访谒良多良多次。而广搜因为它的由近及远的结点扩年夜次序，结点老是以最短路径被访谒。一个结点假如第二次被访谒，第二次的路径确定不会比第一次的短，是以就没有需要再从这个结点向周围扩年夜――第一次访谒这个结点的时辰已经扩年夜过了，第二次再扩年夜只会获得更差的解。是以做过的标识表记标帜不必往失踪。是以统一个点至多只可能被访谒一次。每访谒一个结点，与它相连的边就被搜检一次。是以最坏情况下，所有边都被搜检一次，是以时刻复杂度为O（E）。

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/08/985df7c6c8f649d2945eca84a0a7e190.png