Afternoon,
Will the implementation you require be run on multiple different machines or will it be limited to specific ones? There are versions of the BF algorithm that can run in parallel, either on your CPU or GPU using CUDA. If you have a target platform/specs for it to run on, I can tailor this for you. Obviously the more cores or better your graphics card, the faster you can find your solution.
In the example you provided, the vertices are hard-coded into the program - are you wanting the implementation as a standalone library you will access yourself from within a C++ program or do you require the program to read in a file containing the graph in a specific format?
If you provide a larger sample set I can provide benchmarks for you to see if they are acceptable.
Regards,
Matt