广度优先搜索（BFS）

图的广度优先搜索(Broad First Search) 。类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点

广度优先遍历算法步骤

  1. 访问初始结点v并标记结点v为已访问。
  2. 结点v入队列
  3. 当队列非空时，继续执行，否则算法结束。
  4. 出队列，取得队头结点u。
  5. 查找结点u的第一个邻接结点w。
  6. 若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
    1. 若结点w尚未被访问，则访问结点w并标记为已访问。
    2. 结点w入队列
    3. 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

广度优先搜索抽象图解

image-20241114115852877

代码实现

Graph

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
package com.yukinoshita.dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;
    //记录某个顶点是否被访问过
    private boolean[] vis;

    public static void main(String[] args) {

        int n = 5;
        String Vertexs[] = {"A", "B", "C", "D", "E"};
        Graph graph = new Graph(n);
        for (String vertex : Vertexs) {
            graph.insertVertex(vertex);
        }
        //添加边
        //A-B A-C B-C B-D B-E
        graph.insertEdge(0, 1, 1); // A-B
        graph.insertEdge(0, 2, 1); //
        graph.insertEdge(1, 2, 1); //
        graph.insertEdge(1, 3, 1); //
        graph.insertEdge(1, 4, 1); //
        graph.showGraph();

        graph.bfs();
    }

    //遍历所有节点（确保所有点都被访问）
    public void bfs(){
        for(int i=0;i<getNumOfVertex();i++){
            if(!vis[i]){
                bfs(vis,i);
            }
        }
    }

    //对一个结点进行广度优先遍历的方法
    private void bfs(boolean[] vis, int i) {
        int u;//表示队列的头节点对应下标
        int w;//邻接节点w
        //队列，记录结点访问的顺序
        LinkedList queue = new LinkedList();
        //访问结点，输出结点信息
        System.out.print(getValueByIndex(i) + "=>");
        //标记为已访问
        vis[i] = true;
        //将这个结点加入队列
        queue.addLast(i);

        while (!queue.isEmpty()) {
            //取出队列的头节点下标
            u = (Integer) queue.removeFirst();
            //得到第一个邻接节点的下标
            w = getFirstNeighbor(u);
            while (w != -1) {//找到
                if (!vis[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    vis[w] = true;
                    queue.addLast(w);
                }
                //以u为前驱，找w后面的下一个邻接节点
                w = getNextNeighbor(u, w);
            }

        }
    }

    /**
     * （？存疑）根据前一个邻接节点的下标来获取下一个邻接节点
     *
     * @param v1 上一个节点的行号
     * @param v2 上一个节点的列号
     * @return 下一个节点在vertexList的下标j，没有则-1
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 得到第一个邻接节点的下标
     *
     * @param index
     * @return 下一个邻接节点的下标，没有则-1
     */
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }


    //构造器
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
        vis = new boolean[n];
    }

    //获取顶点数量
    public int getNumOfVertex() {
        return vertexList.size();
    }

    //展示图
    public void showGraph() {
        for (int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }

    //获取边的数量
    public int getNumOfEdges() {
        return numOfEdges;
    }

    //获取顶点的值
    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }

    //获取权值
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    //插入顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }

    //插入边
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}