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

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

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

复制代码

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

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

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

没底的瓶子 发表于 2013-6-1 20:09
将问题抽象下 找个合适的算法 最后在考虑代码
PS:坐等P=NP

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

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

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