It seems natural to use the GPUs (Graphical Processing Units) for performing analytics on big graphs, due to the notable boost in high performance computing that their introduction has determined and to the huge volume of connected data that is being gathered and processed nowadays. A parallel strategy to speed-up the visit of all nodes of a graph based on the precomputation of critical frontiers is proposed in this paper: step by step the critical frontiers are reused so that all threads work optimally. The resulting algorithm is an asynchronous hybrid between Breadth and Depth First Search (BFS and DFS), called HBDFS. Tests with both real and synthetic heterogeneous datasets show a consistent dominance of the proposed approach over the baseline parallel BFS, achieving up to a 30 times speed-up with just a 20% memory overhead