Python全系列 教程
3567个小节阅读:5930.3k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
xxxxxxxxxx
class Graph:
"""基于邻接表实现的无向图类"""
def __init__(self):
"""构造方法"""
# 邻接表,key:顶点,value:该顶点的所有邻接顶点
self.adj_list = {}
def add_vertex(self, vet):
"""添加顶点"""
if vet in self.adj_list:
return
# 在邻接表中添加一个新链表
self.adj_list[vet] = []
def add_edge(self, vet1, vet2):
"""添加边"""
if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
return
# 添加边 vet1 - vet2
self.adj_list[vet1].append(vet2)
self.adj_list[vet2].append(vet1)
def remove_edge(self, vet1, vet2):
"""删除边"""
if vet1 not in self.adj_list or vet2 not in self.adj_list or vet1 == vet2:
return
# 删除边 vet1 - vet2
self.adj_list[vet1].remove(vet2)
self.adj_list[vet2].remove(vet1)
def remove_vertex(self, vet):
"""删除顶点"""
if vet not in self.adj_list:
raise ValueError()
# 在邻接表中删除顶点 vet 对应的链表
self.adj_list.pop(vet)
# 遍历其他顶点的链表,删除所有包含 vet 的边
for vertex in self.adj_list:
if vet in self.adj_list[vertex]:
self.adj_list[vertex].remove(vet)
def display(self):
"""打印邻接表"""
print("邻接表")
for vertex in self.adj_list:
tmp = [v for v in self.adj_list[vertex]]
print(f"{vertex}: {tmp},")
if __name__ == '__main__':
my_graph = Graph()
# 添加顶点
my_graph.add_vertex('A')
my_graph.add_vertex('B')
my_graph.add_vertex('C')
my_graph.add_vertex('D')
my_graph.display()
# 添加边
my_graph.add_edge('A', 'B')
my_graph.add_edge('A', 'C')
my_graph.add_edge('A', 'D')
my_graph.add_edge('B', 'C')
my_graph.display()
# 删除边
my_graph.remove_edge('A', 'B')
my_graph.remove_edge('A', 'D')
my_graph.display()
# 删除顶点
my_graph.remove_vertex('C')
my_graph.display()