How to perform DFS or BFS when the edge list is given?

Question

How can I perform DFS or BFS when only an edge list is given?

I know how to do it when an adjacency list or an adjacency matrix is given and I also know how to convert an edge list to an adjacency list or adjacency matrix, but I want to do DFS or BFS straight from the edge list.

[[1,2],[2,3],[3,4],[1,4],[1,5]]

Answer 1

Assuming this is a directed graph, you can sort the edge list by source edge, and then make a map of the starting or ending position in the list for each source. You effectively get an adjacency list representation without recreating the whole data structure.

The sort can be done in O(N) time with an in-place counting sort like this one: Counting sort implementation that modifies the input array, which conveniently produces the map of ending positions as a side effect.