The leader-following consensus problem for a class of second-order nonlinear multi-agent systems underMarkovian switching topologies is studied. First, a discontinuous distributed adaptive nonlinear control law usingthe relative state information between neighboring agents is designed for heterogeneous multi-agent systems, whichachieves almost sure leader-following consensus for the closed-loop system. Then, a smooth distributed control lawis designed for homogeneous multi-agent systems. Compared with previous results, the nonlinear functions are notrequired to satisfy the globally Lipschitz condition and the adaptive consensus protocol is in a distributed fashion,i.e., using only the relative information. A practical example of ship course control system and simulation areprovided to demonstrate the effectiveness of the control scheme