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

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

自定义顶点类

classVertex(object):#初始化顶点def__init__(self,key):self.id=key#初始化顶点的键self.connectedTo={}#初始化顶点的值#添加邻居顶点,参数nbr是邻居顶点的键,默认权重为0defaddNeighbor(self,nbr,weight=0):self.connectedTo[nbr]=weightdef__str__(self):returnstr(self.id)+'connectedTo:'+str([x.idforxinself.connectedTo])#获取该顶点所有邻居顶点的键defgetConnections(self):returnself.connectedTo.keys()#获取顶点的键defgetId(self):returnself.id#获取到某邻居顶点的权重defgetWeight(self,nbr):returnself.connectedTo[nbr]#自定义图类classGraph(object):#初始化图def__init__(self):self.vertList={}#初始化邻接表self.numVertices=0#初始化顶点数#添加顶点defaddVertex(self,key):newVertex=Vertex(key)#创建顶点self.vertList[key]=newVertex#将新顶点添加到邻接表中self.numVertices=self.numVertices+1#邻接表中顶点数+1returnnewVertex#获取顶点defgetVertex(self,n):ifninself.vertList:#若待查询顶点在邻接表中,则returnself.vertList[n]#返回该顶点else:returnNone#使之可用in方法def__contains__(self,n):returnninself.vertList#添加边,参数f为起始顶点的键,t为目标顶点的键,cost为权重defaddEdge(self,f,t,cost=0):iffnotinself.vertList:#起始顶点不在邻接表中,则self.addVertex(f)#添加起始顶点iftnotinself.vertList:#目标顶点不在邻接表中,则self.addVertex(t)#添加目标顶点self.vertList[f].addNeighbor(self.vertList[t],cost)#在邻接表中添加起始点的目标点及权重#获取邻接表中所有顶点的键defgetVertices(self):returnself.vertList.keys()#迭代显示邻接表的每个顶点的邻居节点def__iter__(self):returniter(self.vertList.values())g=Graph()#实例化图类foriinrange(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)forving:#循环每个顶点forwinv.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图的邻接表表示

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

"""图的邻接表表示"""classGraphNode(object):"""节点类"""def__init__(self,_elem=None):self._elem=_elem#数据域self._next=None#指针域classGraph(object):"""图类"""def__init__(self):"""初始化一个序列"""self._graph=[]defcreatePeak(self,newNode):"""创建一个图顶点"""self._graph.append(newNode)returnself._graphdefcreateSide(self):"""创建图的边"""fornodeinself._graph:graphNode=nodeprint(f"请输入{graphNode._elem}的邻接点,以-1结束")whileTrue:_graphNode=GraphNode()#初始化每个节点的邻接点end=input("请输入:")ifend=='-1':self.printGraph()breakelse:"""临时列表图中的节点值,用来后续判断"""temp=[]foriteminself._graph:temp.append(item._elem)ifendnotintemp:"""输入的邻接节点不在顶点中"""print("输入的节点不属于图中的顶点,重新输入")continueelifend==graphNode._elem:"""输入的顶点就是当前顶点"""print("输入的是当前节点,重新输入")continueelse:#新建节点_graphNode._elem=end#指针向后移_graphNode._next=graphNode._nextgraphNode._next=_graphNodegraphNode=graphNode._nextdefprintGraph(self):"""遍历当前节点列表"""fornodeinself._graph:print(f"顶点{node._elem}的邻接链表:",end='')whilenode!=None:ifnode._next!=None:print(f'{node._elem}-->',end='')else:print(f'{node._elem}',end='')node=node._nextprint()#换节点,换行if__name__=='__main__':count=int(input('请输入顶点个数:'))s=Graph()#创建节点peakNodeStr=input('请输入顶点:')peakNodes=peakNodeStr.split('')#将输入的节点实例化之后添加到图的链表中forpeakNodeinpeakNodes:peak=GraphNode(peakNode)s.createPeak(peak)print('图中的节点:',end='')forpeakins._graph:print(peak._elem,end='')print()#创建边s.createSide()

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