BFS 广度优先搜索

图,一种可以表示对象复杂连接关系的数据结构。其较可以其他数据结构而言,可以很方便描述地图、电路、网络等拓扑结构。本文将介绍图的描述方法和基本的图搜索算法——BFS 广度优先搜索

abstract.jpg

定义

图(Graph),是由一组顶点(Vertex)和一组能够将两个顶点相连的边(Edge)所组成。具体地,根据边是否有方向,可划分为有向图、无向图;根据边是否有权重值,可划分为加权图、无加权图。如下图所示,其是一个顶点数V=5、边数E=6的无向无加权图G1(V,E)

figure 1.png

[Note]:

  • 平行边:连接同一对顶点的两条边
  • 自环:一条顶点与自身连接的边

figure 2.png

描述

现已无向无加权图G1(V,E)为例,介绍图的表示方法

1. 邻接矩阵

邻接矩阵Adjacency Matrix,是一个 VxV 矩阵,当元素 a(v,w) 值为1时,即表示顶点v到顶点w之间有一点边。易知,无向图的邻接矩阵是一个对称矩阵;对于加权图而言,邻接矩阵中表示某条边存在的元素 a(v,w) 可设为加权值。无向无加权图G1使用邻接矩阵描述如下:

缺点:

  • 当一个图很大(顶点数很多)而边数较少,此时若用邻接矩阵表示时,其矩阵是一个稀疏矩阵,且矩阵大小为VxV,这将大大浪费存储空间
  • 表示无向图时,由于是对称矩阵,存在冗余,浪费存储空间
  • 无法表示平行边

2.关联矩阵

关联矩阵 Incidence Matrix,是一个 VxE 矩阵,行表示顶点,列表示边。对于一个无向图而言,当某列中有2个元素的值均为1,即表示该边所连接的两个顶点。即,元素 a(v,w)、a(v,k) 值均为1时表示第v条边的两个顶点分别是w和k;对于一个有向图而言,元素 a(v,w)、a(v,k) 值分别为1、-1时,表示第v条边的起点、终点分别是w、k;当某列中,有一个元素的值为2,即可表示该顶点有一个自环;对于一个加权图而言,可以在关联矩阵下方再增加一行,用于表示各边的加权值。无向无加权图G1使用关联矩阵描述如下:

缺点:

  • 获取某个顶点的全部邻接点时,需要遍历图的所有边

3.邻接表

邻接表Adjacency List 是一个以顶点为索引的哈希表,然后该哈希表与每个顶点的邻接点列表相关联。无向无加权图G1使用邻接表描述如下:

figure 3.png

BFS 算法

基本原理

对于图而言,广度优先搜索(BFS) 和 深度优先搜索(DFS) 是两种最基础的图搜索算法,这里介绍前者——BFS。该算法主要用于解决在一个无加权图下找到从起点S至指定点W的最短路径。该算法搜索路径首先从起点S开始,查找距离起点S一条边的顶点集合中是否存在顶点W;若没有则在所有距离起点S两条边的顶点集合中继续查找,直到找到顶点W。BFS算法的搜索图解过程,如下图所示,其过程类似于走迷宫,当走到分岔处,其会自动分裂成多个人,同时向多个分岔去前进搜索;而当多个分岔合并到一处时,亦会变为一个人继续前进搜索

figure 4.png

算法流程

为保证先搜索相同距离长度的路径,该算法使用队列的FIFO特性来保存已经遇到但还未被搜索的分岔路径

  1. 将起点加入队列,并将该顶点状态标记为已搜索;重复Step 2 - 4,直到队列为空
  2. 从队列中取出一个顶点V
  3. 获取顶点V所有的未被搜索过的邻接点列表 toSearchList
  4. 对邻接点列表 toSearchList 中所有顶点执行:加入队列、状态标记为已搜索、记录访问该顶点路径的前驱顶点

Java Demo

现已上文图解的无向图为例,通过Java实现BFS算法

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
/**
* BFS
*/
public class BFS {
public static void BFSDemo() {

Undigraph undigraph = getUndigraph(); // 通过邻接表构造一个无向图
Integer vertexNum = undigraph.getVertexNum(); // 该无向图的顶点数
Integer start = 0; // 指定遍历起点
// BFS结果: 从起点到该点的最短路径上的上一个位置点
// 即 previousVertex[v] = w, 意为 start → ... → w → v
int[] previousVertex = new int[vertexNum];

Boolean status = BFS(undigraph, start, previousVertex);
if( status ) {
visualPath(start, previousVertex);
}
}

/**
* 广度优先遍历
* @param undigraph 图
* @param start 起点
* @return
*/
private static Boolean BFS( Undigraph undigraph, Integer start, int[] previousVertex) {

Integer vertexNum = undigraph.getVertexNum(); // 该无向图的顶点数

Deque<Integer> deque = new LinkedList<>(); // 遍历队列
int[] markArray = new int[vertexNum]; // 访问状态标记数组 0: 未访问, 1: 已访问

// 将起点加入队列中
deque.offer( start );
markArray[start] = 1; // 标记状态为 已访问

while( !deque.isEmpty() ) {
Integer currentVertex = deque.poll(); // 从队列取出一个顶点

// 该点无邻接点
if( !undigraph.getAdjacencyList().containsKey(currentVertex) ) {
return false;
}
// 取出该点的邻接点
List<Integer> adjacencyList = undigraph.getAdjacencyList().get(currentVertex);
for( Integer nextVertex : adjacencyList) {
if( markArray[nextVertex] != 1 ) { // 当前点的邻接点未访问,则进行访问
markArray[nextVertex] = 1; // 标记状态为: 已访问
deque.offer( nextVertex ); // 将邻接点加入队列
previousVertex[nextVertex] = currentVertex; // 记录访问路径
}
}
}
return true;
}

/**
* BFS 结果可视化
* @param start 起点
* @param resultPath BFS结果路径
*/
private static void visualPath(Integer start, int[] resultPath) {
for( int i=0; i<resultPath.length; i++ ) {
List<String> path = new LinkedList<String>();
Integer vertex = i;
while (vertex != start) {
path.add( vertex.toString() );
vertex = resultPath[vertex];
}
path.add(vertex.toString());
Collections.reverse(path);
String pathStr = path.stream().collect( Collectors.joining("->") );
System.out.println(pathStr);
}
}

/**
* 根据邻接表构造无向图
* @return
*/
private static Undigraph getUndigraph() {
Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

adjacencyList.put(0, Arrays.asList(1, 2, 5) );
adjacencyList.put(1, Arrays.asList(0, 2) );
adjacencyList.put(2, Arrays.asList(0, 1, 3, 4) );
adjacencyList.put(3, Arrays.asList(2, 4, 5) );
adjacencyList.put(4, Arrays.asList(2, 3) );
adjacencyList.put(5, Arrays.asList(0, 3) );

Undigraph undigraph = new Undigraph();
undigraph.setAdjacencyList( adjacencyList );
undigraph.setVertexNum( adjacencyList.size() );
return undigraph;
}
}

/**
* 无向图
*/
@Data
class Undigraph {
/**
* 邻接表
*/
private Map<Integer, List<Integer>> adjacencyList;
/**
* 顶点数
*/
private Integer vertexNum;
}

算法结果:

figure 5.png

应用

  • 无加权图的最短路径问题
  • 二分图判定问题

参考文献

  1. 算法(第4版) Robert Sedgewick、Kevin Wayne 著
0%