Abstract: The cost performance of MPH （minimum path cost heuristic） is nearly the best in several algorithms for constructing multicast tree, but the running time is longer. Two new multicast tree constructing algorithms are presented in this paper, which are called TNS MPH （tree node started minimum cost path heuristic） and NTDS MPH （non tree destination started minimum cost path heuristic）. And a new random networks generating model is given. The model can construct a network with demanded average node degree. The results of the simulation for the two new algorithms show that the new algorithms can gain faster running speed with less cost performance worsening, and have a better scalability than algorithm SCTF （selective closest terminal first）.