DSA 图实现
基本图实现
在对图运行算法之前，我们必须先以某种方式实现它。
为了实现图，我们将使用邻接矩阵，如下所示。
及其邻接矩阵
为了存储每个顶点的（在此情况下为字母 A、B、C 和 D）数据，这些数据被放入一个单独的数组中，该数组与邻接矩阵中的索引匹配，如下所示
vertexData = [ 'A', 'B', 'C', 'D']对于无向且非加权图（如上图所示），顶点 i 和 j 之间的边用值 1 存储。它在 (j,i) 和 (i,j) 两个位置都存储为 1，因为边在两个方向上都有。如你所见，对于此类无向图，矩阵变得对角线对称。
让我们看一个更具体的例子。在上图的邻接矩阵中，顶点 A 在索引 0 上，顶点 D 在索引 3 上，因此我们得到存储在位置 (0,3) 和 (3,0) 中的值 1 的 A 和 D 之间的边，因为边在两个方向上都有。
以下是上图中无向图的基本实现。
示例
Python
vertexData = ['A', 'B', 'C', 'D']
adjacency_matrix = [
[0, 1, 1, 1], # Edges for A
[1, 0, 1, 0], # Edges for B
[1, 1, 0, 0], # Edges for C
[1, 0, 0, 0] # Edges for D
]
def print_adjacency_matrix(matrix):
print("\nAdjacency Matrix:")
for row in matrix:
print(row)
print('vertexData:',vertexData)
print_adjacency_matrix(adjacency_matrix)此实现基本上只是一个二维数组，但为了更好地了解图中顶点是如何通过边连接起来的，我们可以运行此函数
示例
Python
def print_connections(matrix, vertices):
print("\nConnections for each vertex:")
for i in range(len(vertices)):
print(f"{vertices[i]}: ", end="")
for j in range(len(vertices)):
if matrix[i][j]: # if there is a connection
print(vertices[j], end=" ")
print() # new line使用类的图实现
存储图的更合适方法是使用类添加抽象层，以便图的顶点、边和相关方法（例如我们稍后将实现的算法）都包含在一个地方。
具有内置面向对象功能的编程语言（如 Python 和 Java）使得使用类实现图比没有此内置功能的语言（如 C）更容易。
及其邻接矩阵
以下是使用类实现上图中无向图的方法。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1) # A - B
g.add_edge(0, 2) # A - C
g.add_edge(0, 3) # A - D
g.add_edge(1, 2) # B - C
g.print_graph()在上面的代码中，我们为无向图获得的矩阵对称性在第 9 行和第 10 行提供，这在第 29 行到第 32 行初始化图中的边时节省了一些代码。
有向图和加权图的实现
为了实现一个有向且加权的图，我们只需要对之前无向图的实现进行一些更改。
要创建有向图，我们只需要删除前面示例代码中的第 10 行，这样矩阵就不会自动对称了。
我们需要做的第二个更改是在 add_edge() 方法中添加一个 weight 参数，这样一来，我们就可以使用实际的权重值来定义边，而不是仅用值 1 来指示两个顶点之间存在一条边。
及其邻接矩阵。
以下是上图中所示的有向且加权的图的实现。
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[None] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")
g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1, 3) # A -> B with weight 3
g.add_edge(0, 2, 2) # A -> C with weight 2
g.add_edge(3, 0, 4) # D -> A with weight 4
g.add_edge(2, 1, 1) # C -> B with weight 1
g.print_graph()第 3 行：所有边最初都设置为 None。
第 7 行：现在可以使用额外的 weight 参数将权重添加到边中。
第 10 行：通过删除第 10 行，图现在可以设置为有向图。
在下一页中，我们将看到如何遍历图，以及在接下来的几页中，我们将研究可以在图数据结构上运行的不同算法。
