深度优先搜索（DFS）和广度优先搜索（BFS）
这个思路和我们之前的二叉树的遍历类似。
以这个图为例：这是个无向图，有环。
B
|
A ----- D ------- F
| | | |
C --- E G H
同样，两个步骤：
1. 节点被发现，这个是说该节点被发现存在；
2. 节点被访问过，这个是说该节点被检查了，并且是否有子节点需要遍历。
先看深度优先搜索（DFS），从A开始，一直往下，直到终点，然后开始回溯。
explored = []; discovered = [A]
A有三个相邻节点
explored = [A]; discovered = [B,C,D]
然后我们explore B，与B相邻的只有A，A已经在explored里，所以B explore完毕
explored = [A,B]; discovered = [C,D]
然后开始explore C，与C相邻的有A，E，A已经在explored里，把E放入discovered，C explore完毕
explored = [A,B,C]; discovered = [E,D] // 注意这里我们把E放在前面，这保证我们后面优先explore E
接着开始Explore E，D、C相邻，C已经explored，D to be explored，E explore完毕
explored = [A,B,C,E]; discovered = [D]
explore D，F、G相邻新节点
explored = [A,B,C,E,D]; discovered = [F,G]
explored = [A,B,C,E,D,F]; discovered = [H,G]
explored = [A,B,C,E,D,F,H]; discovered = [G]
explored = [A,B,C,E,D,F,H,G]; discovered = []
顺序为：A,B,C,E,D,F,H,G。
广度优先搜索（BFS），从A开始，一次explore相邻节点，然后到下一层。
explored = []; discovered = [A]
explored = [A]; discovered = [B,C,D]
explored = [A,B]; discovered = [C,D]
explored = [A,B,C]; discovered = [D,E]
explored = [A,B,C,D]; discovered = [E,F,G]
explored = [A,B,C,D,E]; discovered = [F,G]
expored = [A,B,C,D,E,F]; discovered = [G,H]
expored = [A,B,C,D,E,F,G]; discovered = [H]
expored = [A,B,C,D,E,F,G,H]; discovered = []
顺序为：A,B,C,D,E,F,G,H。
代码暂略。
性能分析
DFS：
时间复杂度：最坏情况，所有节点和边都遍历到，O(|N| + |E|)，N是节点数；E是边数
空间复杂度：最坏情况，图有很长的path，O(|N|)
BFS：
时间复杂度：最坏情况，所有节点和边都遍历到，O(|N| + |E|)
空间复杂度：最坏情况，O(|N|)
两种都是线性复杂度。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。