0
$\begingroup$

I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related (connected).

Now, at a certain point, there's a question:

How can you organize an edge list to make searching for a particular edge take O(lg E) time?

I was thinking to the trivial solution of sorting, but it is not so easy to sort a list of edges. For example, let the following be our initial list of edges: 

[[3, 2], [1, 2], [1, 3]]

Now, if we try to sort it by using the first vertex, we obtain:

[[1, 3], [1, 2], [3, 2]]

I am not visualizing well if this search would be O(lg E), where E is the number of edges.

Could you please explain how could we organize the edges in order to have a edge searching algorithm with a time complexity of O(lg E)? And why it should be O(lg E)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Any total order will do; more is not needed for sorting and searching with binary search in a sorted list.

The lexicographic order would be a canonical choice for sorting tuples.

If your elements are (unordered) sets (e.g. edges of undirected graphs) you can sort them before comparing by the order on tuples as well.

Improve this answer
$\endgroup$