Adjacency lists are generally faster than adjacency matrices in algorithms in which the key operation performed per node is “iterate over all the nodes adjacent to this node.” That can be done in time O(deg(v)) time for an adjacency list, where deg(v) is the degree of node v, while it takes time Θ(n) in an adjacency matrix. Similarly, adjacency lists make it fast to iterate over all of the edges in a graph - it takes time O(m + n) to do so, compared with time Θ(n2) for adjacency matrices.
一些最常用的图算法（BFS、DFS、Dijkstra 算法、A* 搜索、Kruskal 算法、Prim 算法、Bellman-Ford、Karger 算法等）需要对所有边或与特定边相关的边进行快速迭代节点，因此它们最适合与邻接列表一起使用。
You mentioned that Floyd-Warshall uses adjacency matrices. While Floyd-Warshall does maintain an internal matrix tracking shortest paths seen so far, it doesn’t actually require the original graph to be an adjacency matrix. The overall cost of the dynamic programming work is Θ(n3), which is bigger than the O(n2) cost of converting an adjacency list into an adjacency matrix or vice-versa.
There are only a few places where an adjacency matrix is faster than an adjacency list. Adjacency matrices take time O(1) to test whether a particular edge is present in the graph, which is faster than the O(deg(v)) cost of the corresponding operation on an adjacency list. Since the cost of converting an adjacency list to an adjacency matrix is Θ(n2), the only cases where an adjacency matrix would outperform an adjacency list are in situations where (1) random access of the edges are required and (2) the total runtime of the algorithm is o(n2). I only know a few algorithms that do this. For example, there’s the celebrity-finding problem https://www.cs.princeton.edu/courses/archive/spring13/cos423/problem0-1.pdf where you’re given a graph and are asked to find whether there’s a node with incoming edges from each node and outgoing edges to no nodes. This can be done in time O(n) using an adjacency matrix, faster than what can be done with an adjacency list.
（话虽如此，您也可以使用使用以下表示的邻接列表布谷鸟哈希表 https://en.m.wikipedia.org/wiki/Cuckoo_hashing而不是常规列表并匹配与上面相同的运行时边界，尽管现在仅创建邻接列表的成本expected速度快而不是实际最坏情况下的效率。）
我发现邻接矩阵有用的主要原因是从不同的角度思考图。例如，将邻接矩阵求 k 次方会生成一个新矩阵，该矩阵精确地使用 k 跳来计算从一个节点到另一个节点的路径数。这可以用来比朴素算法更快地计算和查找图中的三角形 http://theory.stanford.edu/%7Evirgi/cs267/lecture1.pdf， 例如。同样，四俄罗斯人算法 https://en.m.wikipedia.org/wiki/Method_of_Four_Russians计算图的传递闭包的工作原理是将图表示为矩阵并使用一些巧妙的技术（将位块视为整数，然后在查找表中使用）来超越简单的搜索。
希望这可以帮助！
