I'm trying to understand better the advantages of using the adjacency matrix (AM) graph representation, in the context of time complexity of graph algorithms (I know, AM is quadratic in space, but let's forget space issues in this question).
AM enables checking the existence of an arbitrary edge in a given graph in O(1) time. This is essentially the main asymptotic advantage over the adjacency list/array graph representation (which needs O(log(max-degree)) for checking edge existence, assuming neighbors of each vertex are stored in sorted arrays).
Now, I'm interested in understanding whether this has any real meaning in the context of the time complexity of different graph algorithms. Namely, are there graph algorithms that benefit from this property of the AM, and have better asymptotic behavior when they use AM, instead of the adjacency list/array representation?
(By the way, I know that in various algorithms you can get better time complexity because you manipulate with the AM using linear algebra operations (squaring the matrix, etc.). I do not mean this here. Instead, I'm exclusively interested in what algorithms benefit from the AM ability to verify the existance of an edge in O(1) time).
Thank you!