数据结构中的邻接矩阵

一、概念

        邻接矩阵（Adjacency Matrix）是图（Graph）的一种表示方法，用于描述图中顶点之间的连接关系。它是一种常见的数据结构，特别适用于表示稠密图（即边数接近于顶点数平方的图）。

在图论中，图由顶点（Vertices）和边（Edges）组成。根据图的类型（有向图或无向图），邻接矩阵的定义略有不同：

• 无向图：对于无向图，邻接矩阵是对称的，即 A[i][j]=A[j][i]。如果顶点 i 和顶点 j 之间有一条边，则邻接矩阵的元素 A[i][j] 和 A[j][i] 都为1，否则为0。
• 有向图：对于有向图，邻接矩阵不一定对称。如果有一条从顶点 i 到顶点 j 的有向边，则邻接矩阵的元素 A[i][j] 为1，否则为0。

        邻接矩阵是一个 n×n 的矩阵，其中 n 是图中顶点的数量。矩阵中的每个元素 A[i][j] 表示顶点 i 和顶点 j 之间的连接关系。邻接矩阵的优点是查询顶点之间是否存在边的时间复杂度为O(1)，但缺点是空间复杂度较高，为O(n2)，不适合表示稀疏图（即边数远小于顶点数平方的图）。

二、原理及特性

1、矩阵构建规则

• 顶点映射：将图的每个顶点分配唯一索引（如 0,1,...,n−1）。

• 对称性：无向图的邻接矩阵是对称矩阵（A[i][j]=A[j][i]），而有向图不一定对称。

• 自环边：若允许顶点到自身的边，则对角线元素 A[i][i] 可能非零。

2、空间复杂度

• 邻接矩阵的空间复杂度为，其中 n 为顶点数。

• 适合稠密图（边数接近顶点数的平方），但对稀疏图（边数远小于顶点数平方）会造成空间浪费。

3、时间复杂度

三、python实现

1、无向图的邻接矩阵

class UndirectedGraph:
    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, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        self.adj_matrix[i][j] = 1
        self.adj_matrix[j][i] = 1

    def remove_edge(self, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        self.adj_matrix[i][j] = 0
        self.adj_matrix[j][i] = 0

    def has_edge(self, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        return self.adj_matrix[i][j] == 1

    def display(self):
        for row in self.adj_matrix:
            print(row)

# 示例使用
graph = UndirectedGraph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(3, 4)

print("邻接矩阵:")
graph.display()

print("顶点 0 和 1 之间是否有边:", graph.has_edge(0, 1))
print("顶点 0 和 3 之间是否有边:", graph.has_edge(0, 3))

2、有向图的邻接矩阵

class DirectedGraph:
    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, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        self.adj_matrix[i][j] = 1

    def remove_edge(self, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        self.adj_matrix[i][j] = 0

    def has_edge(self, i, j):
        if i >= self.num_vertices or j >= self.num_vertices:
            raise ValueError("Vertex index out of bounds")
        return self.adj_matrix[i][j] == 1

    def display(self):
        for row in self.adj_matrix:
            print(row)

# 示例使用
graph = DirectedGraph(5)
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(3, 4)

print("邻接矩阵:")
graph.display()

print("顶点 0 和 1 之间是否有边:", graph.has_edge(0, 1))
print("顶点 0 和 3 之间是否有边:", graph.has_edge(0, 3))