Normalized cut is a powerful method for image segmentation as well as data clustering. However, it does not perform well in challenging segmentation problems, such as segmenting objects in a complex background. Researchers have attempted to incorporate priors or constraints to handle such cases. Available priors in image segmentation problems may be hard or soft, unary or pairwise, but only hard must-link constraints and two-class settings are well studied. The main difficulties may lie in the following aspects: 1) the nontransitive nature of cannot-link constraints makes it hard to use such constraints in multi-class settings and 2) in multi-class or pairwise settings, the output labels have inconsistent representations with given priors, making soft priors difficult to use. In this paper, we propose novel algorithms, which can handle both hard and soft, both unary and pairwise priors in multi-class settings and provide closed form and efficient solutions. We also apply the proposed algorithms to the problem of object segmentation, producing good results by further introducing a spatial regularity term. Experiments show that the proposed algorithms outperform the state-of-the-art algorithms significantly in clustering accuracy. Other merits of the proposed algorithms are also demonstrated.