第 2 章 常用数据结构2.7图2.7.1图的概述线性结构局限于只有一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当我们需要表示多对多的关系时就需要用到图了图是比树更普遍的结构可以认为树是一种特殊的图。图由节点和边组成。图的常见术语节点也称为顶点是图的基础部分。边连接两个节点也是图的基础部分。可以是单向的也可以是双向的。权重边可以添加“权重”变量。邻接两节点之间存在边则称这两个节点邻接。度一个节点的边的数量。入度为指向该节点的边的数量出度为该节点指向其他节点的边的数量。路径从一节点到另一节点所经过的边的序列。环首尾节点相同的路径。2.7.2图的分类1)有向图和无向图有向图边是单向的。无向图边是双向的。2)连通图和非连通图连通图从某个节点出发可以到达其余任意节点。非连通图从某个节点出发有节点不可达。2.7.3图的常用表示法1)邻接矩阵邻接矩阵用一个n×n的矩阵来表示有n个节点之间的关系矩阵的每一行列代表一个节点矩阵m行n列的值代表是否存在由m指向n的边。邻接矩阵适合存储稠密图。2)邻接表邻接表存储n个链表、列表或其他容器每个容器存储该节点的所有邻接节点。邻接表适合存储稀疏图空间效率高尤其在处理边远少于节点的图时表现优越但在进行边查找时不如邻接矩阵高效。2.7.4 图的遍历广度优先搜索广度优先搜索BFSBreadth First Search从起始节点开始首先访问该节点的所有邻接节点然后再访问邻接节点的邻接节点依此类推逐层访问节点。从图的起始节点开始首先访问该节点并标记为已访问。然后依次访问所有未被访问的邻接节点并将它们加入到队列中。当队列中的节点被访问时继续访问它的邻接节点并将新的节点加入队列。直到队列为空表示所有节点都已被访问。深度优先搜索深度优先搜索DFSDepth First Search尽可能地深入到图的每一个分支直到不能再深入为止然后回溯到上一个节点继续尝试其他的分支。从图的一个起始节点开始访问这个节点并标记为已访问。对于每个未访问的邻接节点递归地执行 DFS直到没有未访问的邻接节点。当回溯到一个节点时继续访问它的其他邻接节点。