基本数据结构-图

dff

图的抽象数据类型

• Graph()新建一个空图
• addVertex(vert)向图中添加一个顶点实例
• addEdge(fromVert,toVert)添加一条有向边，用于连接fromVert,toVert
• addEdge(fromVert,toVert,weight)向图中添加一条带权重weight的有向边，用于连接顶点fromVert,toVert。
• getVertex(vertKey)在图中找到名为 vertKey 的顶点。
• getVertices()以列表形式返回图中所有顶点。
• in 通过 vertex in graph 这样的语句，在顶点存在时返回 True，否则返回 False。

邻接矩阵

要实现图，最简单的方式就是使用二维矩阵。在矩阵实现中，每一行和每一列都表示图中的

一个顶点。第 v 行和第 w 列交叉的格子中的值表示从顶点 v 到顶点 w 的边的权重。如果两个顶点

被一条边连接起来，就称它们是相邻的。

邻接表

为了实现稀疏连接的图，更高效的方式是使用邻接表。在邻接表实现中，我们为图对象的所有顶点保存一个主列表，同时为每一个顶点对象都维护一个列表，其中记录了与它相连的顶点。

在对 Vertex 类的实现中，我们使用字典（而不是列表），字典的键是顶点，值是权重。

邻接表的优点是能够紧凑地表示稀疏图。此外，邻接表也有助于方便地找到与某一个顶点相连的其他所有顶点。