search

Azer0s / tinygraph

A tiny graph library for C++17
Apache License 2.0
2 stars 0 forks source link

Implement Breadth First Search (BFS) #5

Open Azer0s opened 4 years ago

Azer0s commented 4 years ago

Breadth First Search is one of the most simple graph algorithms. It traverses the graph by first checking the current node and then expanding it by adding its successors to the next level. The process is repeated for all nodes in the current level before moving to the next level. If the solution is found the search stops.

rudreshr17 commented 4 years ago

Hi! I know how to implement BFS algorithm in C++ using numeric data types. Are we going to use templates so as to allow any data type as value of node? Also, are there any prerequisites to contribute?

Azer0s commented 4 years ago

@rudreshr17 Hi! That's amazing! Yes, Edge actually already has a map (std::map<std::string, std::any>) for properties. As or weights, the vertices also have that map. In the future, one will be able to pass on the field name of the field where the weight of a vertex is. So for instance:

g->shortest_path_weighted<int>("PHX", "BKK", "distance");

Which means that the weight type is an int and the weight is stored in the vertex in the property map under the key distance.

As for prerequisites: no prerequisites, just do a PR ^^ Although #8 has the highest priority right now (I kinda want to sort out the basics before getting started with algorithms)