Hyperspectral anomaly detection (AD) is an important problem in remote sensing field. It can make full use of the spectral differences to discover certain potential interesting regions without any target priors. Traditional Mahalanobis-distance-based anomaly detectors assume the background spectrum distribution conforms to a Gaussian distribution. However, this and other similar distributions may not be satisfied for the real hyperspectral images. Moreover, the background statistics are susceptible to contamination of anomaly targets which will lead to a high false-positive rate. To address these intrinsic problems, this paper proposes a novel AD method based on the graph theory. We first construct a vertex- and edge-weighted graph and then utilize a pixel selection process to locate the anomaly targets. Two contributions are claimed in this paper: 1) no background distributions are required which makes the method more adaptive and 2) both the vertex and edge weights are considered which enables a more accurate detection performance and better robustness to noise. Intensive experiments on the simulated and real hyperspectral images demonstrate that the proposed method outperforms other benchmark competitors. In addition, the robustness of the proposed method has been validated by using various window sizes. This experimental result also demonstrates the valuable characteristic of less computational complexity and less parameter tuning for real applications.