算法复习 (三) 图-无向图(未完成)

算法复习 (三) 图-无向图

一. 图

1.1 应用场景

  • 地图。正在计划旅行的人也许想知道“从普罗维登斯到普林斯顿的最短路线”。对最短路径上经历过交通堵塞的旅行者可能会问:“从普罗维登斯到普林斯顿的哪条路线最快?”要回答这些问题,我们都要处理有关结点(十字路口)之间多条连接(公路)的信息。
  • 网页信息。当我们在浏览网页时,页面上都会包含其他网页的引用(链接)。通过单击链接,我们可以从一个页面跳到另一个页面。整个互联网就是一张图,结点是网页,连接就是超链接。图算法是帮助我们在网络上定位信息的搜索引擎的关键组件。
  • 电路。在一块电路板上,晶体管、电阻、电容等各种元件是精密连接在一起的。我们使用计算机来控制制造电路板的机器并检查电路板的功能是否正常。我们既要检查短路这类简单问题,也要检查这幅电路图中的导线在蚀刻到芯片上时是否会出现交叉等复杂问题。第一类问题的答案仅取决于连接(导线)的属性,而第二个问题则会涉及导线、各种元件
    以及芯片的物理特性等详细信息。
  • 任务调度。商品的生产过程包含了许多工序以及一些限制条件,这些条件会决定某些任务的先后次序。如何安排才能在满足限制条件的情况下用最少的时间完成这些生产工序呢?
    商业交易。零售商和金融机构都会跟踪市场中的买卖信息。在这种情形下,一条连接可以表示现金和商品在买方和卖方之间的转移。在此情况下,理解图的连接结构原理可能有助于增强人们对市场的理解。
  • 配对。学生可以申请加入各种机构,例如社交俱乐部、大学或是医学院等。这里结点就对应学生和机构,而连接则对应递交的申请。我们希望找到申请者与他们感兴趣的空位之间配对的方法。
  • 计算机网络。计算机网络是由能够发送、转发和接收各种消息的站点互相连接组成的。我们感兴趣的是这种互联结构的性质,因为我们希望网络中的线路和交换设备能够高效率地处理网络流量。
  • 软件。编译器会使用图来表示大型软件系统中各个模块之间的关系。图中的结点即构成整个系统的各种类和模块,连接则为类的方法之间的可能调用关系(静态分析),或是系统运行时的实际调用关系(动态分析)。我们需要分析这幅图来决定如何以最优的方式为程序分配资源。
  • 社交网络。当你在使用社交网站时,会和你的朋友之间建立起明确的关系。这里,结点对应人而连接则联系着你和你的朋友或是关注者。分析这些社交网络的性质是当前图算法的一个重要应用。对它感兴趣的不止是社交网络的公司,还包括政治、外交、娱乐、教育、市场等许多其他机构。
应用 结点 连接
地图 十字路口 公路
网络内容 网页 超链接
电路 元器件 导线
任务调度 任务 限制条件
商业交易 客户 交易
配对 学生 申请
计算机网络 网站 物理连接
软件 方法 调用关系
社交网络 友谊关系

1.2 常用术语

  • 某个顶点的度数即为依附于它的边的总数。
  • 子图是由一幅图的所有边的一个子集(以及它们所依附的所有顶点)组成的图。许多计算问题都需要识别各种类型的子图,特别是由能够顺序连接一系列顶点的边所组成的子图。
  • 路径是由边顺序连接的一系列顶点。
  • 简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。
  • 简单环是一条(除了起点和终点必须相同之外)不含有重复顶点和边的环。
  • 路径或者环的长度为其中所包含的边数。
  • 当两个顶点之间存在一条连接双方的路径时,我们称一个顶点和另一个顶点是连通的。
  • 如果从任意一个顶点都存在一条路径到达另一个任意顶点,我们称这幅图是连通图。一幅非连通的图由若干连通的部分组成,它们都是其极大连通子图。
  • 无环图是一种不包含环的图。
  • 图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中,被连接的顶点对很少;而在稠密图中,只有少部分顶点对之间没有边连接。
  • 二分图是一种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点都分别属于不同的部分。

1.3 图与树的关系

树是一幅无环连通图。互不相连的树组成的集合称为森林。连通图的生成树是它的一幅子图,它含有图中的所有顶点且是一棵树。图的生成树森林是它的所有连通子图的生成树的集合。

当且仅当一幅含有V个结点的图满足下列 5 个条件之一时,它就是一棵树:

  • G有V-1条边且不含有环;
  • G有V-1条边且是连通的;
  • G是连通的,但删除任意一条边都会使它不再连通;
  • G是无环图,但添加任意一条边都会产生一条环;
  • G中的任意一对顶点之间仅存在一条简单路径。

1.4 四种图模型

4 种最重要的图模型:

  • 无向图(简单连接)
  • 有向图(连接有方向性)
  • 加权图(连接带有权值)
  • 加权有向图(连接既有方向性又带有权值)

二. 无向图

(1)概念

定义:图是由一组顶点和一组能够将两个顶点相连的边组成的。

一般使用 0 至 V-1 来表示一张含有 V 个顶点的图中的各个顶
点。用 v-w 的记法来表示连接 v 和 w 的边,w-v 是这条边的另一种表示方法。

绘制出的图有时会误导我们,因为图的定义和绘出的图像是无关的。

特殊的图。我们的定义允许出现两种简单而特殊的情况:

  • 自环,即一条连接一个顶点和其自身的边;
  • 连接同一对顶点的两条边称为平行边。

数学家常常将含有平行边的图称为多重图,而将没有平行边或自环的图称为简单图。后续不会出现这种特殊情况,所以用两个顶点就可以指代一条边了。

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
public class Bag<Item> implements Iterable<Item> {
private Node first; // 链表的首结点

private class Node {
Item item;
Node next;
}

public void add(Item item) { // 和Stack 的push() 方法完全相同
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}

public Iterator<Item> iterator() {
return new ListIterator();
}

private class ListIterator implements Iterator<Item> {
private Node current = first;

public boolean hasNext() {
return current != null;
}

public void remove() {
}

public Item next() {
Item item = current.item;
current = current.next;
return item;
}
}
}
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
public class Graph {
private final int V; // 顶点数目
private int E; // 边的数目
private Bag<Integer>[] adj; // 邻接表:数组+链表

public Graph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V]; // 创建邻接表
for (int v = 0; v < V; v++) // 将所有链表初始化为空
adj[v] = new Bag<Integer>();
}

public Graph(In in) {
this(in.readInt()); // 读取V并将图初始化
int E = in.readInt(); // 读取E
for (int i = 0; i < E; i++) { // 添加一条边
int v = in.readInt(); // 读取一个顶点
int w = in.readInt(); // 读取另一个顶点
addEdge(v, w); // 添加一条连接它们的边
}
}

public int V() {
return V;
}

public int E() {
return E;
}

public void addEdge(int v, int w) {
adj[v].add(w); // 将w添加到v的链表中
adj[w].add(v); // 将v添加到w的链表中
E++;
}

public Iterable<Integer> adj(int v) {
return adj[v];
}
}

三. 深度优先搜索

3.1 什么是深度优先搜索?

深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的递归算法,它会沿着图的边寻找和起点连通的所有顶点。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的拓扑排序,利用拓扑排序表可以方便的解决很多相关的图论问题,如无权最长路径问题等等。这种算法不会根据图的结构等信息调整执行策略来源请求。

3.2 迷宫问题和 Tremaux 搜索

思考图的搜索过程的一种有益的方法是,考虑另一个和它等价的问题:在一个由各种通道和路口组成的迷宫中找到出路。有些迷宫的规则很简单,但大多数迷宫则需要很复杂的策略才行。

用迷宫代替图、通道代替边、路口代替顶点仅仅只是一些文字游戏,但就目前来说,这么做可以帮助我们直观地认识问题,参见下图:

探索迷宫而不迷路的一种古老办法(至少可以追溯到忒修斯和米诺陶的传说)叫做 Tremaux 搜索,参见下图:

要探索迷宫中的所有通道,我们需要:

  • 选择一条没有标记过的通道,在你走过的路上铺一条绳子;
  • 标记所有你第一次路过的路口和通道;
  • 当来到一个标记过的路口时(用绳子)回退到上个路口;
  • 当回退到的路口已没有可走的通道时继续回退。

绳子可以保证你总能找到一条出路,标记则能保证你不会两次经过同一条通道或者同一个路口。要知道是否完全探索了整个迷宫需要的证明更复杂,只有用图搜索才能够更好地处理问题。

Tremaux 搜索很直接,但它与完全搜索一张图仍然稍有不同,因此我们接下来看看图的搜索方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class DepthFirstSearch {
private boolean[] marked;
private int count;

public DepthFirstSearch(Graph G, int s) {
marked = new boolean[G.V()];
dfs(G, s);
}

private void dfs(Graph G, int v) {
marked[v] = true;
count++;
for (int w : G.adj(v))
if (!marked[w]) dfs(G, w);
}

public boolean marked(int w) {
return marked[w];
}

public int count() {
return count;
}
}

3.3 算法描述

搜索连通图的经典递归算法深度优先搜索(遍历所有的顶点和边)和 Tremaux 搜索类似。要搜索一幅图,只需用一个递归方法来遍历所有顶点。深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比

在访问其中一个顶点时:

  • 将它标记为已访问;
  • 递归地访问它的所有没有被标记过的邻居顶点。

它使用一个 boolean 数组来记录和起点连通的所有顶点。递归方法会标记给定的顶点并调用自己来访问该顶点的相邻顶点列表中所有没有被标记过的顶点。如果图是连通的,每个邻接链表中的元素都会被检查到。

算法遍历边和访问顶点的顺序与图的表示是有关的,而不只是与图的结构或是算法有关。因为深度优先搜索只会访问和起点连通的顶点,使用下图所示的一幅小型连通图为例,一幅连通的无向图:

  • 在示例中,顶点 2 是顶点 0 之后第一个被访问的顶点,因为它正好是 0 的邻接表的第一个元素。
  • 深度优先搜索中每条边都会被访问两次,且在第二次时总会发现这个顶点已经被标记过。这意味着深度优先搜索的轨迹可能会比你想象的长一倍!示例图仅含有 8 条边,但需要追踪算法在邻接表的 16 个元素上的操作。

下图显示的是示例中每个顶点被标记后算法使用的数据结构,起点为顶点 0。使用深度优先搜索的轨迹,寻找所有和顶点 0 连通的顶点:

查找开始于构造函数调用递归的 dfs() 来标记和访问顶点0,后续处理如下所述:

  • 因为顶点 2 是 0 的邻接表的第一个元素且没有被标记过,dfs() 递归调用自己来标记并访问顶点 2(效果是系统会将顶点 0 和 0 的邻接表的当前位置压入栈中)。
  • 现在,顶点 0 是 2 的邻接表的第一个元素且已经被标记过了,因此 dfs() 跳过了它。接下来,顶点 1 是 2 的邻接表的第二个元素且没有被标记,dfs() 递归调用自己来标记并访问顶点 1。
  • 对顶点 1 的访问和前面有所不同:因为它的邻接表中的所有顶点(0 和 2)都已经被标记过了,因此不需要再进行递归,方法从 dfs(1) 中返回。下一条被检查的边是 2-3(在 2 的邻接表中顶点 1 之后的顶点是 3),因此 dfs() 递归调用自己来标记并访问顶点3。
  • 顶点 5 是 3 的邻接表的第一个元素且没有被标记,因此 dfs() 递归调用自己来标记并访问顶点 5。
  • 顶点 5 的邻接表中的所有顶点(3 和 0)都已经被标记过了,因此不需要再进行递归。
  • 顶点 4 是 3 的邻接表的下一个元素且没有被标记过,因此 dfs() 递归调用自己来标记并访问顶点 4。这是最后一个需要被标记的顶点。
  • 在顶点 4 被标记了之后,dfs() 会检查它的邻接表,然后再检查 3 的邻接表,然后是 2 的邻接表,然后是 0 的,最后发现不需要再进行任何递归调用,因为所有的顶点都已经被标记过了。

3.4 使用场景

  • 连通性问题 / 路径检测问题 :比如给定一幅图,回答“两个给定的顶点是否连通?”或者“图中有多少个连通子图?”等类似问题。问题“两个给定的顶点是否连通?”等价于“两个给定的顶点之间是否存在一条路径?”
  • 单点路径:给定一幅图和一个起点 s,回答“从 s 到给定目的顶点 v 是否存在一条路径?如果有,找出这条路径。”等类似问题。

深度优先搜索算法之所以极为简单,是因为它所基于的概念为人所熟知并且非常容易实现。事实上,它是一个既小巧而又强大的算法,研究人员用它解决了无数困难的问题。上述两个问题只是我们将要研究的许多问题的开始。

3.5 算法题

剑指第12题-矩阵中的路径:深度优先搜索

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
/**
* 矩阵中的路径
*
* 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
* 路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。
* 如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。
* 例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。
*
* [["a","b","c","e"],
* ["s","f","c","s"],
* ["a","d","e","e"]]
*
* 但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。
*
*
*
* 示例 1:
*
* 输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
* 输出:true
* 示例 2:
*
* 输入:board = [["a","b"],["c","d"]], word = "abcd"
* 输出:false
* 提示:
*
* 1 <= board.length <= 200
* 1 <= board[i].length <= 200
*
* Related Topics
* 深度优先搜索
*
*/
public class Jz12Exist {

public static void main(String[] args) {
char[][] board = {
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
String word = "ABCCED";
System.out.println(exist(board, word));
char[][] board1 = {{'a', 'b'}, {'c', 'd'}};
String word1 = "abcd";
System.out.println(exist(board1, word1));
}

/**
* 时间复杂度 O(3^K * M * N) :
* 最差情况下,需要遍历矩阵中长度为 K 字符串的所有方案,时间复杂度为 O(3^K);
* 矩阵中共有 MN 个起点,时间复杂度为 O(MN) 。
* 方案数计算: 设字符串长度为 K ,搜索中每个字符有上、下、左、右四个方向可以选择,舍弃回头(上个字符)的方向,剩下 3 种选择,因此方案数的复杂度为 O(3^K) 。
* 空间复杂度 O(K) :
* 搜索过程中的递归深度不超过 K ,因此系统因函数调用累计使用的栈空间占用 O(K)
* (因为函数返回后,系统调用的栈空间会释放)。
* 最坏情况下 K = MN ,递归深度为 MN ,此时系统栈使用 O(MN) 的额外空间。
*/
public static boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) {
return true;
}
}
}
return false;
}

/**
* 深度优先搜索
* @param board 二维矩阵
* @param word 单词
* @param i 横坐标
* @param j 纵坐标
* @param k 单词坐标
* @return 是否命中
*/
public static boolean dfs(char[][] board, char[] word, int i, int j, int k) {
// 未命中:横纵坐标越界,矩阵对应位置元素不等于单词对应位置元素
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) {
return false;
}
// 单词遍历结束,全部命中
if (k == word.length - 1) {
return true;
}

// 标记表示已访问过
board[i][j] = '\0';
// 递归访问相邻矩阵元素
boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
board[i][j] = word[k];
return res;
}
}

剑指第13题-机器人的运动范围:深度优先搜索

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
/**
* 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。
* 一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),
* 也不能进入行坐标和列坐标的数位之和大于k的格子。
* 例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。
* 但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
*
*
* 示例 1:
*
* 输入:m = 2, n = 3, k = 1
* 输出:3
* 示例 2:
*
* 输入:m = 3, n = 1, k = 0
* 输出:1
* 提示:
*
* 1 <= n,m <= 100
* 0 <= k <= 20
*/
public class Jz13MovingCount {

public static void main(String[] args) {
int m = 2, n = 3, k = 1;
System.out.println(movingCount(m, n , k));
m = 3;
n = 1;
k = 0;
System.out.println(movingCount(m, n , k));
m = 16;
n = 8;
k = 4;
System.out.println(movingCount(m, n , k));
}

/**
* 深度优先搜索
*
* 时间复杂度:O(mn),其中 m 为方格的行数, n 为方格的列数。
* 一共有 O(mn) 个状态需要计算,每个状态递推计算的时间复杂度为 O(1),所以总时间复杂度为 O(mn)。
*
* 空间复杂度:O(mn),其中 m 为方格的行数,n 为方格的列数。我们需要 O(mn) 大小的结构来记录每个位置是否可达。
*
*/
public static int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfs(0, 0, m, n, k, visited);
}

public static int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
if(i >= m || j >= n || k < getSum(i) + getSum(j) || visited[i][j]) {
return 0;
}
visited[i][j] = true;
return 1 + dfs(i + 1, j, m, n, k, visited) + dfs(i, j + 1, m, n, k, visited);
}

private static int getSum(int a) {
int sum = a % 10;
int tmp = a / 10;
while(tmp > 0) {
sum += tmp % 10;
tmp /= 10;
}
return sum;
}
}

四. 寻找路径

4.1 路径API

测试用例:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
Graph G = new Graph(new In(args[0]));
int s = Integer.parseInt(args[1]);
Paths search = new Paths(G, s);
for (int v = 0; v < G.V(); v++) {
StdOut.print(s + " to " + v + ": ");
if (search.hasPathTo(v))
for (int x : search.pathTo(v))
if (x == s) StdOut.print(x);
else StdOut.print("-" + x);
StdOut.println();
}
}

4.2 实现

DepthFirstPaths使用深度优先搜索查找图中的路径:

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
/**
* 使用深度优先搜索查找图中的路径
*/
public class DepthFirstPaths {

/**
* 在此顶点上是否调用过 dfs()
*/
private boolean[] marked;

/**
* 从起点到一个顶点的已知路径上的最后一个顶点
*/
private int[] edgeTo;

/**
* 起点
*/
private final int s;

/**
* 在 G 中找出所有起点为 s 的路径
*/
public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}

private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(G, w);
}
}
}

/**
* 是否存在从 s 到 v 的路径
*/
public boolean hasPathTo(int v) {
return marked[v];
}

/**
* s 到 v 的路径,如果不存在则返回 null
*/
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}

计算轨迹如下:

为了保存到达每个顶点的已知路径,这段代码使用了一个以顶点编号为索引的数组 edgeTo[],edgeTo[w]=v 表示 v-w 是第一次访问 w 时经过的边。edgeTo[] 数组是一棵用父链接表示的以 s 为根且含有所有与 s 连通的顶点的树。

下图显示的是示例中每个顶点被标记后 edgeTo[] 的内容,起点为顶点 0。marked[] 和 adj[] 的内容与 DepthFirstSearch 的轨迹相同,递归调用和边检查的详细描述也完全一样,这里不再赘述。深度优先搜索向 edgeTo[] 数组中顺序添加了 0-2、2-1、2-3、3-5 和 3-4。这些边构成了一棵以起点为根结点的树并提供了 pathTo() 方法所需的信息,使得调用者可以按照前文所述的方法找到从 0 到顶点 1、2、3、4、5 的路径。

五. 广度优先搜索

5.1 什么是广度优先搜索?

广度优先搜索算法(Breadth-First Search,BFS)

单点最短路径。给定一幅图和一个起点 s,回答“从 s 到给定目的顶点 v 是否存在一条路径?如果有,找出其中最短的那条(所含边数最少)。”等类似问题。

解决这个问题的经典方法叫做广度优先搜索(BFS)。深度优先搜索在这个问题上没有什么作为,因为它遍历整个图的顺序和找出最短路径的目标没有任何关系。相比之下,广度优先搜索正是为了这个目标才出现的。

要找到从 s 到 v 的最短路径,从 s 开始,在所有由一条边就可以到达的顶点中寻找 v,如果找不到我们就继续在与 s 距离两条边的所有顶点中查找v,如此一直进行。深度优先搜索就好像是一个人在走迷宫,广度优先搜索则好像是一组人在一起朝各个方向走这座迷宫,每个人都有自己的绳子。当出现新的叉路时,可以假设一个探索者可以分裂为更多的人来搜索它们,当两个探索者相遇时,会合二为一(并继续使用先到达者的绳子),参见下图-广度优先的迷宫搜索。

5.2 算法描述

在深度优先搜索中,我们用了一个可以下压的栈(这是由系统管理的,以支持递归搜索方法)。使用 LIFO(后进先出)的规则来描述压栈和走迷宫时先探索相邻的通道类似。从有待搜索的通道中选择最晚遇到过的那条。在广度优先搜索中,我们希望按照与起点的距离的顺序来遍历所有顶点,看起来这种顺序很容易实现:使用(FIFO,先进先出)队列来代替栈(LIFO,后进先出)即可。我们将从有待搜索的通道中选择最早遇到的那条。

算法 4.2 实现了广度优先搜索算法。它使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将起点加入队列,然后重复以下步骤直到队列为空:

  • 取队列中的下一个顶点 v 并标记它;
  • 将与 v 相邻的所有未被标记过的顶点加入队列。

步骤:

  • 从队列中删去顶点 0 并将它的相邻顶点 2、1 和 5 加入队列中,标记它们并分别将它们在 edgeTo[] 中的值设为 0。
  • 从队列中删去顶点 2 并检查它的相邻顶点 0 和 1,发现两者都已经被标记。将相邻的顶点 3 和 4 加入队列,标记它们并分别将它们在 edgeTo[] 中的值设为 2。
  • 从队列中删去顶点 1 并检查它的相邻顶点 0 和 2,发现它们都已经被标记了。
  • 从队列中删去顶点 5 并检查它的相邻顶点 3 和 0,发现它们都已经被标记了。
  • 从队列中删去顶点 3 并检查它的相邻顶点 5、4 和 2,发现它们都已经被标记了。
  • 从队列中删去顶点 4 并检查它的相邻顶点 3 和 2,发现它们都已经被标记了。
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
/**
* 使用广度优先搜索查找图中的路径
*/
public class BreadthFirstPaths {

/**
* 到达该顶点的最短路径是否已知
*/
private boolean[] marked;

/**
* 到达该顶点的已知路径上的最后一个顶点
*/
private int[] edgeTo;

/**
* 起点
*/
private final int s;

public BreadthFirstPaths(Graph G, int s)
{
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G, s);
}

private void bfs(Graph G, int s) {
Queue<Integer> queue = new Queue<>();
// 标记起点
marked[s] = true;
// 将它加入队列
queue.enqueue(s);
while (!queue.isEmpty()) {
// 从队列中删去下一顶点
int v = queue.dequeue();
for (int w : G.adj(v)) {
// 对于每个未被标记的相邻顶点
if (!marked[w]) {
// 保存最短路径的最后一条边
edgeTo[w] = v;
// 标记它,因为最短路径已知
marked[w] = true;
// 并将它添加到队列中
queue.enqueue(w);
}
}
}
}

public boolean hasPathTo(int v) { return marked[v]; }

public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}

5.3 使用场景

六. 连通分量


参考:

🔗 《算法-第4版》