The　multi-criteria　minimum　spanning　tree　(mc-MST)　problem　is　a　typical　NP-hard　problem.　An　algorithm　to　enumerate　the　set　of　Pareto　optimal　spanning　trees　on　some　mc-MST　instances　was　put　forward　by　Zhou　and　Gen,　but　it　does　not　guarantee　returning　all　the　Pareto　optimal　solutions.　To　settle　this　problem,　an　improved　algorithm　is　developed　and　also　proved　to　be　able　to　find　all　the　true　Pareto　optimal　solutions　in　this　paper.　The　new　algorithm　adds　some　conditions　in　the　elimination　of　subtrees.　Simulation　results　show　that　the　new　algorithm　can　find　all　the　Pareto　optimal　solutions　and　also　show　that　the　new　algorithm　has　potential　usage　in　practice.