精华内容
参与话题
问答
  • BFS和DFS

    千次阅读 2020-03-05 12:43:01
    文章目录DFS填涂颜色马的遍历奇怪的电梯01迷宫DFS八皇后问题迷宫单词方阵 ...例如:6 \times 66×6的方阵(n=6n=6),涂色前涂色后的方阵如下: 输入格式 每组测试数据第一行一个整数n(1≤n≤30) 接下来n行,由0...

    DFS

    填涂颜色

    题目描述
    由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=6),涂色前和涂色后的方阵如下:
    在这里插入图片描述
    输入格式
    每组测试数据第一行一个整数n(1≤n≤30)
    接下来n行,由0和1组成的n×n的方阵。
    方阵内只有一个闭合圈,圈内至少有一个0。

    输出格式
    已经填好数字22的完整方阵。

    输入

    6
    0 0 0 0 0 0
    0 0 1 1 1 1
    0 1 1 0 0 1
    1 1 0 0 0 1
    1 0 0 0 0 1
    1 1 1 1 1 1

    输出

    0 0 0 0 0 0
    0 0 1 1 1 1
    0 1 1 2 2 1
    1 1 2 2 2 1
    1 2 2 2 2 1
    1 1 1 1 1 1

    #include<iostream>
    #include<queue>
    
    using namespace std;
    const int MAXN=100;
    int Map[MAXN][MAXN];
    int vis[MAXN][MAXN];//访问标记,为0表示没被访问
    //能走的四个方向
    int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    struct position{
        int x,y;
        position(int x,int y):x(x),y(y){};
    };
    queue<position> q;
    int main(){
        int n;
        cin>>n;
        //最开始应该在外面再加一圈零(从1开始输入),因为(0,0)这个点若是1就完蛋
        //所以要注意遍历初始点的选取
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>Map[i][j];
            }
        }
        q.push(position(0,0));//初始点进队列
        vis[0][0]=1;
        while(!q.empty()){
            position current=q.front();
            for(int i=0;i<4;i++){
                //沿着每个方向变化后的横纵坐标
                int x=current.x+way[i][0];
                int y=current.y+way[i][1];
                //cout<<x<<" "<<y<<endl;
                //加了Map[x][y]==0的条件,将1围成的圈外部的0全部置已访问
                if(x>=0&&x<=n+1&&y>=0&&y<=n+1&&Map[x][y]==0&&vis[x][y]==0){
                    q.push(position(x,y));
                    vis[x][y]=1;
                }
            }
            q.pop();
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(Map[i][j]==0&&vis[i][j]==0){
                    cout<<2<<" ";
                }
                else  cout<<Map[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    

    马的遍历

    题目描述
    有一个n*m的棋盘(1<n,m<=400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

    输入格式
    一行四个数据,棋盘的大小和马的坐标

    输出格式
    一个n*m的矩阵,代表马到达某个点最少要走几步(左对齐,宽5格,不能到达则输出-1)

    输入

    3 3 1 1

    输出

    0 3 2
    3 -1 1
    2 1 4

    #include<iostream>
    #include<queue>
    #include<cstdio>
    using namespace std;
    const int MAXN=500;
    int Map[MAXN][MAXN];
    int vis[MAXN][MAXN];
    struct position{
        int x,y;
        int steps;
        position(int x,int y,int steps):x(x),y(y),steps(steps){};
    };
    //马跳的8个方向
    int way[8][2]={{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
    
    queue<position> q;
    int main(){
        int n,m,x1,y1;
        cin>>n>>m>>x1>>y1;
        q.push(position(x1-1,y1-1,0));//初始点
        vis[x1-1][y1-1]=1;//这一步别忘了
        while(!q.empty()){
            position current=q.front();
            for(int i=0;i<8;i++){
                int x=current.x+way[i][0];
                int y=current.y+way[i][1];
                if(x>=0&&x<=n-1&&y>=0&&y<=n-1&&vis[x][y]==0){
                    q.push(position(x,y,current.steps+1));
                    Map[x][y]=current.steps+1;
                    vis[x][y]=1;
                }
            }
            q.pop();
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(vis[i][j]!=0) printf("%-5d",Map[i][j]);
                else printf("%-5d",-1);
            }
            cout<<endl;
        }
    }
    
    

    奇怪的电梯

    题目描述
    呵呵,有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第ii层楼(1≤i≤N)上有一个数字Ki(0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如:3, 3 ,1 ,2 ,5代表了Ki(K1=3,K2=3,…),从1楼开始。在1楼,按“上”可以到4楼,按“下”是不起作用的,因为没有−2楼。那么,从A楼到B楼至少要按几次按钮呢?

    输入格式
    共二行。
    第一行为3个用空格隔开的正整数,表示N,A,B(1≤N≤200, 1≤A,B≤N)。
    第二行为N个用空格隔开的非负整数,表示Ki

    输出格式
    一行,即最少按键次数,若无法到达,则输出−1。

    输入

    5 1 5
    3 3 1 2 5

    输出

    3

    #include<iostream>
    #include<queue>
    
    using namespace std;
    struct sta{
        int f;
        int steps;
        sta(int f,int steps):f(f),steps(steps){};
    };
    const int MAXN=300;
    int way[MAXN];//记录可以移动的步数
    int vis[MAXN];
    queue<sta> q;
    int main(){
        int n,a,b;//a为起点,b为终点
        cin>>n>>a>>b;
        for(int i=1;i<=n;i++){
            cin>>way[i];
        }
        q.push(sta(a,0));
        vis[a]=1;
        while(!q.empty()){
            sta current=q.front();
            //cout<<current.f<<endl;
            if(current.f==b){//出口
                cout<<current.steps<<endl;
                return 0;
            }
            int down=current.f-way[current.f];//向下
            if(down>=1&&vis[down]==0){
                q.push(sta(down,current.steps+1));
                vis[down]=1;
            }
            int up=current.f+way[current.f];//向下
            if(up<=n&&vis[up]==0){
                q.push(sta(up,current.steps+1));
                vis[up]=1;
            }
            q.pop();
        }
        cout<<-1<<endl;
    }
    
    

    01迷宫

    题目描述
    有一个仅由数字0与1组成的n×n格迷宫。若你位于一格0上,那么你可以移动到相邻4格中的某一格1上,同样若你位于一格1上,那么你可以移动到相邻4格中的某一格0上。
    你的任务是:对于给定的迷宫,询问从某一格开始能移动到多少个格子(包含自身)。

    输入格式
    第1行为两个正整数n,m。
    下面n行,每行n个字符,字符只可能是0或者1,字符之间没有空格。
    接下来m行,每行2个用空格分隔的正整数i,j,对应了迷宫中第i行第j列的一个格子,询问从这一格开始能移动到多少格。

    输出格式
    m行,对于每个询问输出相应答案。

    输入

    2 2
    01
    10
    1 1
    2 2

    输出

    4
    4

    #include<iostream>
    #include<queue>
    
    using namespace std;
    const int MAXN=2000;
    
    struct position{
        int x,y;
        position(int x,int y):x(x),y(y){};
    };
    int Map[MAXN][MAXN];
    int vis[MAXN][MAXN];
    int ans[10000000];//存的是各个颜色区域的结点数
    int color=0,n,m;
    int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    queue<position> q;
    void bfs(int x1,int y1){
        int cnt=0;//用来对当前颜色的区域来计数
        q.push(position(x1,y1));
        vis[x1][y1]=color;
        while(!q.empty()){
            position current=q.front();
            //cout<<current.x<<" "<<current.y<<endl;
            for(int k=0;k<4;k++){
                int x=current.x+way[k][0];
                int y=current.y+way[k][1];
                if(x>=1&&x<=n&&y>=1&&y<=n&&vis[x][y]==0&&Map[x][y]!=Map[current.x][current.y]){
                    q.push(position(x,y));
                    vis[x][y]=color;
                }
            }
            cnt++;
            q.pop();
        }
        //cout<<color<<endl;
        ans[color]=cnt;
    }
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                char c;
                cin>>c;
                Map[i][j]=c-'0';
                //cout<<Map[i][j]<<endl;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(vis[i][j]==0){
                    color++;//每一个color来区分一块互相可以到达的区域
                    //cout<<color<<endl;
                    bfs(i,j);//注意函数中不能出现i,j
                }
            }
        }
        for(int i=1;i<=m;i++){
            int xx,yy;
            cin>>xx>>yy;
            cout<<ans[vis[xx][yy]]<<endl;
        }
    
    
    }
    
    

    DFS

    八皇后问题

    题目描述
    一个如下的6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。
    在这里插入图片描述
    上面的布局可以用序列2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:
    行号 1 2 3 4 5 6
    列号 2 4 6 1 3 5
    这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
    并把它们以上面的序列方法输出,解按字典顺序排列。
    请输出前 3 个解。最后一行是解的总个数。

    输入格式
    一行一个正整数 nn,表示棋盘是 n \times nn×n 大小的。

    输出格式
    前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

    输入

    6

    输出

    2 4 6 1 3 5
    3 6 2 5 1 4
    4 1 5 2 6 3
    4

    #include<iostream>
    #include<cstdlib>
    using namespace std;
    int ans[13];//作为每次深搜出来的序列的结果
    int vis[13];
    int u[40];//正对角线
    int v[40];//副对角线
    int n;
    int Count=0;
    void print(){
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    
    void dfs(int x){//dfs中的参数是行号
        if(x>n){
            Count++;
            if(Count<=3) print();
            return ;
        }
        for(int i=1;i<=n;i++){//i表示尝试列号
            if(!vis[i]&&!u[x-i+n]&&!v[x+i]){//vis能保证不在同一列,u表示不在同一主对角(+n为了不为负数),v表示不在同一副对角
                //i-ans[j]为列差,x-j为行差
                vis[i]=1;
                u[x-i+n]=1;
                v[x+i]=1;
                ans[x]=i;
                dfs(x+1);
                //为了回溯
                vis[i]=0;
                u[x-i+n]=0;
                v[x+i]=0;
            }
        }
    }
    
    int main(){
        cin>>n;
        dfs(1);
        cout<<Count<<endl;
    }
    
    

    迷宫

    题目背景
    给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。

    题目描述

    输入格式
    第一行N、M和T,N为行,M为列,T为障碍总数。第二行起点坐标SX,SY,终点坐标FX,FY。接下来T行,每行为障碍点的坐标。

    输出格式
    给定起点坐标和终点坐标,问每个方格最多经过1次,从起点坐标到终点坐标的方案总数。

    输入

    2 2 1
    1 1 2 2
    1 2

    输出

    1

    #include<iostream>
    
    using namespace std;
    int n,m,t,sx,sy,fx,fy,Count=0;
    int Map[10][10];//相当于vis数组
    int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    void dfs(int x,int y){
        if(x==fx&&y==fy){
            Count++;
            return;
        }
        for(int i=0;i<4;i++){
            int dx=x+way[i][0];
            int dy=y+way[i][1];
            if(dx>=1&&dx<=n&&dy>=1&&dy<=n&&!Map[dx][dy]){
                Map[dx][dy]=1;
                dfs(dx,dy);
                Map[dx][dy]=0;
            }
        }
    }
    
    
    int main(){
        cin>>n>>m>>t>>sx>>sy>>fx>>fy;
        while(t--){
            int x,y;
            cin>>x>>y;
            Map[x][y]=1;
        }
        Map[sx][sy]=1;
        dfs(sx,sy);
        cout<<Count<<endl;
    }
    
    

    单词方阵

    题目描述
    给一n×n的字母方阵,内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*代替,以突出显示单词。例如:
    在这里插入图片描述
    输入格式
    第一行输入一个数nn。(7 \le n \le 1007≤n≤100)。

    第二行开始输入n \times nn×n的字母矩阵。

    输出格式
    突出显示单词的n \times nn×n矩阵。

    输入

    8
    qyizhong
    gydthkjy
    nwidghji
    orbzsfgz
    hhgrhwth
    zzzzzozo
    iwdfrgng
    yyyygggg

    输出

    yizhong
    gy
    *****
    ni*****
    oz
    ***
    hh***
    z
    o**
    i*****n

    y
    ****g

    #include<iostream>
    
    using namespace std;
    char Map[300][300];
    int vis[300][300];
    int way[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
    string yz="yizhong";//是从i开始比较
    int n;
    void dfs(int x,int y){
        for(int i=0;i<8;i++){//8个方向
            bool flag=true;
            for(int j=1;j<=6;j++){//需要比较的6,也相当于走的步数
                int dx=x+j*way[i][0];
                int dy=y+j*way[i][1];
                if(!(dx>=1&&dx<=n&&dy>=1&&dy<=n)||yz[j]!=Map[dx][dy]){
                    flag=false;
                }
            }
            if(flag){
                for(int j=0;j<7;j++){
                    int dx=x+j*way[i][0];
                    int dy=y+j*way[i][1];
                    vis[dx][dy]=1;
                }
            }
        }
    }
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>Map[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(Map[i][j]=='y'){
                    dfs(i,j);
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(vis[i][j]==1) cout<<Map[i][j];
                else cout<<'*';
            }
            cout<<endl;
        }
    }
    
    
    展开全文
  • BFS DFS

    2019-08-09 09:13:28
    BFS DFS 对比: BFS 空间是指数级别的 大(O(a^n)) 不会有爆栈的风险,因为该内存可以从堆中申请 可以搜最小(短) DFS 空间深度成正比 小(O(n)) 有爆栈的风险,比如树的深度最坏可能有 10万层 不能搜...

    BFS 和 DFS

    对比:

    BFS

    1. 空间是指数级别的 大(O(a^n))
    2. 不会有爆栈的风险,因为该内存可以从堆中申请
    3. 可以搜最小(短)

    DFS

    1. 空间和深度成正比 小(O(n))
    2. 有爆栈的风险,比如树的深度最坏可能有 10万层
    3. 不能搜最小(短)

    实际编程中:

    BFS:代码较多,需要维护一个队列

    DFS:代码简单,需要不断递归

    例题 1:

    279. 完全平方数

    思路:

    1. 初始点:0,如果加 1,状态从 0 转移到 1,如果加 4,状态从 0 转移到 4;在此基础上加 9,状态从 4 到 13;所以转移到 1,需要 1 步,转移到 13,需要 2 步
    2. 所以抽象成图论。从一个状态转移到另一个状态,边的权值为 1。状态就是从 1 到 n,求解的过程就是从 i 点 到 j 点转移的次数
    3. 需要让组成和的完全平方数的个数最少。我们从以上给出 DFS 和 BFS 性质可知,此题应用 BFS
    #include<iostream>
    #include <vector>
    #include <string>
    #include <queue>
    using namespace std;
    
    class solution
    {
    public:
    	int numSquares(int n)
    	{
    		queue<int> q;
    		vector<int> dist(n + 1, INT_MAX);
    		q.push(0);
    		dist[0] = 0;
    		while (q.size())
    		{
    			int t = q.front();
    			q.pop();
    			if (t == n)	return dist[t];
    			for (int i = 1; i*i + t <= n; i++)
    			{
    				int j = t + i*i;
    				if (dist[j] > dist[t] + 1)
    				{
    					dist[j] = dist[t] + 1;
    					q.push(j);
    				}
    			}
    		}
    		return 0;
    	}
    };
    
    
    int main()
    {
    	solution s;
    	cout << s.numSquares(12);
    
    	system("pause");
    	return 0;
    }
    

    代码解析:

    1. 记录状态,即当前应从哪一个点出发,同时宽搜后,下一次可以达到多个状态,也需要将其保存,以便不断循环执行代码,找到结果。

      利用一个队列,保存状态信息

      第一次赋初值

      0

      第二次循环

      先弹出状态 0,相当于从 0 点出发

      在满足条件下,保存从状态 0 出发可以转移到的状态

      1 4 9

      第三次循环

      先弹出状态 1,相当于从 1 点出发

      在满足条件下,保存从状态 1 出发可以转移到的状态

      4 9 2 5 10

      以此类推

    2. 还需要有一个矩阵来维护从状态 i 到状态 j 转移的最小步数(最小边),dist

      dist 矩阵,下标为状态,对应存储的值为最小转移步数

      利用上述每次需要遍历的状态(从 queue 中获取),通过计算,将结果存入 dist 中

      第一次:

      int t = q.front();
      q.pop();
      

      t = 0,可以转移到的状态所需步数如下,同时将其存入 queue 中

      0 1 2 3 4 5 6 7 8 9 10 11 12
      0 1 +∞ +∞ 1 +∞ +∞ +∞ +∞ 1 +∞ +∞ +∞

      第二次:

      t = 1

      0 1 2 3 4 5 6 7 8 9 10 11 12
      0 1 2 +∞ 1 2 +∞ +∞ +∞ 1 2 +∞ +∞

      第三次:

      t = 4

      0 1 2 3 4 5 6 7 8 9 10 11 12
      0 1 2 +∞ 1 2 +∞ +∞ 2 1 2 +∞ +∞

      以此类推,结果:

      0 1 2 3 4 5 6 7 8 9 10 11 12
      0 1 2 3 1 2 3 4 2 1 2 3 3
    展开全文
  • bfs和dfs

    2017-10-11 19:40:13
    一、广度优先算法BFS(Breadth First Search) 基本实现思想  (1)顶点v入队列。  (2)当队列非空时则继续执行,否则算法结束。  (3)出队列取得队头顶点v;  (4)查找顶点v的所以子节点,...

    一、广度优先算法BFS(Breadth First Search)

    基本实现思想

            (1)顶点v入队列。

            (2)当队列非空时则继续执行,否则算法结束。

            (3)出队列取得队头顶点v;

            (4)查找顶点v的所以子节点,并依次进入队列;

            (5)转到步骤(2)。

     

     python伪代码:

      def BFS(root)

        Q=[]

        Q.append(root[0])

        while len(Q)>0:

          node=Q.pop(0)

          print (node)

          #将所有子节点入队列

          for i in node_child:

            Q.append(node_child[i])

     

    :该算法很巧妙的利用了队列的先进先出策略。

     

    二、深度优先算法DFS(Depth First Search)

     

     

    基本思想: 

    递归实现:

                 (1)访问顶点v,打印节点;

                 (2)遍历v的子节点w,while(w存在),递归执行该节点;

    代码:

      /布尔型数组Visited[]初始化成false
      void DFS(Vetex v)
      {
          Visited[v] = true;
          for each w adjacent to v
              if (!Visited[w])
                  DFS(w);
      }

     

    非递归实现:

                 (1)访问顶点v,顶点v入栈S,打印输出顶点,visited[v]=1

                  (2)while(栈S非空)

                          x=栈S的顶元素(不出栈);

                          if(存在并找到未被访问的x的子结点w)

                            访问w,打印输出,visited[w]=1;w进栈;

                          else

                            x出栈;

     注:visited[x]=1,标记该节点已被访问



    算法题:

    107. Binary Tree Level Order Traversal II

    Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

    For example:
    Given binary tree [3,9,20,null,null,15,7],

        3
       / \
      9  20
        /  \
       15   7
    

    return its bottom-up level order traversal as:

    [
      [15,7],
      [9,20],
      [3]
    ]
    1.bfs (2ms)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> list = new LinkedList<List<Integer>>();
            if(root==null) return list;
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            while(queue.size()>0){
                int num = queue.size();
                LinkedList<Integer> sublist = new LinkedList<Integer>();
                for(int i=0;i<num;i++){
                    TreeNode node = queue.poll();
                    if(node.left!=null) queue.add(node.left);
                    if(node.right!=null) queue.add(node.right);
                    
                    sublist.add(node.val);
                }
                list.add(0,sublist);
                
            }
            return list;
        }
    }


    2.dfs (3ms)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> list = new LinkedList<List<Integer>>();
            dfs(list,0,root);
            return list;
        }
        public void dfs(List<List<Integer>> list,int level,TreeNode node){
            if(node == null) return;
            if(level>=list.size()) list.add(0,new LinkedList<Integer>());
            list.get(list.size()-1-level).add(node.val);
            dfs(list,level+1,node.left);
            dfs(list,level+1,node.right);
        }
    }

    展开全文
  • BFS和DFS算法原理(通俗易懂版)

    万次阅读 多人点赞 2016-11-16 17:25:32
    DFS 算法 思想:一直往深处走,直到找到解或者走不下去为止 BFS算法 DFS:使用栈保存未被检测的结点...结点按照宽度优先的次序被访问进出队列。 框架: BFS: #include #include #include #include
    DFS 算法
    
    思想:一直往深处走,直到找到解或者走不下去为止
    BFS算法
    DFS:使用保存未被检测的结点,结点按照深度优先的次序被访问并依次被压入栈中,并以相反的次序出栈进行新的检测。
    BFS:使用队列保存未被检测的结点。结点按照宽度优先的次序被访问和进出队列。
    框架:
    BFS:
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn=100;
    bool vst[maxn][maxn]; // 访问标记
    int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量

    struct State // BFS 队列中的状态数据结构
    {
    int x,y; // 坐标位置
    int Step_Counter; // 搜索步数统计器
    };

    State a[maxn];

    bool CheckState(State s) // 约束条件检验
    {
    if(!vst[s.x][s.y] && ...) // 满足条件
    return 1;
    else // 约束条件冲突
    return 0;
    }

    void bfs(State st)
    {
    queue <State> q; // BFS 队列
    State now,next; // 定义2 个状态,当前和下一个
    st.Step_Counter=0; // 计数器清零
    q.push(st); // 入队
    vst[st.x][st.y]=1; // 访问标记
    while(!q.empty())
    {
    now=q.front(); // 取队首元素进行扩展
    if(now==G) // 出现目标态,此时为Step_Counter 的最小值,可以退出即可
    {
    ...... // 做相关处理
    return;
    }
    for(int i=0;i<4;i++)
    {
    next.x=now.x+dir[i][0]; // 按照规则生成下一个状态
    next.y=now.y+dir[i][1];
    next.Step_Counter=now.Step_Counter+1; // 计数器加1
    if(CheckState(next)) // 如果状态满足约束条件则入队
    {
    q.push(next);
    vst[next.x][next.y]=1; //访问标记
    }
    }
    q.pop(); // 队首元素出队
    }
     return;
    }

    int main()
    {
    ......
     return 0;
    }

    DFS:
    DFS:
    /*
    该DFS 框架以2D 坐标范围为例,来体现DFS 算法的实现思想。
    */
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    const int maxn=100;
    bool vst[maxn][maxn]; // 访问标记
    int map[maxn][maxn]; // 坐标范围
    int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量,(x,y)周围的四个方向

    bool CheckEdge(int x,int y) // 边界条件和约束条件的判断
    {
    if(!vst[x][y] && ...) // 满足条件
    return 1;
    else // 与约束条件冲突
    return 0;
    }

    void dfs(int x,int y)
    {
    vst[x][y]=1; // 标记该节点被访问过
    if(map[x][y]==G) // 出现目标态G
    {
    ...... // 做相应处理
    return;
    }
    for(int i=0;i<4;i++)
    {
    if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
    dfs(x+dir[i][0],y+dir[i][1]);
    }
    return; // 没有下层搜索节点,回溯
    }
    int main()
    {
    ......
    return 0;
    }
    展开全文
  • MFC树控件BFS和DFS示例

    2020-09-24 09:27:41
    MFC自带树控件CTreeCtrl的搜索遍历示例,代码包括对指定节点及子节点进行勾选操作、从指定节点开始搜索操作、按层次打印树节点,涉及BFS和DFS算法。
  • 基于临接表的BFS和DFS

    2010-12-01 22:45:04
    广度优先搜索(Breadth-First-Search)深度优先搜索(Deep-First-Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索.其中有很多的算法都用到了这两种思想,比如:Dijkstra单源最短路径算法Prim最小生成...
  • 这是山东大学可视化课程项目,用js实现的BFS和DFS,详细的展示了BFS和DFS的运行过程,网页可交互。
  • 算法 BFS和DFS

    2018-09-29 15:13:25
    说一下BFS和DFS,这是个比较重要的概念,是很多很多算法的基础。  不过在说这个之前需要先说一下图和树,当然这里的图不是自拍的图片了,树也不是能结苹果的树了。这里要说的是图论和数学里面的概念。    以上...

空空如也

1 2 3 4 5 ... 20
收藏数 6,016
精华内容 2,406
关键字:

bfs和dfs