数据结构与算法--图的搜索（深度优先和广度优先）
有时候我们需要系统地检查每一个顶点或者每一条边来获取图的各种性质，为此需要从图的某个顶点出发，访遍图中其余顶点，且使得每一个顶点只被访问一次，这个过程就称为图的搜索或者图的遍历。如果限制某个顶点只被访问一次？我们可以建立一个布尔数组，在某个顶点第一次被访问时，将该顶点在数组中对应的下标设置为true。图的搜索通常由两种方案——深度优先搜索和广度优先搜索。
深度优先搜索
深度优先搜索（Depth First Search），简称DFS，该方法主要思想是：
- 从某一个顶点开始，选择一条没有到达过的顶点（布尔数组中对应的值为false）
- 标记刚选择的顶点为“访问过”（布尔数组中对应的值设置为true）
- 来到某个顶点，如果该顶点周围的顶点都访问过了，返回到上个顶点
- 当回退后的顶点依然是上述情况，继续返回
这听起来像是递归。没错，代码确实是递归实现的，并且实现起来特别简单。
package Chap7;
import java.util.Arrays;
import java.util.List;
public class DepthFirstSearch {
// 用来标记已经访问过的顶点，保证每个顶点值访问一次
private boolean[] marked;
// s为搜索的起点
public DepthFirstSearch(UndiGraph<?> graph, int s) {
marked = new boolean[graph.vertexNum()];
dfs(graph, s);
}
private void dfs(UndiGraph<?> graph, int v) {
// 将刚访问到的顶点设置标志
marked[v] = true;
// 打印刚访问的顶点，可换成其他操作
System.out.println(v);
// 从v的所有邻接点中选择一个没有被访问过的顶点
for (int w : graph.adj(v)) {
if (!marked[w]) {
dfs(graph, w);
}
}
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v2", "v3", "v4", "v5");
int[][] edges = {{0, 1}, {0, 2}, {0, 3},
{1, 3}, {1, 4},
{2, 4}};
UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
DepthFirstSearch search = new DepthFirstSearch(graph, 0);
}
}
从代码中看出，深度优先搜索其实就两步：
- 标记访问过的顶点
- 递归地访问当前顶点所有没有被标记过的邻居顶点。
在上面的实现中，我们对访问的每个顶点执行了打印操作。打印只是告诉我们搜索的顺序。不过我们很想知道从某个起点开始到另一个顶点的路径。
为此我们用到了一个edgeTo[]的整型数组，这个数组可以记住每个顶点到起点的路径，而不是记录当前顶点到起点的路径。为了做到这一点在由边v-w第一次访问任意w时，将edgeTo[w]设为v，表示v-w是起点s到w的路径上的最后一条已知的边。比如0-2-3-5，表示从0到5的路径，那么edgeTo[5] = 3。同理如果只是到3的路径，那么edgeTo[3] =2， 到2的路径是edgeTo[2] = 0。这样，我们得到的edgeTo[]其实是一棵根结点为起点的树，而且数组里存的是下标的父结点。就像下图一样。
edgeTo[1]= 2，而结点1的父结点就是结点2；edgeTo[2] = 0，而顶点2的父结点就是结点0，这和树的双亲表示法有点类似。不存在给edge[0]（根结点）赋值的情况，因为此例中我们的起点是顶点0，所以edgeTo[0]保持默认值0。从树中可以看出，起点到顶点5的路径是0-2-3-5。如果我们写一个方法pathTo()，若传入5，只能先获取到edgetTo[5]，得到父结点为3，然后根据edgeTo[3]得到父结点2...一直到获取到根结点，可以看到获取的顺序是从叶子结点到根结点，但是真正输出路径的时候是从根结点到叶子结点，所以利用栈（Stack）可以实现这一过程。稍微想一下，先入栈的5被排在了底下，最后入栈的0排在了最顶上，确实是这样的。
现在来实现。
package Chap7;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class DepthFirstSearch {
// 用来标记已经访问过的顶点，保证每个顶点值访问一次
private boolean[] marked;
// 起点
private final int s;
// 到该顶点的路径上的最后一条边
private int[] edgeTo;
public DepthFirstSearch(UndiGraph<?> graph, int s) {
this.s = s;
marked = new boolean[graph.vertexNum()];
edgeTo = new int[graph.vertexNum()];
dfs(graph, s);
}
private void dfs(UndiGraph<?> graph, int v) {
// 将刚访问到的顶点设置标志
marked[v] = true;
// System.out.println(v);
// 从v的所有邻接点中选择一个没有被访问过的顶点
for (int w : graph.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(graph, w);
}
}
}
// 连通图的任意一个顶点都有某条路径能到达任意一个顶点，如果v在这个连通图中，必然存在起点到v的路径
// 现在marked数组中的值都是true，所以数组中若有这个v（在这个连通图中）, 返回true就表示路径存在
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
LinkedList<Integer> path = new LinkedList<>();
for (int i = v; i != s; i = edgeTo[i]) {
path.push(i);
}
// 最后将根结点压入
path.push(s);
return path;
}
// 到v不存在路径，就返回null
return null;
}
public void printPathTo(int v) {
System.out.print(s+" to "+ v+": ");
if (hasPathTo(v)) {
for (int i : pathTo(v)) {
if (i == s) {
System.out.print(i);
} else {
System.out.print("-" + i);
}
}
System.out.println();
} else {
System.out.println("不存在路径！");
}
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4", "v5");
int[][] edges = {{3, 5},{0, 2}, {0, 1}, {0, 5},
{1, 2}, {3, 4}, {2, 3}, {2, 4}};
UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
DepthFirstSearch search = new DepthFirstSearch(graph, 0);
search.printPathTo(4);
}
}
/* Output
0 to 5: 0-2-3-5
*/
只是在深度优先搜索的实现中新加了一些东西，最重要的是在dfs递归方法中插入了一行edgeTo[w] = v;，我们知道w是v的一个邻接点，那么这行的字面意思就是到w的顶点是v，即路径v-w。上面提到过这是起点s到w的最后一条边。
扩展的方法hasPathTo用来判断是否有到某顶点的路径，由于这是连通图，任意一个顶点（包括起点s）都有某条路径能到达任意一个顶点，在初始化该类时，已经调用过深度优先搜索，所以marked数组里都是true，这意味着只要某个顶点能在marked数组中找到对应的下标，那么返回true，表示肯定存在到它的路径。
我们的pathTo用来确定一条从起点到指定顶点的路径，注意这条路径不一定是最短的，也可能并非是唯一路径。必须先判断是否存在到该指定顶点的路径，如果不存在则返回null；若存在，则从查找的顶点开始入栈，i = edgeTo[i]表示树向上一层，更新当前值为结点i的父结点，直到根结点停止，由条件i != s可知，根结点并没有入栈，所以在循环之后要将根结点入栈。
printPathTo就是将pathTo返回的内容格式化输出，就像这样。表示顶点0到顶点5的路径是0-2-3-5。
0 to 5: 0-2-3-5
可见这路径并不是最短路径，0-5直接可达才是最短的。
现在我们来看下深度优先搜索的详细轨迹，注意对照着上图的邻接表：先是从起点0开始
- 因为2是0的邻接表第一个元素且没有被标记访问，则递归调用它并标记。
edgeTo[2] = 0表示0-2这条路径。 - 现在顶点0是顶点2的邻接表第一个元素，但是0已经被标记了，所以跳过它，看下一个。1没有被标记，所以递归调用它，并标记。
edgeTo[1] = 2，表示0-2-1这条路径。 - 顶点1的邻接表元素都被标记过了，所以不再递归，方法从
dfs(1)中返回到上一个顶点2，现在检查2的下一个邻接顶点，3没被标记所以递归它并标记，edgeTo[3] = 2表示0-2-3这条路径。 - 顶点5是3的邻接表第一个元素没被标记，递归调用它并标记，
edgeTo[5] = 3表示0-2-3-5这条路径。 - 顶点5的邻接表元素都被标记过了，方法从
dfs (5)中返回到带上一个顶点3，检查3的邻接表下一个元素，4没有被标记，所以递归它并标记，edgeTo[4] = 3表示0-2-3-4。至此，所有顶点都被标记过。搜索算是完成了。
DFS的非递归版本
DFS也可以自己设一个栈模拟系统栈，下面是非递归版本。
/**
* 非递归实现DFS
*
* @param graph 图
* @param s 起点
*/
public void dfs(UndiGraph<?> graph, int s) {
boolean[] marked = new boolean[graph.vertexNum()];
// 模拟系统栈
LinkedList<Integer> stack = new LinkedList<>();
// 起点先入栈
stack.push(s);
// 标记访问
marked[s] = true;
System.out.print(s);
while (!stack.isEmpty()) {
// 取出刚访问的顶点
int v = stack.peek();
for (int w : graph.adj(v)) {
if (!marked[w]) {
marked[w] = true;
System.out.print(w);
stack.push(w);
// 模拟DFS只存入一个就好，一定要break
break;
}
}
// 所有邻接点都被访问过了，模拟递归的返回
stack.pop();
}
}
广度优先搜索
深度优先搜索得到的路径上面已经看到，并不是最短路径，很自然地我们对下面的问题感到兴趣：单点最短路径，即给定一个图和一个起点s，是否存在到给定顶点v的一条路径，如果有找出最短的那条。
解决这个问题方法是广度优先搜索（Breadth First Search），简称BFS。
这个算法的思想大体是：
- 从起点开始，标记之并加入队列。
- 起点出列，其所有未被标记的邻接点在被标记后，入列。
- 队列头的元素出列，将该元素的所有未被标记的邻接点标记后，入列。
如此反复，当队列为空时，所有顶点也都被标记过了。不像DFS的递归那样隐式地使用栈（系统管理的，以支持递归），BFS使用了队列。
package Chap7;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class BreadthFirstSearch {
// 用来标记已经访问过的顶点，保证每个顶点值访问一次
private boolean[] marked;
// 起点
private final int s;
// 到该顶点的路径上的最后一条边
private int[] edgeTo;
public BreadthFirstSearch(UndiGraph<?> graph, int s) {
this.s = s;
marked = new boolean[graph.vertexNum()];
edgeTo = new int[graph.vertexNum()];
bfs(graph, s);
}
public void bfs(UndiGraph<?> graph, int s) {
marked[s] = true;
// offer入列, poll出列
Queue<Integer> queue = new LinkedList<>();
queue.offer(s);
while (!queue.isEmpty()) {
int v = queue.poll();
// System.out.print(v+" ");
for (int w: graph.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
queue.offer(w);
}
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (hasPathTo(v)) {
LinkedList<Integer> path = new LinkedList<>();
for (int i = v; i != s; i = edgeTo[i]) {
path.push(i);
}
// 最后将根结点压入
path.push(s);
return path;
}
// 到v不存在路径，就返回null
return null;
}
public void printPathTo(int v) {
System.out.print(s+" to "+ v+": ");
if (hasPathTo(v)) {
for (int i : pathTo(v)) {
if (i == s) {
System.out.print(i);
} else {
System.out.print("-" + i);
}
}
System.out.println();
} else {
System.out.println("不存在路径！");
}
}
public static void main(String[] args) {
List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4", "v5");
int[][] edges = {{3, 5},{0, 2}, {0, 1}, {0, 5},
{1, 2}, {3, 4}, {2, 3}, {2, 4}};
UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
BreadthFirstSearch search = new BreadthFirstSearch(graph, 0);
search.printPathTo(5);
}
}
/* Output
0 to 5: 0-5
*/
我把打印操作注释了，实际上它会输出如下内容
0 2 1 5 3 4
先是打印了起点，然后依次打印了0的所有邻接点2、1、5，之后按照队列的出列顺序，打印2的所有未被标记的邻接点，实际上这已经打印完了所有顶点。而且从代码里也能看出，不像DFS那样每次只标记一个顶点，BFS每次都标记了若干顶点。
上面的代码中，除了bfs的实现代码，其余有关path的方法可以直接使用DFS中的实现。还是来看下详细的搜索轨迹。
- 首先顶点0入列
- 顶点0出列，将它所有邻接点2、1、5（参考DFS中的邻接表图片），标记他们。且
edgeTo[2]、edgeTo[1]、edgeTo[5]的值都设为0 - 顶点2出列，检查它的邻接点，0、1已经被标记，于是将3、4入列，并标记它们。
edgeTo[3]、edgeTo[4]的值都设为2 - 顶点1出列，其邻接点均已被标记
- 顶点5出列，其邻接点均已被标记
- 顶点3出列，其邻接点均已被标记
- 顶点4出列，其邻接点均已被标记
可以发现，实际上标记工作和edgeTo数组在第三步之后就已经完成，之后的工作只是检查出列的顶点的邻接点是否被标记过而已。
我们不妨打印下起点到其余各个顶点的路径
0 to 5: 0-5
0 to 4: 0-2-4
0 to 3: 0-2-3
0 to 2: 0-2
0 to 1: 0-1
不难发现，这些路径都是最短路径。实际上有这么一个命题：对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径。
广度优先搜索是先覆盖起点附近的顶点，只在邻近的所有顶点都被访问后才向前进，其搜索路径短而直接；而深度优先搜索是寻找离起点更远的顶点，只有在碰到周围的邻接点都被访问过了才往回退，选一个近处的顶点，继续深入到更远的地方，其路径长而曲折。
以上深度优先和广度优先的实现对于有向图也是适用的，把接收的参数的换成有向图即可。
by @sunhaiyu
2017.9.19
