Python自定义邻接表图类

雨点打透心脏的1/2处 2022-02-19 08:59 404阅读 0赞

**图抽象数据类型（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)