java - 获取2个节点之间的所有路径列表

Question

任何人都可以帮助我理解我在这里做错了什么。我想获取图中两个给定节点之间的所有路径的列表。任何帮助将非常感激。

public class City {
    final private String id;  

      public City(String id) {
        this.id = id;
      }
      public City getCity() {
    return node;
  }
  public int getCost() {
    return cost;
  }
}

public class Route {

    private final City node;
    private final int cost; 

      public Route(City node, int cost) {
        this.node = node;
        this.cost = cost;
      }
}

    public class Graph {

private final List<City> cities;
private final List<Route> routes;
private final Map<City, List<Route>> myGraph = new HashMap<City,List<Route>>();
private Queue<City> visited = new LinkedList<City>();
private Queue<City> beenThere = new LinkedList<City>();

 public Graph(List<City> vertexes, List<Route> edges) {
    this.cities = vertexes;
    this.routes = edges;
  }

  public String toString () {
        StringBuffer s = new StringBuffer();
        for (City c: myGraph.keySet()) 
            System.out.println(c + " -> " + myGraph.get(c));
        System.out.println();
        return s.toString();                
    }

  public void addNew (City vertex) {
        if (myGraph.containsKey(vertex)) 
            return;
        myGraph.put(vertex, new ArrayList<Route>());   
    }

  public void add (City from, City to, int cost) {
        this.addNew(from); 
        this.addNew(to);
        myGraph.get(from).add(new Route(to,cost));
        myGraph.get(to).add(new Route(from,cost));
    }

  public boolean contains (City vertex) {
        return myGraph.containsKey(vertex);
    }

 // public Route returnRoute

  public Queue<City> getNeighbors(City city) {
        Queue<City> neighbors = new LinkedList<City>();
        for (City c : myGraph.keySet()) {
            String c1 = c.toString();
            String city1 = city.toString();
            if (c1.equals(city1)) 
                neighbors.add(myGraph.get(c).get(0).getCity()); 
        }
        return neighbors;
        }

  public Queue<City> checkRoute(City node) {
      Queue<City> neighbors = new LinkedList<City>();
      neighbors = this.getNeighbors(node);
      for (City n : neighbors) 
              if(visited.contains(n))
                  break;
              else
          {
                  visited.add(n);
                  beenThere.add(n);
                  checkRoute(n);
              }

      return beenThere;
  }

  public List<Queue<City>> BFS(Graph graph, City from, City to) {
      List<Queue<City>> rute = new ArrayList<Queue<City>>();
      Queue<City> toVisit = new LinkedList<City>();
      toVisit.add(from);
      beenThere.add(from);
      while(!toVisit.isEmpty()) {
          City node = toVisit.remove();
          visited.add(node);
          Queue<City> neighbors = new LinkedList<City>();
          neighbors = this.getNeighbors(node);
          while(!neighbors.isEmpty()) {
              visited.add(neighbors.element());
              checkRoute(neighbors.remove());
          }
          if (beenThere.poll().equals(to))
              rute.add(beenThere);
          beenThere.clear();
          beenThere.add(from);
          //visited.clear();
      }
      return rute;
    }

    public void ReadFile() throws IOException  {
      String scan;
        FileReader file = new FileReader("C:\\Users\\W7\\workspace\\AI-Lab1\\graph.txt");
        BufferedReader br = new BufferedReader(file);
        while((scan = br.readLine()) != null) {
            String[] numberString =scan.split(" ");
            String from = numberString[0];
            City city1 = new City(from);
            String to = numberString[1];
            City city2 = new City(to);
            int cost = Integer.parseInt(numberString[2]);
            this.add(city1, city2, cost);
        }
        br.close();
  }
    }

城市是从文本文件 graph.txt 中读取的:

Bucuresti Atena 1700
Bucuresti Budapesta 800
Paris Bucuresti 2000
Madrid Berlin 500
Kiew Moscova 800
Oslo Stokolm 590
Bucuresti Berlin 1500
Budapesta Berlin 500

public class Start {

    private static  List<City> nodes;
    private static List<Route> edges;

    private static void run () throws IOException {
        nodes = new ArrayList<City>();
        edges = new ArrayList<Route>();
        Graph graph = new Graph(nodes, edges); 
        graph.ReadFile();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            System.out.println("Press:");
            System.out.println("[1] VIEW THE GRAPH");
            System.out.println("[2] GET THE SHORTEST PATH");
            try {
                String s = br.readLine();
                if(s.equals("exit"))
                    return;
                int option=Integer.parseInt(s);
                if (option == 1 ) {
                    System.out.println("The graph is:" );
                    System.out.println(graph);
                    //getGraph();
                    System.out.println("========================");
                }
                if (option == 2) {
                    System.out.println("\tGive source vertex : ");
                    String source = br.readLine();
                    City from =  new City(source);
                    System.out.println("\tGive destination vertex : ");
                    String destination = br.readLine();
                    City to = new City(destination);
                    //getShortestPath(graph,source,destination);
                    System.out.println(graph.BFS(graph, from, to));
                    System.out.println("========================");
                }
                if (option == 3) {
                    System.out.println("Please insert city:");
                    String c = br.readLine();
                    City city = new City(c);
                    System.out.println(graph.getNeighbors(city));
                }
            }catch(IOException e) {
                e.printStackTrace();
            }
        } 
      }

      public static void main(String[] args) throws IOException  {
          run();

}
}

这会返回一个空列表，我不明白为什么......

Answer 1

我注意到你有:

if (beenThere.poll().equals(to)) {
  rute.add(beenThere);
}

要评估您自己的个人对象之一的相等性，您需要重写该类的 hashCode() 和 equals() 方法。

否则，两个对象永远不会相等，除非它们是内存中完全相同的对象。将这两个方法添加到您的 City 类中:

@Override
public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + ((id == null) ? 0 : id.hashCode());
  return result;
}

@Override
public boolean equals(Object obj) {
  if (this == obj)
return true;
  if (obj == null)
return false;
  if (getClass() != obj.getClass())
return false;
  City other = (City) obj;
  if (id == null) {
if (other.id != null)
  return false;
  } else if (!id.equals(other.id))
return false;
  return true;
}

另一个问题是，您正在清除 beenThere ，这也会清除 ArrayList 中的值，因为它们都引用内存中的同一对象。要理解这一点，请尝试使用以下代码，其中注释掉 clear() 方法以查看差异。

public static void main(String[] args) {
  List<Queue<Integer>> rute = new ArrayList<Queue<Integer>>();
  Queue<Integer> beenThere = new LinkedList<Integer>();

  beenThere.add(1);
  beenThere.add(2);
  beenThere.add(3);
  rute.add(beenThere);

  beenThere.clear(); // run this code with this commented out to see the difference

  System.out.println(rute.toString());
}