Controlled islanding, which splits the whole power system into islands, is an effective way of limiting blackouts during severe disturbances. Finding islanding solutions in real time is difficult because of the combinatorial explosion of the solution space occurs for large power system. This paper proposes a computationally efficient algorithm based on constrained spectral clustering to solve controlled islanding problem. The objective function used in this algorithm is the minimal power- flow disruption. The main constraints applied are related to generator coherency and transmission line availability. An undirected edge-weighted graph is constructed based on power flow data, and constraints related to transmission line availability and generator coherency are included by modifying the graph weights and using a subspace approach. Spectral clustering is then applied to the constrained solution subspace to find the islanding solution. To improve the clustering quality, a robust k-medoids algorithm, which is less sensitive to outliers than the traditional k-means algorithm, is used for clustering. Simulation results show that the proposed algorithm is computationally efficient when solving a controlled islanding problem in real-time.