大家好，又见面了，我是你们的朋友全栈君。

广度优先遍历（BFS）

顾名思义，BFS总是先访问完同一层的结点，然后才继续访问下一层结点，它最有用的性质是可以遍历一次就生成中心结点到所遍历结点的最短路径，这一点在求无权图的最短路径时非常有用。广度优先遍历的核心思想非常简单，用python实现起来也就十来行代码。下面就是超精简的实现，用来理解核心思想足够了：

import Queue

def bfs(adj, start):
    visited = set()
    q = Queue.Queue()
    q.put(start)
    while not q.empty():
        u = q.get()
        print(u)
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                q.put(v)


graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
bfs(graph, 1)

解释一下代码：

1、创建一个队列，遍历的起始点放入队列

2、从队列中取出一个元素，打印它，并将其未访问过的子结点放到队列中

3、重复2，直至队列空

时间复杂度：基本与图的规模成线性关系了，比起图的其它算法动不动就O(n^2)的复杂度它算是相当良心了

空间复杂度：我们看到程序中使用了一个队列，这个队列会在保存一层的结点，当图规模很大时占用内存还是相当可观的了，所以一般会加上一些条件，比如遍历到第N层就停止

关于图的理解的一个技巧

上面提到，BFS遍历会由近及远，同一层会先遍历完。这里随便提一个关于图的展示问题，或者说当你拿到一个图，当你要对它进行分析时，这个图在你的脑海里会一个什么形态呢？比较一下下面两种形态，你觉得哪一种更加清晰？

其实你仔细看，左右两张图其实数据是一样的，只是布局不一样罢了，上面的图使用了一种无规律凌乱的布局，而下面假设出了一个中心点，将与它直接相连的结点放在第一层上，与它距离为2的结点放在第二层了，这样会有什么好处呢？好处就是这样布局后边只会在相邻层或者同一层间的结点间相连，这样就不会出现很长或者交叉的边了，整个图会感觉有序得多，在思考图的一些性质的时候也会清晰得多。

回过头来，这种布局不就是BFS形成的吗。

深度优先遍历（DFS）

深度优先遍历算法（DFS），相比于BFS，只需要将队列改成LifoQueue（其实也就是栈）就可以了：

# encoding=utf-8
import Queue

def bfs(adj, start):
    visited = set()
    q = Queue.LifoQueue() # 与BFS相比，只用改这一行代码
    q.put(start)
    while not q.empty():
        u = q.get()
        print(u)
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                q.put(v)


graph = {1: [4, 2], 2: [3, 4], 3: [4], 4: [5]}
bfs(graph, 1)

解释一下代码（LIFO队列就是栈，下面文字改用栈来描述）：

1、创建一个栈，将遍历的起始点放入栈

2、从栈弹出一个元素，打印它，并将其未访问过的子结点压栈

3、重复2，直至栈空

不同时BFS时用的一般队列Queue，DFS时使用了和栈等效的LIFO队列，也就是后加入的会先拿出，所以子结点会优先被访问到。

时间复杂度：与图的规模成线性关系了，为O(n)。

空间复杂度：栈会保存从根到叶子路径上的结点，及他们子结点，所以空间复杂度还是比较小的。