图的定义
在 Python 中，可以使用字典来表示图。字典的键表示图中的顶点，而对应的值是与该顶点直接相连的顶点及其边的信息。
通常有两种方式来表示图：
邻接列表（Adjacency List）： 使用字典来表示，其中每个顶点对应一个键，值是一个列表，存储与该顶点相邻的顶点及其边的信息。
邻接矩阵（Adjacency Matrix）： 使用二维列表（或二维数组）来表示，其中每行和每列分别对应图中的顶点，矩阵元素表示顶点之间是否相连，以及边的权重信息。
下面分别介绍这两种方式：
1. 邻接列表
graph = {
'A': {
'B': 1, 'C': 4},
'B': {
'A': 1, 'C': 2, 'D': 5},
'C': {
'A': 4, 'B': 2, 'D': 1},
'D': {
'B': 5, 'C': 1}
}
在这个示例中，顶点 ‘A’ 与 ‘B’ 和 ‘C’ 相连，边的权重分别为 1 和 4。
2. 邻接矩阵
# 定义顶点列表
vertices = ['A', 'B', 'C', 'D']
# 定义邻接矩阵
graph = [
[0, 1, 4, 0],
[1, 0, 2, 5],
[4, 2, 0, 1],
[0, 5, 1, 0]
]
在这个示例中，行和列分别代表顶点 ‘A’, ‘B’, ‘C’, ‘D’，而矩阵中的元素表示两个顶点之间的边的权重。如果两个顶点之间没有边相连，则对应元素为 0。
在实际应用中，根据具体情况选择邻接列表或邻接矩阵表示图。如果图是稀疏的（即顶点之间的边相对较少），通常使用邻接列表更加高效。而如果图是稠密的（即顶点之间的边较多），则邻接矩阵更为适用。
图的访问
访问图的方式取决于图的表示方法。下面分别介绍如何访问邻接列表和邻接矩阵表示的图：
1. 邻接列表
对于邻接列表，可以通过字典的键来访问顶点，并通过键对应的值（也是一个字典）来获取与该顶点相邻的顶点及其边的信息。
graph = {
'A': {
'B': 1, 'C': 4},
'B': {
'A': 1, 'C': 2, 'D': 5},
'C': {
'A': 4, 'B': 2, 'D': 1},
'D': {
'B': 5, 'C': 1}
}
# 访问顶点 'A' 的相邻顶点及其边的信息
neighbors_of_A = graph['A']
print(neighbors_of_A) # 输出：{'B': 1, 'C': 4}
# 获取顶点 'A' 到顶点 'B' 的边的权重
weight_from_A_to_B = graph['A']['B']
print(weight_from_A_to_B) # 输出：1
2. 邻接矩阵
对于邻接矩阵，可以通过行和列的索引来访问对应的顶点，并通过矩阵中的元素来获取两个顶点之间的边的权重信息。
# 定义顶点列表
vertices = ['A', 'B', 'C', 'D']
# 定义邻接矩阵
graph = [
[0, 1, 4, 0],
[1, 0, 2, 5],
[4, 2, 0, 1],
[0, 5, 1, 0]
]
# 获取顶点 'A' 到顶点 'B' 的边的权重
weight_from_A_to_B = graph[vertices.index('A')][vertices.index('B')]
print(weight_from_A_to_B) # 输出：1
在邻接矩阵中，可以通过 vertices.index('顶点名称') 获取对应顶点的索引，然后使用索引来访问矩阵中的元素。
