Time Complexity for finding edges in Adjacency Matrix in Graph

📚 Official Books Data Structures & Algorithms in Dart
1

In Chapter 20, Graphs, the Graph Analysis for Adjacency List and Matrix is provided.
The Time Complexity for Finding Edges in Adjacency Matrix is specified as O(1).

Although in the function edges(Vertex<E> source), we are going through the source Vertex row and getting the edges.
This should result in O(V), where V is the number of Vertices.

2

Ah, I think this is a case of the diagram and chapter being unclearly worded.

What you said about the edges method is correct. To find all of the edges for a particular vertex, you have to loop through all the values in a row. And since the row has the same length as the number of vertices, that makes it an O(V) operation.

What I was trying (unsuccessfully, it turns out) to express is that finding any particular edge is an O(1) operation in an adjacency matrix. An edge is the combination of a source, a destination, and a weight. Here is the weight method:

@override
double? weight(Vertex<E> source, Vertex<E> destination) {
  return _weights[source.index]?[destination.index];
}

It’s an O(1) operation to look up a weight from the two dimensional list. And since you’re already given the source and destination, once you have the weight, you essentially have an edge. That’s why in the complexity diagram edges and weight are grouped together. After reading your post, though, I see why this is misleading.

So thank you for posting. I’ll make a note to update this in the next edition. Unfortunately, since we just published Edition 2.0 (in which Graphs is Chapter 21), it probably won’t happen until next year. Thanks to your comment, though, other readers who browse the forums in the meantime will get the clarification here.

1 Like