我听说在大多数图算法中使用了邻接表（但并非全部）。我想知道哪些算法更喜欢邻接矩阵，以及为什么？
迄今为止，我发现 Floyd Warshall 算法使用邻接矩阵。
1个回答
10
邻接表通常比邻接矩阵在算法中更快，其中每个节点执行的关键操作是“迭代与此节点相邻的所有节点”。对于邻接表，可以在时间O(deg(v))内完成，其中deg(v)是节点v的度，而在邻接矩阵中需要Θ(n)的时间。同样，邻接表使得快速迭代整个图中的所有边变得容易 - 它只需要将时间花费O(m + n)，而邻接矩阵需要Θ(n2)的时间。
一些最常用的图算法（BFS、DFS、Dijkstra算法、A*搜索、Kruskal算法、Prim算法、Bellman-Ford、Karger算法等）需要快速迭代所有边或边缘与特定节点相交，因此它们最适合使用邻接表。
您提到Floyd-Warshall使用邻接矩阵。虽然Floyd-Warshall确实维护内部矩阵以跟踪迄今为止看到的最短路径，但它实际上不需要原始图形是邻接矩阵。动态编程工作的总成本是Θ(n3)，这比将邻接表转换为邻接矩阵或反之亦然的O(n2)成本要高。
只有少数情况下邻接矩阵比邻接表更快。邻接矩阵需要O（1）的时间来测试图中是否存在特定边，这比邻接表上对应操作的O（deg（v））成本更快。由于将邻接表转换为邻接矩阵的成本是Θ（n²），因此邻接矩阵优于邻接表的唯一情况是在需要（1）随机访问边缘并且（2）算法的总运行时间为o（n²）的情况下。我只知道很少几个可以做到这一点的算法。例如，有名人找问题，其中给出一个图，并要求查找是否存在一个节点，该节点具有从每个节点传入的边缘和传出到没有节点的边缘。这可以使用邻接矩阵在O（n）的时间内完成，比邻接表更快。
（话虽如此，您也可以使用使用cuckoo hash tables来表示邻接表，而不是常规列表，并匹配与上面相同的运行时限制，尽管创建邻接表的成本现在只有预期快而不是实际最坏情况下高效。）
我发现邻接矩阵有用的主要原因是从不同的角度思考图形。例如，将邻接矩阵提高到第k次方会产生一个新矩阵，该矩阵计算使用恰好k个跳跃从一个节点到另一个节点的路径数。例如，这可以用于比朴素算法更快地计算和查找图中的三角形。类似地，用于计算图的传递闭包的Four Russians algorithm通过将图表示为矩阵并使用一些巧妙的技术（将位块视为整数然后在查找表中使用）来超越朴素搜索。
希望这可以帮助！
一些最常用的图算法（BFS、DFS、Dijkstra算法、A*搜索、Kruskal算法、Prim算法、Bellman-Ford、Karger算法等）需要快速迭代所有边或边缘与特定节点相交，因此它们最适合使用邻接表。
您提到Floyd-Warshall使用邻接矩阵。虽然Floyd-Warshall确实维护内部矩阵以跟踪迄今为止看到的最短路径，但它实际上不需要原始图形是邻接矩阵。动态编程工作的总成本是Θ(n3)，这比将邻接表转换为邻接矩阵或反之亦然的O(n2)成本要高。
只有少数情况下邻接矩阵比邻接表更快。邻接矩阵需要O（1）的时间来测试图中是否存在特定边，这比邻接表上对应操作的O（deg（v））成本更快。由于将邻接表转换为邻接矩阵的成本是Θ（n²），因此邻接矩阵优于邻接表的唯一情况是在需要（1）随机访问边缘并且（2）算法的总运行时间为o（n²）的情况下。我只知道很少几个可以做到这一点的算法。例如，有名人找问题，其中给出一个图，并要求查找是否存在一个节点，该节点具有从每个节点传入的边缘和传出到没有节点的边缘。这可以使用邻接矩阵在O（n）的时间内完成，比邻接表更快。
（话虽如此，您也可以使用使用cuckoo hash tables来表示邻接表，而不是常规列表，并匹配与上面相同的运行时限制，尽管创建邻接表的成本现在只有预期快而不是实际最坏情况下高效。）
我发现邻接矩阵有用的主要原因是从不同的角度思考图形。例如，将邻接矩阵提高到第k次方会产生一个新矩阵，该矩阵计算使用恰好k个跳跃从一个节点到另一个节点的路径数。例如，这可以用于比朴素算法更快地计算和查找图中的三角形。类似地，用于计算图的传递闭包的Four Russians algorithm通过将图表示为矩阵并使用一些巧妙的技术（将位块视为整数然后在查找表中使用）来超越朴素搜索。
希望这可以帮助！
- templatetypedef
3
这是一个很棒的回答！谢谢。 - Tran Anh Minh
m和n代表什么？ - johan
3@johan，在图算法中的惯例是n表示图中节点的数量，m表示边的数量。 - templatetypedef
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接