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)?

$\endgroup$
2
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy