由于图的任意顶点都可能与其他顶点相邻接，所以可以设一个辅助数组 visited[] 来标记顶点是否被访问过

广度优先搜索(BFS, Breadth-First-Search)

类似树的层序遍历

要点：

1. 找到与一个顶点相邻的所有顶点
2. 标记哪些顶点被访问过(visited[])
3. 需要一个辅助队列(queue)
4. FirstNeighbor(G, x): 求图G中第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1
5. NextNeighbor(G, x, y): 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点好，若y是x的最后一个邻接点，则返回-1

• 连通图可以一次BFS完成遍历

• 如果是非连通图可以通过BFSTraverse循环调用BFS

• 同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一

• 同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一

• 空间复杂度：最坏情况，辅助队列大小为 O(|V|)

• 时间复杂度

  • 邻接矩阵：O(|V|²)
  • 邻接表： O(|V|+|E|)

广度优先生成树

广度优先生成树由广度优先遍历过程确定。由于邻接表表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一

对非连通图的广度优先遍历，可以得到广度优先生成森林

深度优先搜索(DFS, Deep-First-Search)

类似树的先根遍历

要点：

1. 标记哪些顶点被访问过(visited[])

• 空间复杂度：

  • 来自函数调用栈
  • 最坏情况，递归深度为 O(|V|)，最好 O(1)

• 时间复杂度：

  • 邻接矩阵：O(|V|²)
  • 邻接表： O(|V|+|E|)

• 同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一

• 同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一

• 当各边当权值相等时，广度优先算法可以解决单源最短路径问题

深度优先生成树

同一个图的邻接矩阵表示方式唯一，因此深度优先生成树也唯一

同一个图的邻接表表示方式不唯一，因此深度优先生成树不唯一

深度优先生成森林同广度优先生成森林

图的连通性

利用图的遍历算法来判断图的连通性

• 无向图：调用BFS/DFS函数的次数==1 ----> 连通图
• 有向图：从任一结点出发都只需要调用1次BFS/DFS ----> 强连通图

错题集

1. 

   答案与解析：

   
   答案： A
   解析：
   对一个有向图做深度优先遍历，并未专门判断有向图是否有环（有向回路）存在，无论图中是否有环，都得到一个顶点序列。若无环，在退出递归过程中输出的应是逆拓扑有序序列。对有向无环图利用深度优先搜索进行拓扑排序的例子如下：
   如图所示，退出DFS栈的顺序为 efgdcahb ，此图的一个拓扑序列为
   bhacdgfe。该方法的每一步均是先输出当前无后继的结点，即对每个结点v，先递归地求出v的每个后继的拓扑序列。对于一个AOV网，按此方法输出的序列是一个逆拓扑序列。
   

2. 

   答案与解析：

   
   答案： D
   解析：
   <v₀, v₁, v₃, v₂>
   <v₀, v₂, v₃, v₁>
   <v₀, v₂, v₁, v₃>
   <v₀, v₃, v₂, v₁>
   <v₀, v₃, v₁, v₂>