图算法疑问：Edge List转Adjacency List/Matrix是否更适合解题？

转换为邻接表/邻接矩阵更合理吗？ #

答案是肯定的，绝大多数场景下转换后处理效率会高很多。边列表本质就是一堆边的集合，没直接体现节点的邻接关系——每次要查某个节点的邻居，都得遍历整个边列表，时间复杂度是O(E)，这在边数多的问题里会拖慢速度。而邻接表（或邻接矩阵）提前把节点的邻接关系组织好了，查邻居的时间复杂度能降到O(1)（邻接矩阵）或者O(节点度数)（邻接表，度数通常远小于总边数E）。

能直接用边列表解决所有图问题吗？ #

绝对不推荐。理论上确实能做，但在LeetCode这类要求效率的场景里，直接用边列表会让很多算法的时间复杂度飙升，大概率超时。结合你提到的三个典型问题具体说：

1. 图的环检测 #

• 用邻接表/邻接矩阵：无向图用并查集，效率接近O(E)（并查集的路径压缩和按秩合并后，时间复杂度里的常数项极小）；有向图用DFS或BFS，时间复杂度O(N+E)，都很高效。
• 直接用边列表：无向图用并查集还能凑活，但有向图做环检测时，每次找节点的出边都得遍历所有边，整体时间复杂度会变成O(E*(N+E))，边数多的话直接卡超时。

2. 查找两节点间路径 #

• 用邻接表/邻接矩阵：DFS或BFS都是标准操作，遍历的时候直接取节点邻居就行，时间O(N+E)。
• 直接用边列表：每次找当前节点的邻居都得扫一遍所有边，比如BFS每一层都要遍历E条边，整体时间复杂度变成O(N*E)，节点数和边数过千的话基本没法通过。

3. 查找两节点间最短路径 #

• 用邻接表：无向无权图用BFS，O(N+E)；有权图用Dijkstra算法（配合优先队列），O(E logN)；负权图用Bellman-Ford也能基于邻接表优化步骤。
• 直接用边列表：BFS的时间直接炸到O(N*E)；Dijkstra算法几乎没法高效实现，因为没法快速获取节点的邻接边；Bellman-Ford虽然能直接用边列表，但本身时间复杂度就是O(N*E)，比邻接表版本慢不少，稀疏图里差距更明显。

少数例外 #

当然也有个别场景可以直接用边列表，比如无向图的并查集相关问题（判断连通分量、环检测），或者只需要遍历所有边一次的简单问题（比如算所有边的权重和）。但这类情况是少数，大部分图问题还是转成邻接表更靠谱。

内容的提问来源于stack exchange，提问作者Ecnoir