Thanks to their non-volatile and multi-bit properties, memristors have been extensively used as synaptic weight elements in neuromorphic architectures. However, their use to define and re-program the network connectivity has been overlooked. Here, we propose, implement and experimentally demonstrate Mosaic, a neuromorphic architecture based on a systolic array of memristor crossbars. For the first time, we use distributed non-volatile memristors not only for computation, but also for routing (i.e., to define the network connectivity). Mosaic is particularly well-suited for the implementation of re-configurable small-world graphical models, with dense local and sparse global connectivity - found extensively in the brain. We mathematically show that, as the networks scale up, the Mosaic requires less memory than in conventional memristor approaches. We map a spiking recurrent neural network on the Mosaic to solve an Electrocardiogram (ECG) anomaly detection task. While the performance is either equivalent or better than software models, the advantage of the Mosaic was clearly seen in respective one and two orders of magnitude reduction in energy requirements, compared to a micro-controller and address-event representation-based processor. Mosaic promises to open up a new approach to designing neuromorphic hardware based on graph-theoretic principles with less memory and energy.