• 图是网络结构的抽象模型,是一组由连接的节点。
  • 图可以表示任何二元关系,比如道路、航班……
    • JS里面没有图,但可以用Object、Array构建图
  • 图的表示方法
    • 邻接矩阵

image.png

  • 邻接表

image.png

  • 关联矩阵
    • 图的常见操作
  • 深度优先遍历
  • 广度优先遍历

    深度优先遍历

  • 深度优先遍历的算法口诀
    • 访问根节点
    • 对根节点的没访问过的相邻节点挨个进行深度优先遍历
    • image.png

广度优先遍历

  • 新建一个队列,把根节点入队
  • 把对头出队并访问
  • 把对头的没访问过的相邻节点入队
  • 重复二三步,直到队列为空