新的HashMap指向旧的HashMap

我想实现一个使用带有整数键的HashMap和一个ArrayList作为值的图算法。新的HashMap指向旧的HashMap

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

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

的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); 
    } 
}

在main方法：

/* 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); 
     }

来源

2013-04-30 Sam Welch

为什么需要这个mapBlacklist摆在首位？

我可以从你的算法，你可以用你的队列进行迭代（递归）对所有未访问过的项目看。

在循环：

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

只是不使用黑名单，不从图中删除任何东西。您只能迭代当前顶点的列表并将其中的所有项添加到队列中。

它是否使感觉？

来源

2013-04-30 18:48:15

因为该图可以是多方向的。 I.E.顶点1指向2，但顶点2指向一个。然后，顶点将返回到顶点2. – 2013-04-30 18:52:15

然后，可以不从黑名单中移除已访问的节点，而是可以将它们添加到已分隔的visitedList并在将下一个节点添加到队列之前检查whis列表？最初visitedList是空的，所以你不会在迭代过程中改变图形。 – 2013-04-30 19:35:35

我发现你正在使用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-30 20:07:43 sharakan

新的HashMap指向旧的HashMap

回答

相关问题