High-throughput low-latency interconnection networks are suitable for workstation clusters. An interconnection network can be constructed in different topologies. Typically, interconnection networks with regular topologies, such as mesh, torus, and hypercube, are less scalable for workstation clusters than those with irregular topologies. There have been many deadlock-free routing algorithms developed for regular networks, but it is relatively difficult to solve deadlock problems for irregular networks. We have previously proposed an effective routing scheme, called TRAIN, for irregular networks. The TRAIN routing algorithm is deadlock-free and requires no routing tables in the switch. This routing algorithm is based on a spanning tree which is constructed in the network. In this paper, we study how to construct a spanning tree so that the network can benefit from the TRAIN routing algorithm. Several schemes of constructing spanning trees are studied. These tree construction schemes are evaluated and compared in unloaded networks based on static analysis. They are also evaluated for loaded networks based on simulations.