Graph traversal based on algorithms such as depth-first search and breadth-first-search is a critical part of many applications. With the advent of multicore computers and the ability to furnish them with large shared random-access-memory, it has become possible to process large-scale graphs in parallel. For such parallel algorithms to be effective in general, they should be highly parallel, exposing as much parallelism as possible and remain work-efficient with respect to optimal serial graph-traversal algorithms. Since the topology of graphs can vary dramatically, simultaneously achieving these two properties is challenging.

In this paper, we present two highly parallel and work-efficient algorithms for performing graph traversals on directed (and undirected) graphs. Our first algorithm is a Parallel Breadth-First Search (PBFS) that improves over the state of the art by exposing more parallelism without detrimentally effecting work efficiency. Our second algorithm is a Parallel Depth-First Search (PDFS) algorithm that improves over the state of the art by guaranteeing work efficiency while remaining highly parallel. Both of our algorithms take advantage of our novel frontier data structure that supports very efficiently several key operations on the set of outgoing edges of visited vertices (the frontier), including push, iteration, split in half, and merge. Also based on this data structure, we present techniques for controlling granularity for improved practical efficiency.

We implement our algorithms and evaluate them carefully by considering both synthetic and real-world graphs and by comparing with the state of the art. The experiments show that, for the graphs considered, our algorithms remain robust, outperforming the state of the art except in a few cases, and dramatically outperforming them in certain cases.