正文

揭秘图的存储：深度解析邻接矩阵与邻接表的奥秘

/0 浏览量
0328

图是一种广泛用于描述实体之间关系的数据结构，在计算机科学、网络、人工智能等领域有着重要的应用。图的存储是图论研究的基础，其中邻接矩阵和邻接表是两种常见的图存储方式。本文将深入解析这两种存储方式的原理、优缺点以及适用场景。

邻接矩阵

原理

邻接矩阵是一种用二维数组表示的图存储方式。它的大小为 ( n \times n )，其中 ( n ) 是图中顶点的数量。矩阵的元素 ( a[i][j] ) 表示顶点 ( i ) 和顶点 ( j ) 之间是否存在边，如果存在边，则 ( a[i][j] ) 的值为边的权重，否则为无穷大或一个特殊的标记值。

代码示例

# 创建一个有5个顶点的无向图
graph = [[0 for _ in range(5)] for _ in range(5)]

# 添加边
graph[0][1] = 1
graph[1][0] = 1
graph[0][2] = 1
graph[2][0] = 1
graph[1][2] = 1

# 打印邻接矩阵
for row in graph:
    print(row)

优缺点

优点：

  • 邻接矩阵的存储结构简单，易于实现。
  • 可以快速判断两个顶点之间是否存在边。

缺点：

  • 空间复杂度高，对于稀疏图来说，空间利用率低。
  • 对于稠密图，查找边的操作时间复杂度为 ( O(n^2) )。

邻接表

原理

邻接表是一种用链表表示的图存储方式。它由一个顶点表和一个边表组成。顶点表中的每个元素包含一个顶点和与该顶点相连的所有边的链表。边表中每个元素表示一条边，包含两个顶点和一个指向邻接表的指针。

代码示例

class Node:
    def __init__(self, vertex):
        self.vertex = vertex
        self.next = None

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj_list = [None] * self.V

    def add_edge(self, v, w):
        # 添加边 v -> w
        new_node = Node(w)
        new_node.next = self.adj_list[v]
        self.adj_list[v] = new_node

        # 如果是无向图，添加边 w -> v
        new_node = Node(v)
        new_node.next = self.adj_list[w]
        self.adj_list[w] = new_node

    def print_graph(self):
        for i in range(self.V):
            print("Adjacency list of vertex", i)
            temp = self.adj_list[i]
            while temp:
                print("\t", temp.vertex)
                temp = temp.next

# 创建一个有5个顶点的无向图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)

# 打印邻接表
g.print_graph()

优缺点

优点：

  • 空间复杂度低，适用于稀疏图。
  • 查找边的操作时间复杂度为 ( O(V + E) )，其中 ( V ) 是顶点数，( E ) 是边数。

缺点：

  • 邻接表的结构比邻接矩阵复杂，不易于实现。
  • 邻接表不便于判断两个顶点之间是否存在边。

总结

邻接矩阵和邻接表是两种常见的图存储方式，它们各有优缺点。在实际应用中，应根据图的特点和需求选择合适的存储方式。对于稠密图，邻接矩阵是较好的选择；对于稀疏图，邻接表则更加高效。

-- 展开阅读全文 --