图是一种表达能力很强的非线性数据结构，因为要表达很多信息，所以他的实现就要比其它的线性数据结构复杂。相应的，图的搜索（查询）就不像之前的线性结构那样简单了，今天在这里我们介绍两种最简单也是最暴力的图的搜索算法：深度优先搜索 和 广度优先搜索。
注：当你的目的不是查找某个数据，而是获取图中所有的数据的时候，可以将这两种搜索算法改造成图的遍历算法，图的遍历也有很多用处，例如使用网络爬虫获取整个互联网的信息。
对于图的搜索算法，最直接的理解就是：在图中从一个顶点出发，找到到达另一个顶点的路径
图的构建
图的搜索算法可以应用在有向图、无向图中，本文使用无向图作为例子讲解，下面是构建一个图的代码：
public class Graph { // 无向图
private int v; // 顶点的个数
private LinkedList<Integer> adj[]; // 邻接表
public Graph(int v) {
this.v = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i) {
adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t) { // 无向图一条边存两次
adj[s].add(t);
adj[t].add(s);
}
}
广度优先搜索（Breadth First Search）
广度优先搜索是一种“地毯式”层层推进的搜索策略，它先查找起始顶点最近的顶点，然后是次近的，依次往外搜索，直到找到期待的数值:
广度优先搜索.jpg
下面是广度优先搜索的代码：
public void bfs(int s, int t) {
if (s == t) return;
boolean[] visited = new boolean[v];
visited[s]=true;
Queue<Integer> queue = new LinkedList<>();
queue.add(s);
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
while (queue.size() != 0) {
int w = queue.poll();
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
if (q == t) {
print(prev, s, t);
return;
}
visited[q] = true;
queue.add(q);
}
}
}
}
private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
if (prev[t] != -1 && t != s) {
print(prev, s, prev[t]);
}
System.out.print(t + " ");
}
在搜索算法中，有三个非常重要的辅助变量，理解这三个变量，基本上就能读懂这段代码了：
- visited：记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
- queue：一个队列，用于存储已经被访问，但是还没有被访问过的相连的顶点。广度优先搜索算法是逐层访问的，所以队列中的元素是按层有序的。
- prev：用来记录搜索路径。当我们从 s 开始，搜索到顶点 t 后，使用 prev 数组中的数据构建搜索路径。比如，我们通过顶点 x 访问到了顶点 y ，那我们就将 prev[y] 设置为 x 。由于 prev 是反向构建的，所以我们需要特殊处理才能打印正确的路径信息，你需要看一下 print( ) 函数的实现方式。
广度优先实例1.jpg
广度优先实例2.jpg
广度优先实例3.jpg
复杂度分析
- 时间复杂度：在最坏情况下，算法要遍历所有的顶点和边，也就是 O(V+E)，其中 V 是顶点的个数，E 是边的个数。如果一个图是连通图，那么 E >= V-1 ，所以，它是时间复杂度也可以简写为 O(E)。
- 空间复杂度：我们需要三个辅助变量辅助计算，而这三个辅助变量使用的空间都不会超过 V，所以空间复杂度为 O(V)。
深度优先搜索（Depth First Search）
深度优先搜索最直观的例子就是走迷宫。
假设你在迷宫的某个岔路口，你不知道走哪条路，那你就随意选择一条路，如果这条路是一条死路，就回退到岔口，换一条路继续走，直到找到出口。
深度优先搜索.jpg
深度优先搜索使用了一个著名的算法思想：回溯思想。这种思想解决问题的过程，非常适合使用递归来实现。
深度优先算法中也使用到了 prev、visted 两个变量以及 print( ) 函数。同时它还使用了一个 found 变量，用于标记是否找到终点 t ，如果 t 以及被找到，我们就不再需要递归查找了：
boolean found = false; // 全局变量或者类成员变量
public void dfs(int s, int t) {
found = false;
boolean[] visited = new boolean[v];
int[] prev = new int[v];
for (int i = 0; i < v; ++i) {
prev[i] = -1;
}
recurDfs(s, t, visited, prev);
print(prev, s, t);
}
private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
if (found == true) return;
visited[w] = true;
if (w == t) {
found = true;
return;
}
for (int i = 0; i < adj[w].size(); ++i) {
int q = adj[w].get(i);
if (!visited[q]) {
prev[q] = w;
recurDfs(q, t, visited, prev);
}
}
}
复杂度分析
- 时间复杂度：从上面画的图可以看出，在这个算法中，每条边最多被访问两次，一次是遍历，一次是回退。所以，时间复杂度是 O(E)，其中 E 是边的个数。
- 空间复杂度：我们需要递归调用栈 和 两个辅助变量，它们的规模不会超过顶点的个数 V ，所以空间复杂度为 O(V)。
总结
- 深度优先搜索 和 广度优先搜索 是两种非常基础也是非常暴力的搜索算法。
- 他们的时间复杂度都是 O(E)，空间复杂度都是 O(V)。
- 广度优先搜索 是一种地毯式的搜索算法。深度优先搜索 利用了回溯思想和递归技巧。
- 思考，我们能否通过广度优先搜索算法实现QQ中推荐“可能认识的人”的功能？
下面是我自己写的图的代码，可以供你参考
import queue
class Graph:
def __init__(self, n):
self.v = [[] for i in range(n)]
def addEdge(self, x, y):
'''
建立一条边
:param x:边的一个顶点
:param y: 边的另一个顶点
:return: None
'''
self.v[x].append(y)
self.v[y].append(x)
def __repr__(self):
return str(self.v)
def dfs(self, s, e):
'''
深度优先搜索
:param s:起始位置
:param e:结束位置
:return:None
'''
visted = [False for i in range(len(self.v))] # 记录每个顶点是否被浏览过
path = [-1 for i in range(len(self.v))] # 记录路径信息
path[s] = s
r = self.recueDfs(s, e, s, visted, path) # 放入递归程序中
print('')
return r
def recueDfs(self, s, e, cur, visted, path):
'''
深度优先搜索会在这里进行递归
:param s: 起始位置
:param e: 结束位置
:param cur: 当前位置
:param visted: 记录顶点是否被浏览过
:param path: 记录路径信息
:return: 寻找完成的路径信息
'''
visted[cur] = True
if cur == e: # 如果当前顶点是终止顶点
self.print_path(path, s, e) # 打印路径
return path
for i in self.v[cur]: # 如不是终点，依次递归该顶点的每个相邻顶点
if visted[i]:
continue
path[i] = cur
res = self.recueDfs(s, e, i, visted, path)
# 如果上一层递归有返回值，代表找到了路径，可以直接 return 跳出；如果递归没有返回值，证明没有找到路径，退出递归函数相当于回退
if res:
return res
def bfs(self, s, e):
'''
广度优先搜索算法
:param s: 起始位置
:param e: 结束位置
:return:寻找完成的路径信息
'''
visted = [False for i in range(len(self.v))] # 记录每个顶点是否被浏览过
visted[s] = True
q = queue.Queue(len(self.v)) # 维护一个队列，用于放置之后要遍历的顶点
q.put(s)
path = [-1 for i in range(len(self.v))] # 记录路径信息
path[s] = s
while q.qsize() != 0: # 队列
w = q.get()
for i in self.v[w]:
if not visted[i]:
path[i] = w
visted[i] = True
q.put(i)
if i == e:
self.print_path(path, s, e)
print('')
return path
def print_path(self, path, s, e):
'''
输出路径信息
:param path: 记录路径信息的数组
:param s: 起始位置
:param e: 结束位置
:return: None
'''
if e == s:
print(e, end='')
return
else:
self.print_path(path, s, path[e])
print('->' + str(e), end='')
if __name__ == '__main__':
g = Graph(6)
g.addEdge(1, 0)
g.addEdge(1, 2)
g.addEdge(1, 3)
g.addEdge(1, 5)
g.addEdge(2, 5)
g.addEdge(3, 5)
g.addEdge(4, 5)
res = g.bfs(0, 4)
print(res)
res = g.dfs(0, 4)
print(res)
以上就是两种图的搜索算法。
注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间
网友评论