BFS Traversal

Use a Queue or PriorityQueue for traversal.

Can be used to find the shortest paths in graphs.

If negative edges are present keep calling update  V-1 (V is the number of vertices) to get the shortest path. If on Vth iteration the distances still reduce that means there are -ve cycles.

Implementation Note:

Queue can be implemented using an array. children for j are 2j+1 & 2j+2 (0 based index) and parent of j is floor(j/2) if j is odd or floor(j/2) -1 if j is even. This is better for dense graphs.

Binary Heap based implementation. This is better for sparse graph’s. insert/decrease key is log(V) and deleteMin is log(V)

Java Priority Queue has no provision for decreasing the key and is based on array implementation.

one set of methods (peek, poll) return nul if no element and (remove, element) throw NoSuchElement if no element is present when operation is performed.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s