数据结构（九）：广度优先与深度优先
?
广度优先搜索(breadth-first search)和深度优先搜索(depth-first search)是两种探索图/树中顶点的思路。这两种搜索方式可以用来查找图中某个指定的顶点，也可以用来对图中顶点进行遍历。
广度优先方式
广度优先遍历图的方式为，一次性访问当前顶点的所有未访问状态相邻顶点，并依次对每个相邻顶点执行同样处理。因为要依次对每个相邻顶点执行同样的广度优先访问操作，所以需要借助队列结构来存储当前顶点的相邻顶点。
广度优先遍历图的方式，是以一种类似波纹扩散的方式进行的，不断放大辐射半径，进而覆盖整张图。
实现方式
- 选择起始顶点放入队列，并标记为已访问；
- 当队列不为空时，从队列中取出顶点作为目标顶点，将目标顶点的所有相邻且未被访问过的顶点放入队列，并标记为已访问；
- 重复执行步骤 2。
根据实现方式可知，广度优先遍历的形式为，选择目标顶点后，依次访问目标顶点的所有相邻顶点，再依次对每个相邻顶点，依次访问其相邻顶点，如此重复对顶点执行向外扩散的访问操作，直至图中所有顶点皆被访问，即存储顶点的队列为空，表示已经没有未被访问的顶点加入队列。
示例演示
对于有向图 digraph，图的顶点集合和边集合如下：
digraph
step 1:
选择 3 作为起始顶点，此时： 队列元素：3 已访问元素：3
step 2:
顶点 3 出队，将顶点 3 周围未被访问的顶点入队： 队列元素：1,5 已访问元素：3,1,5
cycle 1:
顶点 5 出队，将顶点 5 周围未被访问的顶点入队： 队列元素：1 已访问元素：3,1,5
cycle 2:
顶点 1 出队，将顶点 1 周围未被访问的顶点入队： 队列元素：2,4 已访问元素：3,1,5,2,4
cycle 3:
顶点 4 出队，将顶点 4 周围未被访问的顶点入队： 队列元素：2 已访问元素：3,1,5,2,4
cycle 4:
顶点 2 出队，将顶点 2 周围未被访问的顶点入队： 队列元素： 已访问元素：3,1,5,2,4
参考代码
def bfs(index, graph):
queue, flag = Queue(), [False] * graph.number
queue.put(index) # save the node index
flag[index - 1] = True # indicates whether the node has been visited
while not queue.empty():
node = graph.list[queue.get() - 1]
while node:
if not flag[node.index - 1]:
queue.put(node.index)
flag[node.index - 1] = True
node = node.next程序中存在两层循环，第一层循环为判断存储顶点的队列是否为空，因为要对队列中的每个顶点执行访问其相邻顶点操作，所以若队列不为空，则表示还有顶点的相邻顶点未进行访问。第二层循环为判断相邻顶点状态，并执行入队操作。
性能分析
根据参考代码和演示示例可知，对于图中每个顶点的操作类型有如下几种，入队、出队、设置已访问状态以及扫描顶点邻接表。因为对于每个顶点以上操作只发生一次，所以入队、出队和已访问状态设置，时间复杂度为
，根据邻接表的介绍可知，
个顶点的邻接表，存储的总顶点个数为
或
，所以广度优先遍历的时间复杂度为
。bfs 算法过程中，需要申请
的数组记录顶点的访问状态，需要申请
的队列空间存储顶点，且根据邻接表的内容可知，使用邻接表作为存储结构的空间复杂度为
，所以广度优先遍历的空间复杂度为
。
深度优先方式
深度优先遍历图的方式，同样会访问一个顶点的所有相邻顶点，不过深度优先的方式为，首先访问一个相邻顶点，并继续访问该相邻顶点的一个相邻顶点，重复执行直到当前正在被访问的顶点出度为零，或者不存在未访问状态的相邻顶点，则回退到上一个顶点继续按照该深度优先方式访问。因为存在回溯行为，所以需要借助栈结构保存顶点，或者直接利用递归调用产生的方法栈帧来完成回溯。
相对于广度优先访问，深度优先的方式更像是一条路走到黑，走不下去了再回到上个路口选择另外一条路。
实现方式
- 选择起始顶点入栈，并标记为已访问；
- 当栈不为空时，选择栈顶元素作为目标顶点，若目标顶点存在未访问状态的相邻顶点，则将该相邻顶点入栈，并标记为已访问；若不存在未访问状态的相邻顶点，则执行出栈操作；
- 重复执行步骤 2。
示例演示
对于有向图 digraph，图的顶点集合和边集合如下：
digraph
step 1:
选择 3 作为起始顶点，此时： 栈元素：3 已访问元素：3
step 2:
顶点 3 作为目标顶点，将顶点 3 相邻未访问状态的顶点入栈： 栈元素：3,5 已访问元素：3,5
cycle 1:
顶点 5 作为目标顶点，因为不存在相邻未访问状态的顶点，所以执行出栈操作： 栈元素：3 已访问元素：3,5
cycle 2:
顶点 3 作为目标顶点，将顶点 3 相邻未访问状态的顶点入栈： 栈元素：3,1 已访问元素：3,5,1
cycle 3:
顶点 1 作为目标顶点，将顶点 1 相邻未访问状态的顶点入栈： 栈元素：3,1,4 已访问元素：3,5,1,4
cycle 4:
顶点 4 作为目标顶点，因为不存在相邻未访问状态的顶点，所以执行出栈操作： 栈元素：3,1 已访问元素：3,5,1,4
cycle 5:
顶点 1 作为目标顶点，将顶点 1 相邻未访问状态的顶点入栈： 栈元素：3,1,2 已访问元素：3,5,1,4,2
cycle 6:
顶点 2 作为目标顶点，因为不存在相邻未访问状态的顶点，所以执行出栈操作： 栈元素：3,1 已访问元素：3,5,1,4,2
cycle 7:
顶点 1 作为目标顶点，因为不存在相邻未访问状态的顶点，所以执行出栈操作： 栈元素：3 已访问元素：3,5,1,4,2
cycle 8:
顶点 3 作为目标顶点，因为不存在相邻未访问状态的顶点，所以执行出栈操作： 栈元素： 已访问元素：3,5,1,4,2
参考代码
def dfs(index, graph):
stack, flag = [], [False] * graph.number
stack.append(index) # save the node index
flag[index - 1] = True # indicates whether the node has been visited
while len(stack) > 0:
node, size = graph.list[stack[-1] - 1], len(stack)
while node:
if not flag[node.index - 1]:
stack.append(node.index)
flag[node.index - 1] = True
break
node = node.next
if size == len(stack): # means no node append
stack.pop()程序中存在两层循环，第一层循环为判断栈是否为空，因为深度优先的遍历方式存在回溯的行为，所以借助栈结构来完成回溯操作。当栈为空时，表示已经回溯到起始顶点，且没有未访问状态的相邻顶点入栈，即图中所有顶点皆被访问过。第二层循环为对目标顶点的相邻顶点进行扫描，若存在未访问的相邻顶点，则将该相邻顶点入栈，并标记为已访问；若不存在，则执行出栈操作。
这里提供另外一种实现方式，通过函数递归调用形成的方法栈帧完成回溯操作：
def dfs(index, graph, flag):
node, flag[index - 1] = graph.list[index - 1], True
while node:
if not flag[node.index - 1]:
dfs(node.index, graph, flag)
node = node.next性能分析
根据参考代码和演示示例可知，对于图中每个顶点的操作类型有如下几种，入栈、出栈、设置已访问状态以及扫描顶点邻接表。对于入栈、出栈以及设置访问状态操作，每个顶点只会执行一次。根据程序中第二层循环的实现可知，对每个顶点的相邻顶点扫描只会全扫描一次，扫描结束即发生回溯。所以深度优先遍历的时间复杂度为
。dfs 算法过程中，需要申请
的数组记录顶点的访问状态，需要申请
的栈空间存储顶点，且根据邻接表的内容可知，使用邻接表作为存储结构的空间复杂度为
，所以深度优先遍历的空间复杂度为
。