data-structures - 哪种图算法更喜欢邻接矩阵，为什么？

Question

我听说大多数图形算法(但不是全部)都使用邻接表。我只是想知道哪些算法更喜欢邻接矩阵，为什么？

到目前为止，我发现 Floyd Warshall 使用邻接矩阵。

Answer 1

在算法中，邻接列表通常比邻接矩阵更快，在这些算法中，每个节点执行的关键操作是“遍历与该节点相邻的所有节点”。对于邻接列表，这可以在时间 O(deg(v)) 时间内完成，其中 deg(v) 是节点 v 的度数，而在邻接矩阵中需要时间 Θ(n)。类似地，邻接列表可以快速迭代图中的所有边 - 与邻接矩阵的时间 Θ(n²) 相比，这样做需要时间 O(m + n)。

一些最常用的图算法(BFS、DFS、Dijkstra 算法、A* 搜索、Kruskal 算法、Prim 算法、Bellman-Ford、Karger 算法等)需要对所有边或边进行快速迭代特定节点的事件，因此它们最适合邻接列表。

您提到 Floyd-Warshall 使用邻接矩阵。虽然 Floyd-Warshall 确实维护了一个内部矩阵来跟踪目前看到的最短路径，但它实际上并不要求原始图是邻接矩阵。动态规划工作的总成本为 Θ(n³)，大于将邻接表转换为邻接矩阵的 O(n²) 成本或反之亦然。

只有少数地方邻接矩阵比邻接表快。邻接矩阵需要时间 O(1) 来测试图中是否存在特定边，这比邻接列表上相应操作的 O(deg(v)) 成本更快。由于将邻接列表转换为邻接矩阵的成本是 Θ(n²)，因此邻接矩阵优于邻接列表的唯一情况是 (1) 边的随机访问是必需的，并且 (2) 算法的总运行时间为 o(n²)。我只知道执行此操作的一些算法。例如，有 celebrity-finding problem给你一张图，要求你找出是否有一个节点，每个节点都有入边，出边没有节点。这可以使用邻接矩阵在时间 O(n) 内完成，比使用邻接表更快。

(话虽这么说，您也可以使用用 cuckoo hash tables 表示的邻接列表而不是常规列表，并匹配与上面相同的运行时边界，尽管现在创建邻接列表的成本只是预期 要快而不是实际上最坏情况下的效率。)

我发现邻接矩阵有用的主要原因是从不同的角度考虑图。例如，将邻接矩阵提高到 k 次方会生成一个新矩阵，该矩阵计算从一个节点到另一个节点的路径数，恰好使用 k 跳。这可以用于 count and find triangles in graphs faster than the naive algorithm ， 例如。同样，Four Russians algorithm用于计算图的传递闭包的方法是将图表示为矩阵，并使用一些巧妙的技术(将位 block 视为整数，然后在查找表中使用)以优于朴素搜索。

希望这对您有所帮助!