为啥edges数组不能用来存储图

Question

数据结构中 图的存储方式有邻接链表和邻接矩阵，但是一些题目中会用edges数组来表示图 比如

为什么不能用这种方式来表示图 求解答

Answer 1

引自免费微信小程序：皆我百晓生

在数据结构中，确实存在多种方式来表示图（Graph），包括邻接链表、邻接矩阵以及边集数组（Edge List）。您提到的“edges数组”实际上就是边集数组的一种表示形式，并且完全能够用来存储图的数据结构。

为什么 edges 数组可以用来表示图：

1. 边集数组表示法： 边集数组是一种简洁的方式来记录图中的每条边。它以数组的形式存储所有边，每一条边通常由两个顶点构成，如 (u, v) 表示从顶点 u 到顶点 v 的一条边。例如：

   edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
   

   这个例子表示一个有4个顶点的无向图，其中顶点0与顶点1和2相连，顶点1与顶点2相连，顶点2与顶点3相连。

边集数组的特点及优缺点：

• 优点：

  • 空间效率高：对于稀疏图（即边的数量远小于顶点数量的平方）来说，这种方式占用的空间较小。
  • 描述灵活：可以直接添加或删除边，便于动态操作。

• 缺点：

  • 查询某个顶点的所有邻接点速度较慢，需要遍历整个数组。
  • 不直观地反映顶点之间的直接连接关系，不利于实现某些特定算法，如判断两点之间是否有路径等。

总结： 所以，edges 数组完全可以用来表示图，尤其适合于存储稀疏图。尽管在查询邻接信息时效率相对较低，但在实际应用中，根据具体需求选择合适的图存储方法是非常重要的。