CODEWITHSUNDEEP
algorithm
aminy
aminy

Reputation: 489

how to speed up breadth-first-search in a undirected graph

I think we can use queue to do the breadth-first-search(BFS) traversal, and since add() and remove() in queue is constant time, so I think BFS traversal from a starting node to the target node is linear time.

But how to speed up BFS? is there a data structure that can reduce this time complexity?

Upvotes: 1

Views: 6510

Answers (2)

vonbrand
vonbrand

Reputation: 11791

The worst case time is linear in the number of nodes (and that can clearly be attained). You can speed up the search via heuristics, i.e., instead of adding the new nodes to a queue add them to a priority queue, where the priority is some measure of how near the new node seems to be to the goal.

Another way to speed it up is to work in paralell, i.e., farm out the queue of nodes to be processed to worker threads. But then you get the hassle of making sure no (or at least not too many) nodes get visited more than once.

Unless the graphs you are trying to process are truly huge, I wouldn't worry too much about this, there is little to be squeezed out here performance-wise. Measure where the bottlenecks of your system are, and concentrate on them. And do this only if the performance isn't enough, otherwise spend your time at the beach (or whatever you like to do best).

Upvotes: -1

amit
amit

Reputation: 178411

You can speed up BFS from a source to a target by doing a bi-directional search.

A bi-directional search is basically doing a BFS from the source and from the target at the same time, one step from each - until the two fronts meet each other.

Why is it better?

  • A BFS at worst case discovers O(B^d) nodes (B is the branch factor, the degree of each node) - and d is the depth fo the solution.
  • A bi-directional BFS at worst case discovers O(B^(d/2)*2)=O(B^(d/2)) nodes, which is usually much smaller

Empirically, a bi-directional search is usually faster than regular BFS for large/infinite graphs.

Upvotes: 4

Related Questions