Medical image segmentation is a fundamental and challenging problem for analyzing medical images. Among different existing medical image segmentation methods, graph-based approaches are relatively new and show good features in clinical applications. In the graph-based method, pixels or regions in the original image are interpreted into nodes in a graph. By considering Markov random field to model the contexture information of the image, the medical image segmentation problem can be transformed into a graph-based energy minimization problem. This problem can be solved by the use of minimum s-t cut/ maximum flow algorithm. This review is devoted to cut-based medical segmentation methods, including graph cuts and graph search for region and surface segmentation. Different varieties of cut-based methods, including graph-cuts-based methods, model integrated graph cuts methods, graph-search-based methods, and graph search/graph cuts based methods, are systematically reviewed. Graph cuts and graph search with deep learning technique are also discussed.