图的邻接矩阵算法实现

引言

在图论中，图是一种由节点（或顶点）和边组成的非线性数据结构。图的应用非常广泛，包括社交网络、计算机网络、交通系统等。为了方便对图进行操作与分析，我们常常需要使用一些数据结构来存储图的信息，邻接矩阵就是其中一种重要的表示方式。

邻接矩阵的概念

定义

邻接矩阵是一种二维数组，用来表示图中节点之间的连接关系。对于一个有向或无向图 (G = (V, E))，其邻接矩阵 (A) 是一个 (|V| \times |V|) 的方阵，其中 (|V|) 表示图的顶点数。

• 元素定义：如果节点 (v_i) 和节点 (v_j) 之间存在边（无向图中的双向连接），则矩阵中对应位置 (A[i][j]) 或 (A[j][i]) 的值为1；对于有向图，若从节点 (v_i) 到节点 (v_j) 存在一条边，则仅 (A[i][j] = 1)。如果不存在这样的连接，则对应的矩阵元素值设为0。

特点

• 直观性：邻接矩阵能直接反映每一对顶点之间的关系。
• 存储效率：对于稀疏图（即存在大量没有边的节点对），邻接矩阵可能会浪费大量的内存空间，因为许多位置被填充了0。
• 操作简便：查找两个顶点之间是否存在连接非常快速。

邻接矩阵的实现

基本结构

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

这里我们定义了一个图类 Graph，包含一个初始化方法。构造函数中传入顶点数作为参数，并创建了一个大小为 (|V|\times |V|) 的二维数组来表示邻接矩阵。

添加边

def add_edge(self, v1, v2):
    self.adj_matrix[v1][v2] = 1
    # 对于有向图，可以不添加这一行。如果需要双向连接，则应同时在 adj_matrix[v2][v1] 中设置为1。

此方法用于添加边。当调用 add_edge 方法并传入两个顶点的索引时，相应位置会被设置为1。

删除边

def remove_edge(self, v1, v2):
    if self.adj_matrix[v1][v2] == 0:
        print("No edge between the vertices")
        return
    self.adj_matrix[v1][v2] = 0

此方法用于删除边。首先检查该位置是否已经为零，即原本不存在一条连接的边；如果存在，则将对应位置设置为0。

检查相邻节点

def is_adjacent(self, v1, v2):
    return self.adj_matrix[v1][v2] == 1

此方法用于检查两个顶点之间是否存在直接连接。返回值表示是否有边连接这两个顶点。

结论

邻接矩阵是一种简单且直观的图结构表示方法，适用于各种图的操作和分析任务。尽管对于稀疏图而言它可能会占用较多的存储空间，但在某些应用场景中（例如完全图），其优势更为明显。通过上述实现代码示例，我们可以清晰地看到如何在程序中使用邻接矩阵来模拟图，并进行基本操作。