我的最小生成树丫!!!!!!!!!!!!!!!!!!!
楼主的问题看似有点问题。既然规定好费用要最低,且每个城市至少经过一次,怎么可能会允许城市经过2次或2次以上呢?那1次以上的开销不是白白浪费了嘛。这个问题叫旅行商问题(Traveling Salesman Problem, TSP),是一个典型的NP难问题,没有一个能给出问题精确解的多项式算法。你们老师如果说给一个拓扑排序算法,那肯定只能用于几个城市的小规模TSP问题,一般中等规模以上的TSP问题多用智能优化算法(如GA、ACO等)在有限时间内给出近似解。