图算法-边表到邻接表或邻接矩阵

Question

当使用图算法时，似乎大部分的解都是根据图的邻接表或邻接矩阵表示给出的。

但是，我认为leetcode中的大多数问题都是作为边缘列表提供的。由于大多数解都是不使用边表的，所以把边表转换成邻接表或邻接矩阵是个好主意吗？是否建议使用边缘列表解决所有问题？以下是一些与图有关的基本问题：

1. 循环检查图
2. 查找图中两个节点间的路径
3. 找到图

中两个节点之间的最短路径

Answer 1

这要看情况了！

对于大型稀疏图(即节点多，边少)，邻接矩阵占用大量内存，而邻接列表不消耗内存。

如果您处理的是小图(<1000个节点)或具有更多边的大图，那么您使用的是什么并不重要。

以上假设您有一个有效的数据结构和良好的设计。

Answer 2

如果我正确理解，边列表只是一个没有特定顺序的顶点对列表，而邻接列表是一个众所周知的数据结构，其中列表中的每个项都包含一个源顶点和该源目标顶点的嵌套列表。

从这个意义上说，邻接列表只是一个更好的结构:它占用更少的空间，并且遍历特定顶点的外边是很简单的(与搜索相反，即使它是通过排序的边列表进行的二进制搜索)。

所以要回答这个问题，是的，把边列表转换成邻接列表是个好主意，除非用简单的边列表来解决这个问题很简单。

至于邻接矩阵:它们有一些优点，比如引用的局部性，以及在某些情况下，它们可以被包装得比邻接列表小。