欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

DFS和BFS学习总结

程序员文章站 2022-06-12 09:21:29
...

DFS深度优先遍历

DFS和BFS学习总结

深度遍历就是在图中从一个顶点开始,按照一个规则不重复地走下去。就是不撞南墙不回头一样。假如从A顶点开始,按照一个规则去走(假如我们按照一直字典顺序走)那么就从A走到B再从B走到了C,走到C后再按照字典顺序的时候,发现A已经走过,那么此时就退回到C点,选择另一个D走下去。就和树的前序遍历是一样的。

实现方式

1、递归实现(通过邻接矩阵来实现)

void DFS(MGrap G. int i)
{
    int j = 0;
    visited[i] = 1;
    count++;
    for(j=0; j<G.numVertexes; j++)
    {
        if(G.arc[i][j]==1 && !visited[j])//i和j有关系相邻,并且j顶点没有被访问过
        {
            DFS(G, j);
        }
    }
}
void dfs(MGrap G,int v)  
{  
    init(&s);//使用自定义栈之前对栈进行初始化  
    push(&s,v);  //入栈第一个元素
    while(!isEmpty(&s))  
    {  
        pop(&s,&v);  //取出栈顶元素
        if(!visit[v])  //若没有访问过
        {  
            cout<<v<<' '; //输出该顶点
            visit[v]=true;  //标记已经访问过
            for(int k=0;k<M;k++)  //查找与该顶点相关联的顶点
            {  
                if(!visit[k]&&g[v][k]==1)  //若果未被访问过,且有相连的边
                {  
                    /*入栈操作*/
                    push(&s,k);  
                }  
            }  
        }  
    }  

}  

BFS广度 优先搜索遍历

类似于树的层次搜索,主要是从图中的某个顶点出发,在访问此顶点后,依次访问未被访问的邻接顶点。

DFS和BFS学习总结

以A为开始节点,依次遍历B,C,再从B相邻的结点DFE开始遍历,最后遍历的结果就是:ABCDFEGHI(遵循先进先出规则)

实现(采用邻接矩阵)

1、采用队列的方式

void BFS(MGrap G)
{
    int i,j;
    Queue Q;
    for(i=0; i<G.numVertexes; i++)/*初始化访问数组*/
    {
        visited[i] = -1;
    }
    InitQueue(&Q);
    for(i=0; i<G.numVertexes; i++)
    {
        if(!visited[i])
        {
            visited[i] = 1;
            printf("%c",G.vexs[i]);
            EnQueue(&Q,i);/*入队操作*/
            while(!QueueEmpty(Q))
            {
                DeQueue(&Q, &i);
                for(j=0; j<G.numVertexes; j++)
                {
                    /* 判断当前的节点与其他节点的关系 */
                    if(G.arc[i][j]==1 && !visited[j])
                    {
                        visited[j] = 1;
                        EnQueue(&Q,j);
                    }
                }
            }
        }
    }
}


总结:

两者的不同点是,BFS遍历的时候,按照深度去遍历,需要回退,所以需要用栈来记录原来顶点的位置;DFS是从相邻的结点开始依次遍历,所以先遍历到谁就先输出谁,所以采用队列的方式去实现。