Skip to content

Latest commit

 

History

History
24 lines (19 loc) · 1.55 KB

README.md

File metadata and controls

24 lines (19 loc) · 1.55 KB
Raw

Graph Algorithms

Implemented Breadth First Search (BFS) algorithm when traversing through tree or graph data structures when searching for the nearest hospital in a locality map

Problem Statement

In a given number of nodes (i.e. the locality map), traverse the neighbouring nodes to find the nearest hospital nodes from a starting node

Functionality

  1. Implemented the BFS algorithm to find the nearest hospital node by controlling the following variables: Total number of nodes (n), Number of hospitals (h), Number of hospitals to be searched (k)
  2. BFS search is carried out level-by-level (i.e. by searching through all adjacent nodes first before proceeding to the next level)

Conclusion

  1. When n is small, the time taken is relatively the same but increases rapidly when k is higher (e.g. finding the two nearest hospitals or more). This supports the theoretical worst-case time complexity of O(kh+km)
  2. Initial increase of h results in a significant decrease in the time taken, but little to none when h becomes too big
  3. Time take increases exponential as k increases as we have to find more and more closest hospital nodes to the starting node

Documentation

  1. Full detailed report of the project: CZ2001 Project 2.pdf
  2. Summary and presentation of the project: CZ2001 Project 2.pptx

Developed by:

  1. Ang Shu Hui
  2. Bachhas Nikita
  3. Kundu Koushani
  4. Leonardo Irvin Pratama