python实现抽象数据类型=＞图(邻接矩阵和邻接表)

 实现图共两种方法：

1. 邻接矩阵
2. 邻接表

以下代码用邻接矩阵实现

inf = -1

class Graph:
	def __init__(self, n):
		self.n = n  # n个顶点
		self.edges = []  # 邻接矩阵
		for i in range(n):
			L = []
			for j in range(n):
				L.append(inf)
			self.edges.append(L)
			
	def addEdge(self, u, v, w):
		"""
		向邻接矩阵中添加权重
		u: 第u行
		v: 第v列
		w: 权重
		"""
		self.edges[u][v] = w
		
	def printGraph(self):
		"""
		打印邻接矩阵
		"""
		for i in range(self.n):
			for j in range(self.n):
				print(self.edges[i][j], end=" ")
			print('')
			
def test():
	g = Graph(5)
	g.addEdge(0, 1, 1)
	g.addEdge(0, 2, 3)
	g.addEdge(1, 2, 2)
	g.addEdge(2, 3, 7)
	g.addEdge(3, 4, 9)
	g.addEdge(4, 0, 4)
	g.addEdge(4, 2, 5)
	g.printGraph()
	
test()

以下代码用邻接表实现图

class EdgeNode:
	"""
	有向边节点
	"""
	def __init__(self, v, w):
		self.vertex = v   # 弧尾
		self.weight = w   # 权重
		
class VertexNode:
	"""
	有向边节点
	"""
	def __init__(self, v):
		self.vertex = v   # 弧头
		self.edges = []   # 所有弧尾组成的列表
		
class Graph:
	"""
	有向图类
	"""
	def __init__(self, n):
		self.n = n   #有n个顶点
		self.nodes = [VertexNode(i) for i in range(n)]  # 初始化n个弧头节点
		
	def addEdge(self, u, v, w):  #u: 弧头  v: 弧尾   w: 权重
		"""
		将指定的弧尾节点和权重添加到指定的弧头
		"""
		self.nodes[u].edges.append(EdgeNode(v, w))
		
	def printGraph(self):
		"""
		输出图节点
		"""
		for i in range(self.n):
			print("Vertex: ", i, end=":")
			for e in self.nodes[i].edges:
				print(e.vertex, '(', e.weight, ')', end=" ")
			print("")
			
def test():
	g = Graph(5)
	g.addEdge(0, 1, 4)
	g.addEdge(0, 2, 2)
	g.addEdge(1, 2, 3)
	g.addEdge(2, 3, 4)
	g.addEdge(3, 4, 2)
	g.printGraph()
	
test()