7.1图

图Graph的概念

图Graph是比书更为一般的结构，也是由节点和边构成（实际上树是一种具有特殊性质的图），图可以用来表示现实世界中很多事物。
相关术语：

• 顶点Vertex（也称“节点Node”）
  是图的基本组成部分，顶点具有名称标识Key，也可以携带数据项payload
• 边Edge（也称“弧Arc”）
  作为2个顶点之间关系的表示，边连接两个顶点；边可以是无向或者有向的，相应的图称作“无向图”和“有向图”
• 权重Weight
  为了表达从一个顶点到另一个顶点的“代价”，可以给边赋权；例如公交网络中两个站点之间的“距离”、“通行时间”和“票价”都可以作为权重。

图的定义：
一个图G可以定义为G=(V, E)其中V是顶点的集合，E是边的集合，E中的每条边e=(v, w)，v和w都是V中的顶点；如果是赋权图，则可以在e中添加权重分量子图：V和E的子集
赋权图的例子：6个顶点及9条边
有向赋权图，权重为整数

image.png
image.png
image.png

路径Path
图中的路径，是由边依次连接起来的顶点序列；无权路径的长度为边的数量；带权路径的长度为所有边权重的和；
如上图的一条路径(v3,v4,v0,v1) 其边为{(v3,v4,7),(v4,v0,1),(v0,v1,5)}
圈Cycle
圈是首尾顶点相同的路径，如上图中(v5,v2,v3,v5)是一个圈，如果有向图中不存在任何圈，则称作“有向无圈图directed acyclic graph: DAG”后面我们可以看到如果一个问题能表示成DAG，就可以用图算法很好地解决。

图抽象数据类型

抽象数据类型ADT Graph定义如下：

• Graph()：创建一个空的图；
• addVertex(vert)：将顶点vert加入图中
• addEdge(fromVert, toVert)：添加有向边
• addEdge(fromVert, toVert, weight)：添加带权的有向边
• getVertex(vKey)：查找名称为vKey的顶点
• getVertices()：返回图中所有顶点列表

• in：按照vert in graph的语句形式，返回顶点是否存在图中True/False
  ADT Graph的实现方法有两种主要形式：
  邻接矩阵（adjacency matrix）和邻接表（adjacency list），后者较常用。
  邻接矩阵Adjacency Matrix
  矩阵的每行和每列都代表图中的顶点，如果两个顶点之间有边相连，设定行列值
  无权边则将矩阵分量标注为1，或者0，带权边则将权重保存为矩阵分量值

  
  image.png
  image.png
  

  邻接矩阵实现法的优点是简单，可以很容易得到顶点是如何相连，但如果图中的边数很少则效率低下成为“稀疏sparse”矩阵，而大多数问题所对应的图都是稀疏的边远远少于|V|^2这个量级。
  邻接列表Adjacency List
  邻接列表adjacency list可以成为稀疏图的更高效实现方案维护一个包含所有顶点的主列表（master list）主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表

  
  image.png
  邻接列表法的存储空间紧凑高效，很容易获得顶点所连接的所有顶点，以及连接边的信息