我设计了一个城市公交查询系统,效率极其低下,求帮助。

代码就不贴了。说说我的主要思路。公交信息保存在一个文本文件中,每一行是一条公交路线,行首是公交号,站点间空格隔开。
然后,我就设计了两个类,一个是保存站点信息的stationNode,另一个是保存路线信息的pathLineNode,每一个stationNode都记录有站点名称、能够直接到达的下一站点的集合,以及经过本站的公交号集合:

struct StationNode{
   friend bool operator==(const StationNode&,const StationNode&);
   friend bool operator<(const StationNode&,const StationNode&);
   friend bool operator>(const StationNode&,const StationNode&);
   StationNode():left(NULL),right(NULL),bf(0){}
   StationNode *left,*right;
   int bf;  //节点平衡因子
   QSet<QString> nextStations; //记录本站能直接到达的所有其他站
   QString StationName;   //本站站名
   QSet<QString> BusNums;  //记录所有经过本站的汽车车号

};

先不讨论pathLineNode,我通过获取用户输入的起点和终点,根据起点名称找到对应的StationNode,然后根据nextStations进行遍历,整个过程使用一个队列保存经过的站点,如果当前站点已经存在于队列中,则说明此路线是回路,舍弃;如果当前站点是终点,则找到一条可行路线,不再遍历当前站点的nextStations;否则,继续遍历当前站点的nextStations。
因为要求找到所有可行路线,所以我只能想到这么一种遍历方法了,但是运行好久都停不下来。哪位大神有高级算法么?

这类问题应该可以用经典的图论方法解决吧。

将问题抽象下 找个合适的算法 最后在考虑代码
PS:坐等P=NP:7_145:

我一直在想,没遍历过你怎么知道这条路线不能到达终点站呢?因为要求找到所有可行路线嘛,图的所谓最短路径算法只能找到最短路径?

如果你只是想求最短路径的最优解,用某些图遍历、单源(多源)最短路径算法、动态规划这些能搞定;
但是换乘公交得多花钱的。。。

其实一个城市的公交线路都是相对固定的 所以没必要每次查询都要重新计算各种路径
直接一次算好 查数据库