Python怎么自定义邻接表图类

这篇文章主要介绍“python怎么自定义邻接表图类”，在日常操作中，相信很多人在Python怎么自定义邻接表图类问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Python怎么自定义邻接表图类”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

Python自定义邻接表图类

图抽象数据类型（ADT）的术语

顶点(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)则保存顶点连接边的权重。

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

自定义顶点类

class Vertex(object):# 初始化顶点def __init__(self, key):self.id = key #初始化顶点的键self.connectedTo = {}#初始化顶点的值# 添加邻居顶点，参数nbr是邻居顶点的键，默认权重为0def addNeighbor(self, nbr, weight=0):self.connectedTo[nbr] = weightdef __str__(self):return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])# 获取该顶点所有邻居顶点的键def getConnections(self):return self.connectedTo.keys()# 获取顶点的键def getId(self):return self.id# 获取到某邻居顶点的权重def getWeight(self, nbr):return self.connectedTo[nbr]# 自定义图类class Graph(object):# 初始化图def __init__(self):self.vertList = {}#初始化邻接表self.numVertices = 0 #初始化顶点数# 添加顶点def addVertex(self, key):newVertex = Vertex(key)#创建顶点self.vertList[key] = newVertex #将新顶点添加到邻接表中self.numVertices = self.numVertices + 1 #邻接表中顶点数+1return newVertex# 获取顶点def getVertex(self, n):if n in self.vertList:#若待查询顶点在邻接表中，则return self.vertList[n] #返回该顶点else:return None# 使之可用in方法def __contains__(self, n):return n in self.vertList# 添加边，参数f为起始顶点的键，t为目标顶点的键，cost为权重def addEdge(self, f, t, cost=0):if f not in self.vertList:#起始顶点不在邻接表中，则self.addVertex(f) #添加起始顶点if t not in self.vertList:#目标顶点不在邻接表中，则self.addVertex(t)#添加目标顶点self.vertList[f].addNeighbor(self.vertList[t], cost)#在邻接表中添加起始点的目标点及权重# 获取邻接表中所有顶点的键def getVertices(self):return self.vertList.keys()# 迭代显示邻接表的每个顶点的邻居节点def __iter__(self):return iter(self.vertList.values())g = Graph() #实例化图类for i in range(6): g.addVertex(i) #给邻接表添加节点print(g.vertList)#打印邻接表g.addEdge(0, 1, 5) #给邻接表添加边及权重g.addEdge(0, 5, 2) g.addEdge(1, 2, 4) g.addEdge(2, 3, 9) g.addEdge(3, 4, 7) g.addEdge(3, 5, 3) g.addEdge(4, 0, 1) g.addEdge(5, 4, 8) g.addEdge(5, 2, 1) for v in g: #循环每个顶点for w in v.getConnections(): #循环每个顶点的所有邻居节点print("(%s, %s)" % (v.getId(), w.getId())) #打印顶点和其邻居节点的键

结果为：

{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)

python图的邻接表表示

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

"""图的邻接表表示""" class GraphNode(object):    """节点类"""    def __init__(self,_elem=None):        self._elem = _elem # 数据域        self._next = None # 指针域  class Graph(object):    """图类"""    def __init__(self):        """初始化一个序列"""        self._graph = []     def createPeak(self,newNode):        """创建一个图顶点"""        self._graph.append(newNode)        return self._graph     def createSide(self):        """创建图的边"""        for node in self._graph:            graphNode = node            print(f"请输入{graphNode._elem}的邻接点,以-1结束")            while True:                _graphNode = GraphNode() # 初始化每个节点的邻接点                end = input("请输入: ")                if end == '-1':                    self.printGraph()                    break                else:                    """临时列表图中的节点值,用来后续判断"""                    temp = []                    for item in self._graph:                        temp.append(item._elem)                    if end not in temp:                        """输入的邻接节点不在顶点中"""                        print("输入的节点不属于图中的顶点,重新输入")                        continue                    elif end == graphNode._elem:                        """输入的顶点就是当前顶点"""                        print("输入的是当前节点,重新输入")                        continue                    else:                        # 新建节点                        _graphNode._elem = end                        # 指针向后移                        _graphNode._next = graphNode._next                        graphNode._next = _graphNode                        graphNode = graphNode._next     def printGraph(self):        """遍历当前节点列表"""        for node in self._graph:            print(f"顶点{node._elem}的邻接链表: ",end='')            while node != None:                if node._next != None:                    print(f'{node._elem}-->',end='')                else:                    print(f'{node._elem}', end='')                node = node._next            print() # 换节点,换行  if __name__ == '__main__':    count = int(input('请输入顶点个数: '))    s = Graph()    # 创建节点    peakNodeStr = input('请输入顶点: ')    peakNodes = peakNodeStr.split(' ')    # 将输入的节点实例化之后添加到图的链表中    for peakNode in peakNodes:        peak = GraphNode(peakNode)        s.createPeak(peak)     print('图中的节点：',end='')    for peak in s._graph:        print(peak._elem,end=' ')    print()     # 创建边    s.createSide()

到此，关于“Python怎么自定义邻接表图类”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！