哪种图算法更喜欢邻接矩阵，为什么？
Which Graph Algorithms prefer adjacency matrix and why?
我听说大多数图形算法（但不是全部）都使用邻接表。我只是想知道什么算法更喜欢邻接矩阵，为什么？
到目前为止，我发现 Floyd Warshall 使用邻接矩阵。
在算法中，邻接列表通常比邻接矩阵更快，在这些算法中，每个节点执行的关键操作是“遍历与该节点相邻的所有节点”。对于邻接列表，这可以在时间 O(deg(v)) 时间内完成，其中 deg(v) 是节点 v 的度数，而在邻接矩阵中需要时间 Θ(n)。类似地，邻接列表可以快速迭代图中的所有边 - 与时间 Θ(n2) 相比，这样做需要时间 O(m + n)邻接矩阵。
一些最常用的图算法（BFS、DFS、Dijkstra 算法、A* 搜索、Kruskal 算法、Prim 算法、Bellman-Ford、Karger 算法等）需要对所有边进行快速迭代或特定节点的边缘，因此它们最适合邻接列表。
您提到 Floyd-Warshall 使用邻接矩阵。虽然 Floyd-Warshall 确实维护了一个内部矩阵来跟踪目前看到的最短路径，但它实际上并不要求原始图是邻接矩阵。动态规划工作的总成本为 Θ(n3)，大于转换邻接的 O(n2) 成本列表到邻接矩阵或反之亦然。
只有少数地方邻接矩阵比邻接表快。邻接矩阵需要时间 O(1) 来测试图中是否存在特定边，这比邻接列表上相应操作的 O(deg(v)) 成本更快。由于将邻接列表转换为邻接矩阵的成本是 Θ(n2)，因此邻接矩阵优于邻接列表的唯一情况是 (1) 随机访问的边缘是必需的，并且 (2) 算法的总运行时间是 o(n2)。我只知道执行此操作的一些算法。例如，在 celebrity-finding problem 中，你会得到一个图，并被要求找出是否存在一个节点，每个节点都有入边，出边没有节点。这可以使用邻接矩阵在时间 O(n) 内完成，比使用邻接列表更快。
（也就是说，您也可以使用使用 cuckoo hash tables 表示的邻接列表而不是常规列表，并匹配与上述相同的运行时边界，尽管现在创建邻接列表的成本仅为 预期 是快速的而不是实际上最坏情况下的效率。）
我发现邻接矩阵有用的主要原因是从不同的角度考虑图。例如，将邻接矩阵提高到 k 次方会生成一个新矩阵，该矩阵计算从一个节点到另一个节点的路径数，恰好使用 k 跳。这可用于 count and find triangles in graphs faster than the naive algorithm, for example. Similarly, the Four Russians algorithm 计算图的传递闭包，通过将图表示为矩阵并使用一些巧妙的技术（将位块视为整数，然后在查找中使用 table）来超越天真的搜索。
希望对您有所帮助！
我听说大多数图形算法（但不是全部）都使用邻接表。我只是想知道什么算法更喜欢邻接矩阵，为什么？
到目前为止，我发现 Floyd Warshall 使用邻接矩阵。
在算法中，邻接列表通常比邻接矩阵更快，在这些算法中，每个节点执行的关键操作是“遍历与该节点相邻的所有节点”。对于邻接列表，这可以在时间 O(deg(v)) 时间内完成，其中 deg(v) 是节点 v 的度数，而在邻接矩阵中需要时间 Θ(n)。类似地，邻接列表可以快速迭代图中的所有边 - 与时间 Θ(n2) 相比，这样做需要时间 O(m + n)邻接矩阵。
一些最常用的图算法（BFS、DFS、Dijkstra 算法、A* 搜索、Kruskal 算法、Prim 算法、Bellman-Ford、Karger 算法等）需要对所有边进行快速迭代或特定节点的边缘，因此它们最适合邻接列表。
您提到 Floyd-Warshall 使用邻接矩阵。虽然 Floyd-Warshall 确实维护了一个内部矩阵来跟踪目前看到的最短路径，但它实际上并不要求原始图是邻接矩阵。动态规划工作的总成本为 Θ(n3)，大于转换邻接的 O(n2) 成本列表到邻接矩阵或反之亦然。
只有少数地方邻接矩阵比邻接表快。邻接矩阵需要时间 O(1) 来测试图中是否存在特定边，这比邻接列表上相应操作的 O(deg(v)) 成本更快。由于将邻接列表转换为邻接矩阵的成本是 Θ(n2)，因此邻接矩阵优于邻接列表的唯一情况是 (1) 随机访问的边缘是必需的，并且 (2) 算法的总运行时间是 o(n2)。我只知道执行此操作的一些算法。例如，在 celebrity-finding problem 中，你会得到一个图，并被要求找出是否存在一个节点，每个节点都有入边，出边没有节点。这可以使用邻接矩阵在时间 O(n) 内完成，比使用邻接列表更快。
（也就是说，您也可以使用使用 cuckoo hash tables 表示的邻接列表而不是常规列表，并匹配与上述相同的运行时边界，尽管现在创建邻接列表的成本仅为 预期 是快速的而不是实际上最坏情况下的效率。）
我发现邻接矩阵有用的主要原因是从不同的角度考虑图。例如，将邻接矩阵提高到 k 次方会生成一个新矩阵，该矩阵计算从一个节点到另一个节点的路径数，恰好使用 k 跳。这可用于 count and find triangles in graphs faster than the naive algorithm, for example. Similarly, the Four Russians algorithm 计算图的传递闭包，通过将图表示为矩阵并使用一些巧妙的技术（将位块视为整数，然后在查找中使用 table）来超越天真的搜索。
希望对您有所帮助！