Atmospheric turbulence causes fluctuations in the local refractive index of air that accumulatively disturb a waves phase and amplitude distribution as it propagates. This impairs the effective range of laser weapons as well as the performance of free space optical (FSO) communication systems. Adaptive optics (AO) can be applied to effectively correct wavefront distortions in weak turbulence situations. However, in strong or deep turbulence, where scintillation and beam breakup are common phenomena, traditional wavefront sensing techniques such as the use of Shack-Hartmann sensors lead to incorrect results. Consequently, the performance of AO systems will be greatly compromised. We propose a new approach that can determine the major phase distortions in a beam instantaneously and guide an AO device to compensate for the phase distortion in a few iterations. In our approach, we use a plenoptic wavefront sensor to image the distorted beam into its 4D phase space. A fast reconstruction algorithm based on graph theory is applied to recognize the phase distortion of a laser beam and command the AO device to perform phase compensation. As a result, we show in our experiments that an arbitrary phase distortion with peak to peak value up to 22{pi} can be corrected within a few iteration steps. Scintillation and branch point problems are smartly avoided by the plenoptic sensor and its fast reconstruction algorithm. In this article, we will demonstrate the function of the plenoptic sensor, the fast reconstruction algorithm as well as the beam correction improvements when our approach is applied to an AO system.