图上BFS和DFS

166天前 · OI · 12次阅读

假设我们不会DFS和BFS,因为DFS和BFS本身就是图而来的。

补充一下,之前没有说清楚,无向图的本质是存储有向图。

有向有权图是图的存储的终极形式。

补充知识:C++11循环

c++11有增强for循环,可以这样遍历整个数组:

for (auto item : array)
    {
        cout << item << " ";
    }

DFS

image.png

想一想为什么他叫DFS?因为DFS是deep first search,深度优先搜索!
他先搜索的深度,一条路走到黑再回头(~小朋友可不能学DFS一样一路走到黑哦~~)

如图现在我们需要用a~z的字母把他们4个格子填满,DFS会先填第一个并且考虑a然后在第一个为a的情况下考虑第二个。以此类推,当全部填满的时候就会回头考虑第四个填b。

这就是DFS:勇往直前,碰壁回头。

eg:跑路

我们混得不好准备跑路,需要从城市1跑路到终点城市n。

问能否成功跑路?

定义vis[x]表示x节点是否经过,vector <int> e[x]表示x城市的道路。

void dfs(int x) {
    if(vis[x]) return;
    vis[x] = 1;
    if(x == n)          // 成功跑到
        ans = true;
    for(int &p: e[x])
        dfs(p);         // 考虑从 x 能直接跑到的所有的 p,递归过去
}

这样我们就完成了图上DFS遍历!

DFS:深度第一!上面说得优先深度!

BFS: 广度第一!上面说得优先访问每一条边

BFS

BFS(breadth first search)顾名思义,广度优先搜索自然是广度第一。

优先搜索每一条边。

image.png
可以看到,搜完第1条直接搜索第二条,将第一条压入队列,搜完第一层再取出。所以dfs是一层一层的搜索的。

eg:跑路

没错,又是我!

说明不必再提。

BFS需要队列来存储搜到哪.

还是和刚刚一样,定义vis[x]表示x节点是否经过,vector <int> e[x]表示x城市的道路。

void bfs() {
    queue <int> q;      // STL 容器有二次内存分配机制
    // 把起点加进队列
    q.push(1);
    
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        // 取出队首,访问

        if(vis[now]) continue;      // 防止重复访问
        vis[now] = 1;

        if(now == n) {
            puts("Yes");
            return;
        }

        for(int &p: e[now])     // 把相邻的点丢进队列
            q.push(p);
    }

    puts("No");
}

这样我们就完成了图上BFS!

This post was written on August 17, 2022.
👍 0

none

最后修改于7天前

评论

贴吧 狗头 原神 小黄脸
收起

贴吧

  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡
  • 贴吧泡泡

狗头

  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头
  • 狗头

原神

  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神
  • 原神

小黄脸

  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸
  • 小黄脸

目录

avatar

only_matthew

人生如戏,戏如人生。

41

文章数

2

评论数

7

分类