We study the parallel machine scheduling problems with tree and road constraints, where the job set corresponds to the set of edges (or arcs) of the undirected graph (or directed graph). The goal is to select a subset of jobs that constitutes a tree or path, and then execute the selected jobs on parallel machines to minimize the makespan. By exploiting the combinatorial properties of the problem, we draw the following conclusions: under the constraint of Ktree, an efficient polynomial time approximation scheme (EPTAS) can be obtained by using the property of the minimum spanning Ktree; under the constraint of the road between two fixed points, the weight of edges can be controlled by constructing auxiliary instances, and through analyzing the relationship between the optimal value of the original instance and the output value of the auxiliary instance, an  2approximation algorithm can be obtained by using the property of the shortest path; under the constraint of a singlesource shortest path tree, an EPTAS can be obtained according to the property of the shortest path tree; under the constraint of the shortest path between two fixed points, based on the subgraph constructed by all the shortest paths between two points, the weight of arcs can be controlled by constructing new auxiliary instances, and then using the property of the shortest path, an  1.618approximation algorithm can be obtained.