Python如何自定义邻接表图类
目录
- Python自定义邻接表图类
- 图抽象数据类型(ADT)的术语
- 邻接矩阵和邻接表的优缺点
- 自定义顶点类
- 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()
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。