投稿
  1. 极客之音首页
  2. 技术随笔

“ 寻友之旅 “ 的三种解决办法（BFS 、双向BFS、Dijsktra堆优化）

飞熊 • • 技术随笔 • 阅读 212

不管现实多么惨不忍睹，都要持之以恒地相信，这只是黎明前短暂的黑暗而已。不要惶恐眼前的难关迈不过去，不要担心此刻的付出没有回报，别再花时间等待天降好运。真诚做人，努力做事！你想要的，岁月都会给你。“ 寻友之旅 “ 的三种解决办法（BFS 、双向BFS、Dijsktra堆优化），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com，来源：原文

题目来源于：字节跳动青训营主题创作

” 寻友之旅 ” 的三种解决办法！

在这里插入图片描述

                        💧本文将分别讲解如何使用BFS、双向BFS以及 Dijsktra堆优化的方法来解决此题~ 一起来看看吧！💧          

🌷 仰望天空，妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 数据结构与算法专栏的文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺
🪁 希望本文能够给读者带来一定的帮助🌸文章粗浅，敬请批评指正！🐥

文章目录

前言

这是我在青训营里面遇到的一个主题创作题目，整好最近在复习算法，整合三种解决方案给大家。（本文完全由本人自己总结，如有问题请在评论区指出）

题目——寻友之旅
小青要找小码去玩，他们的家在一条直线上，当前小青在地点 N ，小码在地点 K （0≤N , K≤100 000），并且小码在自己家原地不动等待小青。小青有两种交通方式可选：步行和公交。
步行：小青可以在一分钟内从任意节点 X 移动到节点 X-1 或 X+1
公交：小青可以在一分钟内从任意节点 X 移动到节点 2×X （公交不可以向后走）
请帮助小青通知小码，小青最快到达时间是多久？
输入： 两个整数 N 和 K
输出： 小青到小码家所需的最短时间（以分钟为单位）

错误思路——动态规划

拿到这道题时，我们被小青有两种交通方式可选：步行和公交。（前进一步、后退一步、直达2 * current）这句话吸引了，可能首先想到用动态规划来做。
似乎好像大概是没问题的，那我们根据动态规划的思想：”当前的结果都是由前面的结果推导出来的”进行推导，举例：例如小码的地点在200这个结点（即终点下标为200），我们可以画出的示意图如下图所示：

50

99

100

101

198

199

200

201

202

我们会发现一个问题！！！200可以由199推导过来，而199同样可以由200推导过来，emmm…这不成环了吗？其实，动态规划是拓扑图，一般来说是由当前状态推出下一状态，是无环的！ ~好家伙，那这题咋做呢？经过一些思考，我们会想到用搜索来做，dfs和bfs里面，我选bfs，因为dfs每次都要搜到底，容易爆栈，而且里面的控制条件写起来相对bfs可能要更难一些，所以我们尝试用bfs来解此题！

BFS题解

bfs找最短，最多就是100000的空间，vis记录一下已经访问过的点
dfs是找到底，可能会爆栈和超时
这个题相当于一维走迷宫，前进一步、后退一步、前进到两倍下标的地方，
二维走迷宫是上下左右走而已
以start为出发点，每次弹出元素时时先记录当前队列中元素的数量，这些数量就是以上一次访问到的点作为起点找出的其他能够访问的点的数量，方便后面弹出指定数量的元素；同时用vis[]来记录已经访问过的点，由于流程是逐层递进的，所以每个初次访问到的点所在的时间一定是最短时间！（举个例子：y点最初通过x点访问到，在后续的情况中，可能还会通过其他点再次访问到该点，而此时的时间一定是大于等于初次访问到y点的。）

代码如下（java）：

import java.io.*;
import java.util.*;

public class Main {
    static int n, k;
    static boolean[] vis = new boolean[100001];

    public static void main(String[] args) throws IOException {
        //例如输入：20 38   输出 2
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        k = Integer.parseInt(line[1]);
        if (n == k)
            System.out.println(0);
        else if (n < k) {
            System.out.println(bfs(n, k));
        } else {
            System.out.println(n - k);
        }

    }

    private static int bfs(int start, int target) {
        int time = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        vis[start] = true;
        while (!queue.isEmpty()) {
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                Integer current = -1;
                if (!queue.isEmpty())
                    current = queue.poll();
                if (current == target) {
                    return time;
                }
                if (current - 1 >= 0 && !vis[current - 1]) {
                    queue.offer(current - 1);
                    vis[current - 1] = true;
                }
                if (current + 1 <= 100000 && !vis[current + 1]) {
                    queue.offer(current + 1);
                    vis[current + 1] = true;
                }
                if (current * 2 <= 100000 && !vis[current * 2]) {
                    queue.offer(current * 2);
                    vis[current * 2] = true;
                }
            }
            time++;
        }
        return -1;
    }

}

双向BFS题解

分别从起点和终点出发进行搜索，这里将起点走过的地点标记为1，终点走过来的路标记为2，如果能相遇（vis[current] + vis[other] == 3），则已经找到最短时间。

代码如下（java）：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
    static int n, k;
    static int[] vis = new int[100001];//前队标记1  后队标记2  相加得3 即为相遇
    static int[] dis = new int[100001];
    static Queue<Integer> frontQueue = new LinkedList<>();//从起点开始搜
    static Queue<Integer> backQueue = new LinkedList<>();//从终点开始搜

    public static void main(String[] args) throws IOException {
        //例如输入：20 38   输出 2
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        k = Integer.parseInt(line[1]);
        if (n == k)
            System.out.println(0);
        else if (n < k) {
            System.out.println(dbfs(n, k));
        } else {
            System.out.println(n - k);
        }

    }

    private static int dbfs(int start, int target) {
        int flag;
        int length;
        Queue<Integer> curQueue;
        frontQueue.offer(start);
        backQueue.offer(target);
        vis[start] = 1;
        vis[target] = 2;
        while (!frontQueue.isEmpty() && !backQueue.isEmpty()) {
            if (frontQueue.size() <= backQueue.size()) {
                flag = 1;
                length = frontQueue.size();
            } else {
                flag = 0;
                length = backQueue.size();
            }
            for (int i = 0; i < length; i++) {
                Integer curPoll;
                if (flag == 1) {
                    curPoll = frontQueue.poll();
                    curQueue = frontQueue;
                } else {
                    curPoll = backQueue.poll();
                    curQueue = backQueue;
                }
                if (curPoll - 1 >= 0 && vis[curPoll - 1] == 0) {
                    curQueue.offer(curPoll - 1);
                    vis[curPoll - 1] = 1;
                    dis[curPoll - 1] = dis[curPoll] + 1;
                } else if (curPoll - 1 >= 0 && vis[curPoll - 1] != 0) {
                    if (vis[curPoll] + vis[curPoll - 1] == 3) {
                        return dis[curPoll] + 1 + dis[curPoll - 1];
                    }
                }
                if (curPoll + 1 <= 100000 && vis[curPoll + 1] == 0) {
                    curQueue.offer(curPoll + 1);
                    vis[curPoll + 1] = 1;
                    dis[curPoll + 1] = dis[curPoll] + 1;
                } else if (curPoll + 1 <= 100000 && vis[curPoll + 1] != 0) {
                    if (vis[curPoll] + vis[curPoll + 1] == 3) {
                        return dis[curPoll] + 1 + dis[curPoll + 1];
                    }
                }
                if (curPoll * 2 <= 100000 && vis[curPoll * 2] == 0) {
                    curQueue.offer(curPoll * 2);
                    vis[curPoll * 2] = 1;
                    dis[curPoll * 2] = dis[curPoll] + 1;
                } else if (curPoll * 2 <= 100000 && vis[curPoll * 2] != 0) {
                    if (vis[curPoll] + vis[curPoll * 2] == 3) {
                        return dis[curPoll] + 1 + dis[curPoll * 2];
                    }
                }
            }
        }
        return -1;
    }

}

Dijsktra（堆优化）题解

我们把题目中的时间想象成路径，求“最短时间”是不是就变成了求“最短路径”问题了？（不过此题较为特殊，因为所有的移动方式所花费的时间都为1，即所有边的长度都为1。）
但是我们需要注意样例范围：（0≤N , K≤100 000）
朴素算法的时间复杂度是n²，而一般题目给的数据都是差不多le5,这时候肯定会爆
于是乎，我们想到用堆优化来降低时间复杂度，将时间复杂度从n²降到nlogn+m
堆优化了每次找离起点最近的点的时间复杂度
用“链式前向星”来创建图（如果不清楚这种建图方式可以先看下文部分【什么是“链式前向星”？】）

代码如下（java）：

import java.io.*;
import java.util.*;

public class Main {
    static int[] head, next, ends;
    static int[] times;//结果
    static int n = 100000, m = 300000;//最多有n个顶点，m条边
    static int start, target, total = 0;//++total：从第一条边到最后一条边

    public static void main(String[] args) throws IOException {
        //例如输入：20 38   输出 2
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        start = Integer.parseInt(line[0]);
        target = Integer.parseInt(line[1]);
        if (start == target)
            System.out.println(0);
        else if (start < target) {
            head = new int[m + 1];//表示以 i 为起点的最后一条边的编号
            next = new int[m + 1];//存储与当前边起点相同的上一条边的编号
            ends = new int[m + 1];//存储边的终点
            times = new int[n + 1];
            Arrays.fill(head, -1);//初始化
            for (int i = 0; i <= n; i++) {
                if (i - 1 >= 0) add(i, i - 1);
                if (i + 1 <= n) add(i, i + 1);
                if (i * 2 <= n) add(i, i * 2);
            }
            dijkstra(start);
            System.out.println(times[target]);
        } else {
            System.out.println(start - target);
        }
    }

    private static void dijkstra(int startPoint) {
        for (int i = 1; i <= n; i++) times[i] = Integer.MAX_VALUE;
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(startPoint, times[startPoint]));
        times[startPoint] = 0;//起始位置，应当赋上最好的情况
        while (!queue.isEmpty()) {
            Node x = queue.poll();//当前点
            //链式前向星的遍历方法，遍历出以x为起点的所有边
            for (int i = head[x.num]; i != -1; i = next[i]) {//i表示：第 i 条边
                int j = ends[i];//第 i 条边的终点
                if (times[j] > times[x.num] + 1) {//如果length(起点-->终点) > length(起点 --> 当前点) + length(当前点 --> 终点)
                    times[j] = times[x.num] + 1;//更新起点到终点的最短距离
                    queue.offer(new Node(j, times[j]));//并将这个终点入队，以便之后通过该点访问其他顶点
                }
            }
        }
    }

    static class Node implements Comparable<Node> {
        int num;
        int dis;

        public Node(int num, int dis) {
            this.num = num;
            this.dis = dis;
        }

        @Override
        public int compareTo(Node o) {
            return dis - o.dis;
        }
    }

    private static void add(int start, int end) {
        ends[++total] = end;
        next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号
        head[start] = total;//更新以start为起点的上一条边的编号
    }

}

或许有同学会不太清楚上述的建图方式，这里单独讲一下 ↓ 也可以看我的 这篇文章

什么是“链式前向星”？

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》

链式前向星其实就是静态建立的邻接表;
时间效率为O（n）、空间效率也为O（n）、遍历效率也为O（n）;
对于下面的数据:第一行5个顶点、7条边。接下来是边的起点，终点和权值。如：边1 -> 2 权值为1。

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

*链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：

1 //以1为起点的边的集合
1 5 6 
1 3 4 
1 2 1 

2 //以2为起点的边的集合 
2 3 2

3 //以3为起点的边的集合 
3 4 3

4 //以4为起点的边的集合
4 5 7
4 1 5 

5 //以5为起点的边不存在

我们先对上面的7条边进行编号第一条边是0以此类推编号【0~6】。
然后我们要知道两个变量的含义：

  • Next，表示与这个边起点相同的上一条边的编号。
  • head[ i ]数组，表示以 i 为起点的最后一条边的编号。

head数组一般初始化为-1， 为什么是 -1后面会讲到。加边函数是这样的：

//java版本 
static int total = 0;//total++：记录从第一条边到最后一条边 
private static void add(int start, int end, long weight) {//链式前向星的创建方法 
    ends[total] = end; 
    weights[total] = weight; 
    next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号 
    head[start] = total++;//更新以start为起点的上一条边的编号 
}

我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：
对于1 2 1这条边：end[0] = 2; next [0] = -1; head[1] = 0;

对于2 3 2这条边：end[1]= 3; next [1]= -1; head[2] = 1;

对于3 4 3这条边：end[2] = 4; next [2]= -1; head[3] = 2;

对于1 3 4这条边：end[3] = 3; next [3]= 0; head[1] = 3;

对于4 1 5这条边：end[4] = 1; next [4]= -1; head[4] = 4;

对于1 5 6这条边：end[5] = 5; next [5]= 3; head[1] = 5;

对于4 5 7这条边：end[6] = 5; next [6]= 4; head[4] = 6;

遍历函数是这样的：

//java版本
static int[] head;//表示以 i 为起点的最后一条边的编号
static int[] next;//存储与当前边起点相同的上一条边的编号
static int[] ends;//存储边的终点
static long[] weights;//权值

//链式前向星的遍历方法，遍历出以x为起点的所有边
for (int i = head[x]; i != -1; i = next[i]) {//i表示：第 i 条边
    System.out.println(i + "这条边的终点：" + ends[i] + "这条边的权值：" + weights[i]);
}
/**
第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。
第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，
注意head[ i ]中存的是以 i 为起点的最后一条边的编号。
然后通过next[ j ]来找下一条边的编号。我们初始化head为-1，
所以找到你最后一个边（也就是以 i 为起点的第一条边）时，
你的next[ j ]为 -1作为终止条件。
*/

现在再回头去看代码，是不是更容易理解了呢？(*￣︶￣)

相关的题还有：蓝桥王国，评论区里面有我的题解 ↓ 欢迎大家来踩踩~

image.png

总结

三种方法都能做出此题（或许还有更多方法），但是我们必须思考：如果这个题变个形————比如把第二个条件改一下：“小青可以在times[x]分钟内从任意节点X移动到节点2*X ”，那这个题就变成了一个带权的图，用bfs就不太行了。bfs就是特殊的最短路，边权为1的最短路可以用bfs，而堆优化可以有效降低朴素dijsktra的时间复杂度，OI必备，希望大家仔细理解后将其掌握！

大家还有其他解法吗？欢迎在评论区留言讨论！~

文章粗浅,如果本文对大家有帮助的话，希望可以点赞支持下~~~ (*￣︶￣)

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/159806.html

赞 (0)
飞熊的头像飞熊bm
0 0

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！