In this letter, we propose a method to automate the exploration of unknown underwater structures for autonomous underwater vehicles (AUVs). The proposed algorithm iteratively incorporates exteroceptive sensor data and replans the next-best-view in order to fully map an underwater structure. This approach does not require prior environment information. However, a safe exploration depth and the exploration area (defined by a bounding box, parameterized by its size, location, and resolution) must be provided by the user. The algorithm operates online by iteratively conducting the following three tasks: (1) Profiling sonar data are first incorporated into a 2-D grid map, where voxels are labeled according to their state (a voxel can be labeled ...