深度优先搜索DFS和广度优先搜索BFS的总结

朱雀 2022-06-09 08:00 295阅读 0赞

**图的遍历顺序有两种** ：深度优先搜索（ DFS ）和广度优先搜索（ BFS ）

**深度优先算法思想DFS**

深度优先搜索遍历类似于树的先序遍历。 假定给定图 G 的初态是所有顶点均未被访问过，在 G 中任选一个顶点 i 作为遍历的初始点，则深度优先搜索递归调用包含以下操作：

（ 1 ）访问搜索到的未被访问的邻接点；

（ 2 ）将此顶点的 visited 数组元素值置 1 ；

（ 3 ）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

**深度优先搜索** **DFS** **可描述为：**

（ 1 ）访问 v0 顶点；

（ 2 ）置  visited\[v0\]=1 ；

（ 3 ）搜索 v0 未被访问的邻接点 w ，若存在邻接点 w ，则 DFS(w) 。

**遍历过程：**

DFS 在访问图中某一起始顶点 v  后，由 v 出发，访问它的任一邻接顶点 w1 ；再从 w1 出发，访问与 w1 邻 接但还没有访问过的顶点 w2 ；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

例题1：

**方格填数**

如下的10个格子

\+--+--+--+

| | | |

\+--+--+--+--+

| | | | |

\+--+--+--+--+

| | | |

\+--+--+--+

（如果显示有问题，也可以参看【图1.jpg】）

![Center][]

填入0~9的数字。要求：连续的两个数字不能相邻。

（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。

#include <stdio.h>
    #include <cmath>
    using namespace std;
    int flag[3][4]; //表示哪些位置可以填数
    int mpt[3][4]; //填数
    bool visit[10];  //没赋值，默认是false
    int ans = 0;
    void init()   //初始化
    {
        int i,j;
        for(i = 0 ; i < 3 ; i ++)
            for(j = 0 ; j < 4 ; j ++)
                flag[i][j] = 1;
        flag[0][0] = 0;  //边缘化处理
        flag[2][3] = 0;
    }
    
    
    void Solve()  //判断填的数是否满足要求
    {
        int dir[8][2] = { 0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
        int book = true;
        for(int i = 0 ; i < 3 ; i ++)
        {
            for(int j = 0 ; j < 4; j ++)
            {
                //判断每个数周围是否满足
                if(flag[i][j] == 0) continue;
                for( int k = 0 ; k < 8 ; k ++)
                {
                    int x,y;
                    x = i + dir[k][0];
                    y = j + dir[k][1];
                    if(x < 0 || x >= 3 || y < 0 || y >= 4 || flag[x][y] == 0) continue; //如果超界或者这个位置是两个角则进行下一个位置的判断
                    if(abs(mpt[x][y] - mpt[i][j]) == 1)  book = false;  //如果相邻的是紧挨着的数 则不满足条件
                }
            }
        }
        if(book) ans ++;
    }
    
    
    void dfs(int index)
    {
        int x,y;
        x = index / 4;  //巧妙的写出了3*4表格的坐标
        y = index % 4;
        if( x == 3)   //已经填满数，判断填上的数是否满足要求
        {
            Solve();
            return;
        }
        if(flag[x][y])  //表示这个位置可以填数
        {
            for(int i = 0 ; i < 10 ; i ++)
            {
                if(!visit[i])   //如果这个数没有用过
                {
                    visit[i] = true;//表示这个数暂时用了
                    mpt[x][y] = i;
                    dfs(index+1);  //一直深下去，直到返回来
                    visit[i] = false;  //返回来之后把数又重新置假，表示没用过这个数  以此来完成填的数的不同
                }
            }
        }
        else
        {
            dfs(index+1);
        }
    }
    int main()
    {
        bool vi[10];
        for(int i=0; i<10; i++)
            printf("%d  ",vi[i]);
        init();
        dfs(0);
        printf("%d\n",ans);
        return 0;
    }

BFS遍历

![Center 1][]

![Image 1][]

![Image 1][]  
  
BFS思想  
1.从初始状态S开始，利用规则，生成下一层的状态。  
2.顺序检查下一层的所有状态，看是否出现目标状态G。否则就对该层所有状态节点，分别利用规则。生成再下一层的所有状 态节点。  
3.继续按上面思想生成再下一层的所有状态节点，这样一层一层往下展开。直到出现目标状态为止。按层次的顺序来遍历搜索树  
  
  
BFS框架

![Center 2][]

例题 ：迷宫问题(最短路径)-BFS  
![Center 3][]

代码：

#include <iostream>
    #include <queue>
    #include <cstring>
    #include <cstdio>
    #include <stack>
    using namespace std;
    int maze[6][6];
    int visit[6][6]; //判断是够拜访过这个点 
    int dis[6][6];   //标记步数 
    int dir[4][2]={
        {-1,0},{0,-1},{0,1},{1,0}};
    struct node
    {
    	int x;
    	int y;
    };
    queue <node> p;
    int nyj(int a,int b)
    {
    	if(a>=0 && a<5 && b>=0  && b<5) return 1;
    	else return 0;
    }
    void print(int i,int j)
    {
    	if(i==0 && j==0) 
    	{
    		printf("(%d, %d)\n",i,j);
    		return ;
    	}
    	for(int x=0;x<4;x++)
    	{
    		int xx=i+dir[x][0];
    		int yy=j+dir[x][1];
    		if(nyj(xx,yy) && !maze[xx][yy] && dis[xx][yy]==dis[i][j]-1)  
    		print(xx,yy);
    	}
    	printf("(%d, %d)\n",i,j);
    }
    void BFS(int i,int j)
    {
    	node n;
    	n.x=i; n.y=j;
    	p.push(n);
    	dis[i][j]=1;
    	visit[i][j]=1;
    	while(!p.empty())
    	{
    		n=p.front();
    		p.pop();
    		for(int x=0;x<4;x++)
    		{
    			int xx=n.x+dir[x][0];
    			int yy=n.y+dir[x][1];
    			if(nyj(xx,yy) && maze[xx][yy]==0 &&  !visit[xx][yy]) {
    				visit[xx][yy] =1;
    				dis[xx][yy]=dis[n.x][n.y]+1;
    				node a;
    				a.x=xx; a.y=yy;
    				p.push(a);
    				
    			}
    		}
    	}
    	print(4,4);
    }
    int main()
    {
    	for(int i=0;i<5;i++)
    	for(int j=0;j<5;j++)
    	cin>>maze[i][j];
    	memset(visit,0,sizeof(visit));
    	memset(dis,0,sizeof(dis));
    	BFS(0,0);
    	return 0;
    }

[Center]: /images/20220609/2a8a3b4417d7411288ff8e0de0ab73c8.png
[Center 1]: /images/20220609/799170ab31684a66a794385cd859046d.png
[Image 1]: 
[Center 2]: /images/20220609/98bc546bdac8484aa70564a9526d113f.png
[Center 3]: /images/20220609/6935231631f340b2b20268225ab40865.png