无权重最短路径问题：广度优先搜索 & Java 实现_无权最短路径算法java实现

一、什么是图

通俗的说，图就是由 顶点（Vertex） 和 边（edge） 组成的。一般来说又分为 有向图 和 无向图，即顶点到顶点的边是否是有方向区分的。

二、广度优先搜索

1. 概念

广度优先搜索（Breadth First Search）通常用于指出是否存在一条路径由顶点 A 到达顶点 B，如果有，则找出顶点 A 到顶点 B 的最短路径。
注意，这里的最短路径是没有权重概念的，即可以认为任一边的长度均为 1。

2. 步骤

首先，我们从顶点 A 出发，找出它的所有直接邻居点（可以想象为一度人脉），检查这里面是否存在顶点 B。
然后，假设上述 “一度人脉” 中不存在顶点 B，这将邻居点的邻居点（可以想象为二度人脉）也加入到搜索队列中，并检查其中是否存在顶点 B。
如上，我们依次扩大到 “三度人脉”、“四度人脉” … 直到找到顶点 B 为止。
如果找完了都找不到顶点 B 的话，则说明图中不存在顶点 A 到顶点 B 的路径。

注意： 找过的点务必不要再去检查，否则可能导致无限循环！

3. 运行时间

广度优先搜索的运行时间为 O(顶点数 + 边数)，通常记为 O(V + E)。

三、实例分析

1. 如下给定一个图，求 “顶点0” 到 “顶点8” 的最短路径

2. 思路分析

• 首先我们可以想到，顶点是一类拥有共同特性的对象，因此我们可以创建一个 Vertex 类来表示图中的顶点。它应该包含 自己的id，有哪些邻居 等基本特性。
• 其次为了代码实现和记录搜索路径，Vertex 类还需要一个 是否被检查过 和 它的上一个顶点是谁 这两个属性。
• 然后，我们选择 队列 作为我们的数据结构，我们先将起始点的直接邻居全部添加到队列中去，依次从队首取出元素比较，如果不是我们要找的点这将其邻居（这里就是类似第二度人脉了）添加到队尾。
• 对于检查过的点，我们选择跳过，避免无限循环。
• 我们只需要重复上述过程，直到找到终点或是队列为空时结束。

3. 代码实现

首先创建一个 Vertex 类，如下：

import java.util.LinkedList;

public class Vertex {

    private int id; // 顶点的标识
    private LinkedList<Vertex> neighbors; // 这个顶点的邻居顶点
    private boolean isSerched; // 这个顶点是否被搜索过了
    private Vertex predecessor; // 这个顶点的前驱，用来记录路径的
    
    public Vertex(int id) {
        this.id = id;
    }
    
    public void addNeighbor(Vertex... vertexes) {
        this.neighbors = new LinkedList<>();
        for (Vertex vertex : vertexes) {
            this.neighbors.add(vertex);
        }
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public LinkedList<Vertex> getNeighbors() {
        return neighbors;
    }

    public void setNeighbors(LinkedList<Vertex> neighbors) {
        this.neighbors = neighbors;
    }

    public boolean isSerched() {
        return isSerched;
    }

    public void setSerched(boolean isSerched) {
        this.isSerched = isSerched;
    }

    public Vertex getPredecessor() {
        return predecessor;
    }

    public void setPredecessor(Vertex predecessor) {
        this.predecessor = predecessor;
    }
    
}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

然后，创建一个场景类，并实现和调用 BFS 方法：

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {
        // init data (对照上面题目给的图)
        Vertex[] vertexes = new Vertex[9];
        for (int i = 0; i < vertexes.length; i++) {
            vertexes[i] = new Vertex(i);
        }
        vertexes[0].addNeighbor(vertexes[1], vertexes[3]);
        vertexes[1].addNeighbor(vertexes[0], vertexes[2]);
        vertexes[2].addNeighbor(vertexes[1], vertexes[4], vertexes[5]);
        vertexes[3].addNeighbor(vertexes[0], vertexes[5], vertexes[6]);
        vertexes[4].addNeighbor(vertexes[2], vertexes[8]);
        vertexes[5].addNeighbor(vertexes[2], vertexes[3], vertexes[6], vertexes[8]);
        vertexes[6].addNeighbor(vertexes[3], vertexes[5], vertexes[7]);
        vertexes[7].addNeighbor(vertexes[6], vertexes[8]);
        vertexes[8].addNeighbor(vertexes[4], vertexes[5], vertexes[7]);
        // start search
        Vertex start = vertexes[0];
        Vertex end = vertexes[8];
        boolean hasPath = bfs(start, end);
        if (hasPath) {
            // print path
            Vertex predecessor = end;
            do {
                System.out.print(predecessor.getId() + " -> ");
                predecessor = predecessor.getPredecessor();
            } while (predecessor != null);
        } else {
            System.out.println("不存在该起点到该终点的路径");
        }
    }

    public static boolean bfs(Vertex start, Vertex end) {
        LinkedList<Vertex> queue = new LinkedList<>();
        queue.addLast(start); // 添加到队尾
        while (!queue.isEmpty()) {
            Vertex vertex = queue.pollFirst(); // 从队首取出一个元素
            // 如果这个顶点是否已经检索过了，则跳过
            if (vertex.isSerched()) {
                continue;
            }

            if (vertex == end) {
                // 如果到了终点了就可以返回了
                return true;
            } else {
                // 如果还不是终点，这把该顶点可以到达的邻居全部添加到队列末端
                for (Vertex neighbor : vertex.getNeighbors()) {
                    if (neighbor.getPredecessor() == null && neighbor != start) {
                        neighbor.setPredecessor(vertex);
                    }
                    queue.addLast(neighbor);
                }
            }
            vertex.setSerched(true);
        }
        return false;
    }

}
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

执行结果：

8 -> 5 -> 3 -> 0 -> 
1