广搜与深搜-蒲公英云

一、深搜

属于图算法的一种，英文缩写为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

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）将初始节点压栈。

（2） While(栈非空) {

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

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

（5）将栈顶元素出站。

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

（7）将其入栈。

}

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

（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）。