V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
guagual
V2EX  ›  程序员

小菜举个手,问个问题

  •  
  •   guagual · 2013-09-22 19:49:47 +08:00 · 3074 次点击
    这是一个创建于 4079 天前的主题,其中的信息可能已经有所发展或是发生改变。
    给出数据:
    1、给出了全国所有站点
    2、给出了所有车次以及车次途经的站点。

    问题:
    1、设计一个数据结构存储所给的数据;
    2、现在给出站点A,B站点。求A到B的有几种走法(途经的站点数不超过n个),设计算法实现。
    7 条回复    1970-01-01 08:00:00 +08:00
    11
        1
    11  
       2013-09-22 19:53:13 +08:00
    helone
        2
    helone  
       2013-09-22 19:53:26 +08:00
    mark一下 等大牛分析~
    slixurd
        3
    slixurd  
       2013-09-22 20:07:15 +08:00
    要求效率么?不要求效率就直接用邻接表然后回溯来查找
    需要效率的话用动态规划吧(虽然每次找动态规划方程我都跪...
    felix021
        4
    felix021  
       2013-09-23 10:06:07 +08:00
    这么裸的BFS……n层内从A到B的路径数一下就行了。

    这个是数据结构书上讲队列的时候就会介绍的算法吧。
    wnd62ee
        5
    wnd62ee  
       2013-09-23 10:13:14 +08:00
    mark
    fangzhzh
        6
    fangzhzh  
       2013-09-23 10:19:23 +08:00
    我以前写过一个android的,BFS即可,
    代码: https://github.com/fangzhzh/mobile91 学android练手用, 请忽略暴丑UI.
    还有一个ruby的还没写完, 在web目录.
    66450146
        7
    66450146  
       2013-09-23 11:25:12 +08:00
    如果没有时空限制和数据规模的话,什么问题都解决不了的

    从直觉来说,如果是火车站的话,直接邻接矩阵 bfs 就搞定了

    如果是全国的公车站的话。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1194 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 23:54 · PVG 07:54 · LAX 15:54 · JFK 18:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.