数据结构（七）——图

图的相关术语

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点）。学习图是重要的，因为任何二元关系都可以用图来表示。
相邻顶点：由一条边连接在一起的顶点。
度 ：其相邻顶点的数量
路径：顶点 v1, v2, …, vk的一个连续序列，其中 vi和 vi+1是相邻的。

图的表示

• 邻接矩阵 每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接
• 邻接表 邻接表由图中每个顶点的相邻顶点列表所组成

• 关联矩阵 在关联矩阵中，矩阵的行表示顶点，列表示边

  
  image.png

图的遍历

广度优先搜索（breadth-first search，BFS）和深度优先搜索（depth-first search，DFS）

• 广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的邻点（相邻顶点），就像一次访问图的一层。换句话说，就是先宽后深地访问顶点
• 深度优先搜索算法将会从第一个指定的顶点开始遍历图，沿着路径直到这条路径最后一个顶点被访问了，接着原路回退并探索下一条路径。换句话说，它是先深度后广度地访问顶点。