I would like to inform all users of the boost system that as expected was my mistake. Infact, the library and the bfs.cpp work exactely as to be expected given the semantic of the methods used. The very patient and creative Jeremy have explained me in the meantime that I was using the wrong class type for my need. If I use the undirectedS instead of the bidirectionalS in the typedef of the adjacency_list, then I get exactely the behaviour and the result that I needed/expected. The mistake I was doing was to assume that "bidirectionalS" and "undirectedS" be the same thing. Indeed they are not. Again, a mistake of a beginner with very limited knowledge in graphs and very limited knowledge in C++. Thanks to your patience I got my wheel running now, and it is a powerful stimulus for adding depth to my knowledge. For this reason, I am now looking forward your excellent Graph book that I ordered yesterday. I will post on this mailing list as soon as the paper (describing the study which also makes use of the boost library) is accepted for publication. Regards Luca