我听说大多数图算法（但不是全部）中都使用了邻接表。我只是想知道哪种算法更喜欢邻接矩阵，为什么？
到目前为止，我发现Floyd Warshall使用邻接矩阵。
在算法中，邻接表通常比邻接矩阵更快，在邻接算法中，每个节点执行的关键操作“在与该节点相邻的所有节点上迭代”。对于邻接表，可以在时间O（deg（v））的时间内完成，其中deg（v）是节点v的度，而在邻接矩阵中则花费时间Θ（n）。类似地，邻接表可以快速遍历图形中的所有边缘-与邻接矩阵的时间Θ（n 2）相比，它需要花费时间O（m + n）。
一些最常用的图形算法（BFS，DFS，Dijkstra算法，A *搜索，Kruskal算法，Prim算法，Bellman-Ford，Karger算法等）要求在所有边或与特定边有关的边上进行快速迭代。节点，因此它们最适合与邻接列表一起使用。
您提到Floyd-Warshall使用邻接矩阵。尽管Floyd-Warshall确实维护了一个内部矩阵，该矩阵跟踪到目前为止所看到的最短路径，但实际上并不需要原始图形作为邻接矩阵。动态编程工作的总成本为Θ（n 3），大于将邻接表转换为邻接矩阵或反之亦然的O（n 2）成本。
仅有少数几个地方的邻接矩阵比邻接列表快。邻接矩阵需要时间O（1）来测试图中是否存在特定边，这比邻接表上相应操作的O（deg（v））成本要快。由于将邻接列表转换为邻接矩阵的成本为Θ（n 2），因此只有在（1）需要边缘的随机访问和（2）边缘随机访问的情况下，邻接矩阵才能胜过邻接列表。该算法的总运行时间为o（n 2）。我只知道几种算法可以做到这一点。例如，有名人发现问题在该图中，您会得到一个图形，并被要求查找是否有一个节点，其中每个节点的入站边都没有，而出站边则没有节点。可以使用邻接矩阵在时间O（n）内完成，比使用邻接表可以更快。
（话虽这么说，你也可以使用一个邻接表为代表的使用杜鹃哈希表，而不是常规列表和创建邻接表现在只有成本匹配相同的运行时间界限如上，但预计要快，而不是实际最差大小写有效。）
我发现邻接矩阵有用的主要原因是从不同角度考虑图。例如，将邻接矩阵提高到k次幂，就可以创建一个新矩阵，该矩阵使用恰好k个跃点来计数从一个节点到另一个节点的路径数。例如，它可以用于计算和查找图形中的三角形，其速度比朴素的算法快。类似地，用于计算图的传递闭合的四位俄罗斯人算法的工作原理是将图表示为矩阵，并使用一些聪明的技术（将位块作为整数处理，然后在查找表中使用）胜过朴素的搜索。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句