bfs dfs num islands max island

Breadth first search visualization

Speed

Obstacles

 

Controls

Speed - increase or decrease the speed of the visualization

Obstacles- - create walls/obstacles, on a map these can be buildings or structures which hinder a path. You can adjust the number of obstacles generated per click.
- You can also click on the grid cells to create obstacles.

Start - After adjusting the speed and creating obstacles, you can now start the visualization to see the workings of the algorithm.

Clear Path - After visualizing, you may opt to clear the path and add more obstacles.

Speed - If the grid becomes to cluttered you can reload it and repeat the above steps.

 
This is an empty path without any walls, you can click is to add obstacles/walls.
A
 
Start Node -> this is the starting point(source), search for a path starts here.
B
 
End Node -> where the search stops when a path to destination has been found
 
These act as obstacles, walls. On a real map these may be buildings or structures that may block a shorter path to a destination.
7
 
After the algorithm is complete, we have arrived at the destination, now the shortest path is highlighted in green with the cost of path written in black inside the path.

Breadth first traversal

This algorithm starts from a chosen node(source) and examines all its neighbors, then it examines all the neighbors of the neighbors, and etcetera.
The algorithm can be understood as a "fire spreading" on the graph, at the 0th step only the source is on fire. At each step, the buring fire at each vertex spreads to all its neighbors.
The ring of fire is expanded at each iteration. We use a queue data structure.

Algorithm

1. Add root node to the queue, and mark it as visited(already explored).

2. Loop through the queue as long as it's not empty do the following.

1. Get and remove the node at the top of the queue(current).

2. For every non-visited child of the current node, do the following:

1. Mark it as visited.

2. Check if it's the destination node, If so, then return and terminate.

3. Otherwise, push it to the queue.

3. If queue is empty, then no path exists!

Computational complexity

This algorithm takes O(V + E) where V is the number of vertices and E is the number of edges.

Applications

  • peer to peer networking
  • search engine crawlers
  • social networking websites
  • maps and gps navigation software
  • cycle detection in undirected graph
  • bipartite graph testing
  • spotting connected components

References

bfs