鄰接表怎么畫(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)則保存頂點連接邊的權重。

鄰接表的優點:是能高效地表示一個稀疏圖。鄰接表還能很容易的找到某個頂點與其他頂點的所有連接。

自定義頂點類

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怎么自定義鄰接表圖類”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注本站網站,小編會繼續努力為大家帶來更多實用的文章!