图的遍历

图的遍历可以解决很多搜索问题,在实际中应用非常广泛。图的遍历根据搜索方式的不同,分为广度优先搜索和深度优先搜索。

图的遍历

• 算法
  • 地位
    • 各种图的操作基础
• 按照
  • 某种
    • 搜索方法沿着图的边访遍图中的其余顶点
• 顶点
  • 图
    • 某一顶点出发
• 如果给定的图是
  • 无向图
    • 地位
      • 连通
  • 有向图
    • 地位
      • 强连通
  • 则
    • 遍历过程一次就能完成
      • 并
        • 可以
          • 按照访问的先后顺序
            • 得到
              • 由该图所有顶点
                • 组成的一个序列
                  • 请记住是一个
• 方法
  • 采用的数据结构
    • 邻接表
  • 深度优先搜索
    • 这是一个递归过程
      • 因此
        • 先设计一个
          • 从某个顶点为v0
            • 开始深度优先搜索的
              • 函数
  • 广度优先搜索
• 浮动主题