在数据结构和图论中，图的表示方法之一是邻接矩阵。邻接矩阵是一种简洁而强大的方式来表示图。每个元素 adj[i][j] 在矩阵中都表示了节点 i 和节点 j 之间的连接关系。本文是“数据结构编程实践：Python版”系列的第14讲，我们将详细讨论如何使用Python实现邻接矩阵。

什么是邻接矩阵？

邻接矩阵是一个二维数组，用于表示有限图。在这个矩阵中，行和列分别表示图的节点，对于无向图，如果节点 i 和 j 之间有连接，则 adj[i][j] 和 adj[j][i] 都被设置为1。对于有向图，仅 adj[i][j] 被设置为1，而 adj[j][i] 则设为0。如果图是加权的，矩阵中的每个条目可能包含边的权重。

邻接矩阵的实现

我们来实现一个简单的邻接矩阵来表示图。首先，我们定义一个类来封装邻接矩阵的行为。

class Graph:  
    def __init__(self, num_vertices):  
        self.num_vertices = num_vertices  
        self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]  
    def add_edge(self, start, end, weight=1):  
        # 对于无向图，设置两个方向  
        self.adj_matrix[start][end] = weight  
        self.adj_matrix[end][start] = weight  
    def remove_edge(self, start, end):  
        # 对于无向图，清除两个方向的连接  
        self.adj_matrix[start][end] = 0  
        self.adj_matrix[end][start] = 0  
    def has_edge(self, start, end):  
        return self.adj_matrix[start][end] != 0  
    def display(self):  
        for row in self.adj_matrix:  
            print(row)  
# 使用示例  
if __name__ == "__main__":  
    g = Graph(4)  
    g.add_edge(0, 1)  
    g.add_edge(1, 2)  
    g.add_edge(2, 3)  
    g.display()  

特点

1. 空间复杂度：邻接矩阵需要 O(V^2) 的空间，其中 V 是节点的数量。因此，对于大图（稀疏图），邻接矩阵可能不是最具效益的存储方式。

2. 时间复杂度：

   • 检查两个节点是否相连：O(1)
   • 添加/删除边：O(1)

3. 表示简单：易于实现，并且表示清晰直观。

应用场景

• 邻接矩阵适用于图节点较少或图较为稠密的场合。
• 因为检索连接关系的时间复杂度是常数级别的，因此在需要快速查询两个节点之间是否有边存在时特别有效。

通过这种方式，你可以用Python实现一个简单有效的邻接矩阵来表示图结构。这种表示方法虽然空间复杂度较高，但在有需要时，其简单的实现和快速查询能力仍然十分有用。希望这篇文章对你理解和使用邻接矩阵有所帮助！