Please, couold you suggest me a simple way to find a cycle into a graph (just a sentence, no code)? What about the computational complexity?

You really need to get the BGL book or read the online tutorial (see the documentation page for BGL - http://www.boost.org/libs/graph/doc). My explanation here will not do the algorithm justice, and there really is no "shortcut" - you do need to understand the concepts presented in that documentation. To find cycles, you start a recursive traversal starting at each "incomplete" vertex (node) in the graph, keeping track of what nodes you've visted. A "completed" vertex is one that has had all its outbound edges traversed both ways ("out and back"). The visitation traversal occurs in a Depth-First search manner, and the nodes "in progress" (i.e., all nodes in the paths originating with the current start node that is not yet completed - i.e., traversal is not finished/paths not exhaustively traversed) are marked in a distinct manner. If, while traversing the nodes, one is found with this distinct marking, then there is a cycle in the graph. There is also ways to determine the extent of the cycle (i.e., what edges and vertexes are involved/reachable in the cycle), and that is also discussed in the book. The computational complexity is based on the traversal - i.e., the complexity of the DFS - see the documentation - the cost is related to the actual graph type, I believe. HTH, Mike