图的遍历

图的遍历

• 连通分量是无向图的极大连通子图，其极大的含义是将依附于连通分量中顶点的所有边都加上，所以连通分量中可能存在回路，就不是生成树
• 对于无向图的广度优先生成树，起点到其他顶点的路径是图中对应的最短路径，即所有生成树中树高最小。
  • 深度优先总是尽可能深的搜索图，因此其路径也尽可能长，故深度优先生成树的树高总是大于或等于广度优先生成树的树高
• 若具体的存储结构已给出，则顶点和邻接点的顺序固定，DFS和BFS的搜索序列固定