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是鄰居頂點的鍵，默認權重為0	
	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

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