In this chapter, we consider the applicability of a non-traditional massively multithreaded architecture, the Cray MTA-2 [13], as a platform for graph algorithms. Graph-theoretic problems have emerged as a prominent computational workload in the petascale computing era, and are representative of fundamental kernels in biology, scientific computing, and applications in national security. However, they pose serious challenges on current parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality [35]. We present multithreaded algorithms for two fundamental graph problems – single source shortest paths and connected components – that are designed for processing large-scale, unstructured graph instances.