0

我正在尝试使用带有整数键的 HashMap 和值的 ArrayList 来实现图形算法。

关键是顶点，ArrayList是连接到关键顶点的所有顶点。

我正在使用黑名单来跟踪我去过的地方。如果该项目在黑名单中，我还没有访问过那个顶点。这段代码的问题是我必须能够在程序运行时多次调用搜索。我正在做的是将黑名单指向带有顶点的图形。然后，当我访问一个顶点时，我删除了黑名单中的值。问题是，黑名单指向原始图中的值。因此，当我再次运行搜索时，原始图丢失了我之前搜索过的所有顶点。

TL:DR 问题是这样的：如何在不指向的情况下创建一个新的相同 HashMap。

我知道我可以循环遍历 HashMap 并复制每个条目，但是如果我进行大量搜索（大量搜索！），它会变慢。如果这是唯一的方法，我不会这样做。

 //The class variables used for this search
 HashMap<Integer, ArrayList<Integer>> mapBlacklist;
 Queue<Integer> line = new PriorityQueue<Integer>();
 int searchFor;
 boolean areTheyConnected;

 //The constructor I'm using
 GraphSearch(HashMap<Integer, ArrayList<Integer>> graph, int match){
    mapBlacklist = new HashMap<Integer, ArrayList<Integer>>(graph);
    searchFor = match;
 }
 //The search method.
 void numberOne(int start, HashMap<Integer, ArrayList<Integer>> graph){
    if(graph.get(start).contains(this.searchFor)){
        this.areTheyConnected = true;
    }
    else{
        while(!this.mapBlacklist.get(start).isEmpty()){
            this.line.add(this.mapBlacklist.get(start).get(0) ;
            this.mapBlacklist.get(start).remove(0);
        }
    }

    if(!this.line.isEmpty() && !this.areTheyConnected){
            numberOne(this.line.remove(), graph);
    }
}

在主要方法中：

/* What it looks like in the command line to see if vertices 2 5 are connected:
       1 2 5

   To close the program:
       0
*/
boolean keepGoing = true;
    while(keepGoing){
        Scanner sc = new Scanner(System.in);
        int number0 = Integer.parseInt(sc.next());
        if(number0 == 0){
            keepGoing = false;
            sc.close();
        }
        else if(number0 == 1){
            int number1 = Integer.parseInt(sc.next());
            int number2 = Integer.parseInt(sc.next());
           // GraphSearch gsearch = new GraphSearch(graph, number2);
            GraphSearch gsearch = new GraphSearch(mapGraph, number2);
            gsearch.numberOne(number1, mapGraph);
            System.out.println(gsearch.areTheyConnected);
        }
4

2 回答 2

0

我发现您使用的方式mapBlackList令人困惑，而且我认为这种混乱导致了您的问题。

您无需知道地图的结构即可防止重新访问，只需知道您在此搜索期间访问过的内容即可。因此，与其在构造函​​数中制作整个图的浅表副本，为什么不简单地保留Set<Integer>到目前为止您访问过的顶点？您的搜索方法变得类似于：

void numberOne(int start, HashMap<Integer, ArrayList<Integer>> graph){
  visited.add(start);

  if(graph.get(start).contains(this.searchFor)){
    this.areTheyConnected = true;
    return;
  }
  else{
    for (Integer destination : graph.get(start)) {          
      if (!areTheyConnected && !visited.contains(destination)) {
        numberOne(destination, graph);          
      }
    }
  }
}
于 2013-04-30T20:07:43.040 回答
0

为什么首先需要这个 mapBlacklist？

我可以从您的算法中看到，您可以使用队列来迭代（递归）所有未访问的项目。

在循环：

while(!this.mapBlacklist.get(start).isEmpty()){
        this.line.add(this.mapBlacklist.get(start).get(0) ;
        this.mapBlacklist.get(start).remove(0);
    }

只是不要使用黑名单，也不要从图表中删除任何内容。您只能遍历当前顶点中的列表并将其中的所有项目添加到队列中。

这有意义吗？

于 2013-04-30T18:48:15.693 回答