This paper presents second-order accurate genuine BGK (Bhatnagar-Gross-Krook) schemes in the framework of finite volume method for the ultra-relativistic flows. Different from the existing kinetic flux-vector splitting (KFVS) or BGK-type schemes for the ultra-relativistic Euler equations, the present genuine BGK schemes are derived from the analytical solution of the Anderson-Witting model, which is given for the first time and includes the genuine particle collisions in the gas transport process. The BGK schemes for the ultra-relativistic viscous flows are also developed and two examples of ultra-relativistic viscous flow are designed. Several 1D and 2D numerical experiments are conducted to demonstrate that the proposed BGK schemes not only are accurate and stable in simulating ultra-relativistic inviscid and viscous flows, but also have higher resolution at the contact discontinuity than the KFVS or BGK-type schemes.