CODEWITHSUNDEEP
algorithmdata-structuresgraphdepth-first-searchbreadth-first-search
The Lazy Programmer
The Lazy Programmer

Reputation: 125

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

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]]

Upvotes: 3

Views: 3962

Answers (2)

ARK
ARK

Reputation: 4074

If you know the nodes(n), then create adjancency list using the edge list. That is O(n). Then do DFS which is O(V+E).

Having the right data structure makes the difference.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59303

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.

Upvotes: 4

Related Questions