Python怎么自定义邻接表图类(python,开发技术)

接下来，请跟着小编一起来学习吧！

顶点(Vertex)：也称节点(node)，是图的基础部分。具有名称标识“key”。顶点也可以有附加信息项“playload”。

边(Edge)：也称弧(arc)，也是图的基础组成部分。如果一条边连接两个顶点，则表示两者具有联系。边可以是单向的，也可以是双向的。如果图中的边都是单向的，则称这个图是“有向图(directed graph/digraph)”。

权重(Weight)：为了表达从一个顶点到另一个顶点的“代价”，可以给边赋权。

路径(Path)：图中的路径，是由边依次连接起来的顶点序列。无权路径的长度为边的数量。带权路径的长度为所有边的权重之和。

圈(Cycle)：有向图里的圈是首尾顶点相同的路径。没有圈的图称为“无圈图(acyclic graph)”，没有圈的有向图称为“有向无圈图(directed acyclic graph 或 DAG)”。

实现图的两个著名方法：邻接矩阵(adjacency matrix)和邻接表(adjacency list)。

二维矩阵中，每行和每列都代表图中的顶点。如果顶点v到顶点w之间有边相连，则将值储存在矩阵的v行、w列。每一格的值代表了从顶点v到顶点w边的权重。

邻接矩阵的优点：是简单，然而，大部分的矩阵是空的，这种情况则称矩阵是“稀疏”的。矩阵并不是一个储存稀疏数据的有效途径。

实现稀疏图的更高效方法是使用邻接表(adjacency list)。

在这个实现方法中，包含一个含有所有顶点的主列表(master list)，主列表中的每个顶点，再关联一个与自身有边连接的所有顶点的列表。

在实现顶点类的方法中使用字典而不是列表，字典中的键(key)对应顶点，值(value)则保存顶点连接边的权重。

邻接表的优点：是能高效地表示一个稀疏图。邻接表还能很容易的找到某个顶点与其他顶点的所有连接。

classGraph(object):

结果为：

{0: <main.Vertex object at 0x00000000021BF828>, 1: <main.Vertex object at 0x00000000021BF860>, 2: <main.Vertex object at 0x00000000021BF898>, 3: <main.Vertex object at 0x00000000021BF8D0>, 4: <main.Vertex object at 0x00000000021BF908>, 5: <main.Vertex object at 0x00000000021BF940>}
(0, 1)
(0, 5)
(1, 2)
(2, 3)
(3, 4)
(3, 5)
(4, 0)
(5, 4)
(5, 2)

我就废话不多说了，上代码

_graphNode._elem=end

s.createSide()若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！