The present disclosure provides an obstacle detecting method and apparatus, a device and a storage medium, wherein the method comprises: obtaining a 3D point cloud collected by a driverless vehicle during travel; determining a set of vertexes and a set of edges respectively according to the obtained 3D point cloud; clustering vertexes in the set of vertexes according to the set of edges to obtain a smallest generated tree as an obstacle detection result. The solutions of the present disclosure can be applied to reduce workload and improve the accuracy of detection results.