换人！小编连怎么能快速找到女朋友都不知道

2022-10-30 105

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 换人！小编连怎么能快速找到女朋友都不知道

换人！小编连怎么能快速找到女朋友都不知道

在数据结构中对广撒网有一种类似的定义，叫做广度优先搜索（Breadth-First-Search），简称BFS。是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次进的，依次往外搜索。

先把一个顶点附近的顶点查找一遍，然后再从它附近的顶点开始查找，重复一样的操作。如上图所示，先从A点出发，查找离A点最近的B和C，如果这两个不是想要的节点，那么就以B和C为起点，查找与B和C相连接的顶点。广度优先搜索策略得到的路径是起始点到终点的最短路径。

为什么说广度优先搜索策略找到的路径是最短路径呢？最简单的一种解释方式，想想圆规画圆，以A点为顶点，不断的增加圆的半径。

这个像不像你先跟某寝室的女孩子小A相处，然后发现小A不跟你玩，然后你开始通过A对她的室友下手，emmm……最后得出结论，渣男实锤了。我们下次还是聊点专一的操作吧。

编程逻辑

从一个顶点 A 出发，查找与 A 相通的其它顶点
判断查找的顶点是否访问过，访问过则直接跳过
如果顶点没有访问过，判断顶点是否为要查找的顶点
如果是不是要查找到顶点，则标记顶点为已访问的状态
把刚刚更改状态的顶点放入待查找顶点集合
接着寻找顶点 A 的相通顶点，重复 2 ~ 5 的步骤
当 A 的通顶点都遍历一遍时，从待查找顶点集合中取出一个元素，重复上述 1 ~ 6 的操作

代码实现

import java.util.LinkedList;
import java.util.Queue;
/**
 * 广度优先搜索
 *
 * @since 2021-03-18
 */
public class GrapBfs {
    // 顶点的个数
    private int v;
    // 邻接表
    private LinkedList<Integer>[] adj;
    public GrapBfs(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
        visited = new boolean[v];
        pre = new Integer[v];
        for (int i = 0; i < v; i++) {
            pre[i] = -1;
        }
    }
    /**
     * 一条边的两个顶点，表示两个边相连
     *
     * @param s 顶点
     * @param t 顶点
     */
    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }
    public int getV() {
        return v;
    }
    public LinkedList<Integer>[] getAdj() {
        return adj;
    }
    // 存放接下来需要查找其周边顶点的顶点
    Queue<Integer> queue = new LinkedList<>();
    // 记录顶点是否已经被访问过
    boolean[] visited;
    // 记录顶点的前一个顶点
    Integer[] pre;
    /**
     * 广度优先搜索
     * 
     * @param start 起始位置
     * @param end 结束位置
     */
    public void bfs(int start, int end) {
        if (start == end) {
            return;
        }
        queue.offer(start);
        Integer present;
        visited[start] = true;
        while (!queue.isEmpty()) {
            present = queue.poll();
            LinkedList<Integer> linkedList = adj[present];
            for (Integer nextVertex : linkedList) {
                if (visited[nextVertex]) {
                    continue;
                }
                visited[nextVertex] = true;
                pre[nextVertex] = present;
                if (nextVertex == end) {
                    print(pre, nextVertex);
                    System.out.println(end);
                    return;
                }
                queue.offer(nextVertex);
            }
        }
    }
    /**
     * 输出查找的路径
     * 
     * @param pre 记录顶点前一个顶点的数组
     * @param nextVertex 当前顶点的下一个顶点
     */
    private void print(Integer[] pre, Integer nextVertex) {
        if (pre[nextVertex] == -1) {
            return;
        }
        print(pre, pre[nextVertex]);
        System.out.print(pre[nextVertex]);
    }
    public static void main(String[] args) {
        GrapBfs grap = new GrapBfs(9);
        grap.addEdge(1, 2);
        grap.addEdge(1, 4);
        grap.addEdge(2, 3);
        grap.addEdge(2, 5);
        grap.addEdge(3, 6);
        grap.addEdge(4, 5);
        grap.addEdge(5, 6);
        grap.addEdge(5, 7);
        grap.addEdge(6, 8);
        grap.addEdge(7, 8);
        grap.bfs(1, 7);
    }
}