Intrusion detection systems that make use of artificial intelligence techniques in order to improve effectiveness have been actively pursued in the last decade. However, their complexity to learn new attacks has become very expensive, making them inviable for a real time retraining. In order to overcome such limitations, we have introduced a new pattern recognition technique called optimum- path forest (OPF) to this task. Our proposal is composed of three main contributions: to apply OPF for intrusion detection, to identify redundancy in some public datasets and also to perform feature selection over them. The experiments have been carried out on three datasets aiming to compare OPF against Support Vector Machines, Self Organizing Maps and a Bayesian classifier. We have showed that OPF has been the fastest classifier and the always one with the top results. Thus, it can be a suitable tool to detect intrusions on computer networks, as well as to allow the algorithm to learn new attacks faster than other techniques.