java - 广度优先搜索以查找两个地铁站之间的路线

Question

您好，我正在创建一个程序来查找伦敦地铁两个车站之间的路线。我正在使用链接对象来表示网络。因此，车站对象包含:名称、车站所在线路的列表、与其相邻的车站列表。我还有线路对象，其中包含:线路的名称、站点列表。还有一个网络对象，其中包含所有站点的列表和所有线路的列表。

我正在考虑使用广度优先搜索，但对如何在我的数据结构上实现该算法感到困惑。任何帮助将不胜感激。

我还使用了一种不同的方法来查找路线，如果它包含目的地，则搜索源的线路。如果没有，则查看线路中的路口，即超过 1 条线路的车站。并查看他们的线路，看看目的地是否在这些线路中。但是在进行了 1 次更改后，我对如何进行多次更改感到困惑。这是我使用的代码:

public void finder(String from, String to)
{

    Station source = network.searchStation(from);
    Station destination = network.searchStation(to);
    ArrayList<Line> sourceLines = source.getLines();
    ArrayList<String> routes = new ArrayList<String>();

    for(Line line:sourceLines)
    {
        ArrayList<Station> stations = line.getStations();
        if(stations.contains(destination))
        {
            Station endStart;
            if(stations.indexOf(destination) > stations.indexOf(source))
            {
                endStart = stations.get(stations.size()-1);
            }
            else{
                endStart = stations.get(0);
            }
            routes.add(endStart.getName());
            routes.add(line.getName());
            break;
        }
    }
    if(routes.size() != 0)
    {
        System.out.println("Start: " + from);
        System.out.println("Take the " + routes.get(1) + " line towards " + routes.get(0));
        System.out.println("End: " + to);
    }
    else{
        routes = search(source, destination, routes);
        System.out.println("Start: " + from);
        for(int n = 0; n < (routes.size() / 6);n++)
        {
            System.out.println("Take the " + routes.get(n + 1) + " line towards " + routes.get(n));
            System.out.println("Change at: " + routes.get(n + 2) + " to the " + routes.get(n + 3) + " line");
            System.out.println("Take the " + routes.get(n + 5) + " line towards " + routes.get(n + 4));
        }
        System.out.println("End: " + to);
    }
}

public ArrayList<String> search(Station source, Station destination, ArrayList routes)
{
    ArrayList<Line> sourceLines = source.getLines();
    for(Line line:sourceLines)
    {
        ArrayList<Station> searchList = new ArrayList<Station>();
        ArrayList<Station> lineStations = line.getStations();
        if(line.getVisited() == false)
        {
            for(Station station: lineStations)
            {
                if(station.getLines().size() > 1)
                {
                    searchList.add(station);
                }
            }
        }

        for(Station station:searchList)
        {
            ArrayList<String> stationChanges = new ArrayList<String>();
            ArrayList<Line> lines = station.getLines();
            Station endLine;
            if(lineStations.indexOf(station) > lineStations.indexOf(source))
            {
                endLine = lineStations.get(lineStations.size()-1);
            }
            else{
                endLine = lineStations.get(0);
            }
            stationChanges.add(endLine.getName());
            stationChanges.add(line.getName());
            for(Line stationLine:lines)
            {
                ArrayList<Station> stations = stationLine.getStations();
                if(stations.contains(destination))
                {
                    stationChanges.add(station.getName());
                    stationChanges.add(stationLine.getName());
                    Station endStart;
                    if(stations.indexOf(destination) > stations.indexOf(station))
                    {
                        endStart = stations.get(stations.size()-1);
                    }
                    else{
                        endStart = stations.get(0);
                    }
                    stationChanges.add(endStart.getName());
                    stationChanges.add(stationLine.getName());
                    for(String str:stationChanges)
                    {
                        routes.add(str);
                    }
                    return routes;
                }
                else
                {
                    stationLine.markVisited();
                    search(station,destination,stationChanges);
                }
            }

        }
    }
    return routes;
}

谢谢

Answer 1

路由是完全不同的问题。您需要使用 dijkstra 算法 或其变体，简单的 BFS 或回溯类算法，如果不考虑太多可能会让您误入歧途!