新的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

回答

相關問題