图的遍历

发表于2021-09-20更新于2021-09-20阅读次数

dfs bfs ..

dfs

dfs需要解决的最关键问题：
当无法继续往下遍历时，如何回退到上一步
方法：看到关键字回退，应该想到递归，递归就是一步步往下处理，处理到末尾再一步步回退，与dfs很契合
对于dfs过程中的结点，有先入后出的特点，FILO,即栈。
（栈这里不懂看这篇https://blog.csdn.net/saltriver/article/details/54429068）
下面演示用dfs数出图中与源点距离大于d的点的个数

1
2
3
4
5
6
7
void dfs(ll u,ll step){
    if(step>d)  ans++;
    for(ll i=head[u];i!=-1;i=edge[i].next){//链式前向星存储
        dfs(edge[i].to,step+1);
    }
    return ;
}

灵活运用(dfs思维好题)

题目链接 https://www.luogu.com.cn/problem/P3916
题意 给出N个点，M条边的有向图，对于每个点v，求A(v)表示从点v出发，能到达的编号最大的点。
思路 编号最大的点，我们不妨从最大的点开始遍历，反向建边，这样子从最大的点遍历到的所有点，就都是以该点作为最大值

灵活运用（较简单dfs）

题目链接 https://www.luogu.com.cn/problem/P1123
题意 一个N×M的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻8个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
对于100%的数据，N, M≤6,T≤20，T是样例数
思路 简单dfs

灵活运用（dfs思维好题）

题目链接 https://ac.nowcoder.com/acm/contest/188/C?&headNav=www&headNav=acm&headNav=acm&headNav=acm
题意 小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度，小w现在在点x上，她想知道从点x出发经过每个点至少一次，最少需要走多少路
思路 只有从起点到各个结点中，最长的那个路径需要走一次，其他路径都需要走两次

1
2
3
4
5
6
7
void dfs(ll u,ll uu,ll length){
      ans=max(ans,length);
      for(ll i=head[u];~i;i=edge[i].next){
          if(edge[i].to==uu)  continue;
          dfs(edge[i].to,u,length+edge[i].w);
      }
}

灵活运用（细节dfs）

题目链接 https://vjudge.net/problem/HDU-2821
题意 有一个R*C的方格，‘.’代表空地，‘az’分别代表该处有126个箱子，某人可以从距离箱子至少一个空格处推箱子，推一次此处少一个箱子，如果这个格还有其他箱子，则和它下一个格的箱子合并或到下一个格，朝着某个方向一直推到边界或者遇到箱子不能推为止（即箱子数多于1的堆在边界）才可以换方向，任意输出一种可以把箱子推完的方案，输出推箱子时起点的位置以及推箱子时的方向。
注意：①起点不能有箱子。②必须要隔一个位置才能碰。③碰的箱子在边上时，剩下的箱子不能移出矩形范围。④格子在边上时，碰之后如果还有格子剩余，pusher的位置就不在边上，否则就在边上。
思路 细节dfs，先预处理下，将’.’换成数字0,abcd换成对应数字即可
踩坑 别用getchar()一个个读入处理，容易出错！！！
小技巧 双重循环还可以这样退出！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ll dfs(ll x,ll y,ll cnt,string s,ll d,ll b){//d 1 2 3 4,上右下左，b为间隙数。dfs找到返回1，否则返回0
    if(x<1 || x>r || y<1 || y>c)  return 0;//当前越界
    if(cnt==0){//箱子全部清除
        outs=s;
        return 1;
    }  
    if(d==0){//d为0，选择方向
        for(ll i=1;i<=4;i++){
            if(dfs(x+dir[i][0],y+dir[i][1],cnt,s+ar[i],i,b+1))  return 1;
        }
    }
    else{//d不为0
        if(gra[x][y]==0){//当前位置是道路
            if(dfs(x+dir[d][0],y+dir[d][1],cnt,s,d,b+1))  return 1;
        }  
        else{//当前位置是与木块重合，即撞到木块，
            if(b<2)  return 0;//如果没有间隙，即必须要隔一个位置才能碰
            if(x+dir[d][0]<1 || x+dir[d][0]>r || y+dir[d][1]<1 || y+dir[d][1]>c){//如果后面是边界
                ll t=gra[x][y];
                if(t>1)  return 0;//如果箱子数比1多
                gra[x][y]=0;
                if(dfs(x,y,cnt-1,s,0,0))  return 1;
                gra[x][y]=1;
            }
            else{//如果后面不是边界
                ll t=gra[x][y];
                gra[x][y]=0;
                gra[x+dir[d][0]][y+dir[d][1]]+=t-1;
                if(dfs(x,y,cnt-1,s,0,0))  return 1;
                gra[x][y]=t;//回溯
                gra[x+dir[d][0]][y+dir[d][1]]+=1-t;
            }
        }
    }
    return 0;
}

bfs

结点性质符合FIFO，即队列

1
2
3
4
5
6
7
8
9
10
11
12
放入0点到队列里。
while（队列不为空）{
        取出队列里的一个点为A。
        弹出A
    for（遍历A点所有相连的点）{
        if(该点没有被访问过) {
        记录该点访问过
        该点入队列
        }
    }
}