爲什麼我的ArrayList填充了重複的節點值？

Question

它應該簡單地爲節點5的5 = [6]，爲什麼3個不同的值。另外，我知道，這個當前的代碼是錯誤的大時間，因爲當我添加像2,1和2,3這樣的邊時，它甚至會執行2 = [3,3]。它只是用最後一個替換舊值並複製它。這是帶有結果的圖像。

Graph.java

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.Map.Entry; 


public class Graph { 

    HashMap <Integer, ArrayList<Integer>> adj =new HashMap<Integer, ArrayList<Integer>>(); 

    public void addEdge(int source, int destination) { 

     ArrayList<Integer> list = new ArrayList<Integer>(); 
     adj.put(source,list); 
     list.add(destination); 

     for(Entry<Integer, ArrayList<Integer>> entry: adj.entrySet()) { 
      int existing = entry.getKey(); 
      System.out.println("Existing: "+existing); 
      System.out.println("Source: " +source); 
      if (source != existing) { 
       //adj.get(2).add(9); 
       //System.out.println(source +": "+ destination); 
       adj.get(source).add(destination); 

      } 

     } 


    } 


    public void print() { 
     System.out.println(adj); 
    } 


} 

AdjacencyList.java

import java.util.Scanner; 



public class AdjacencyList { 

    public static void main(String[] args) { 

     Scanner in = new Scanner (System.in); 
     System.out.println("Enter nodes below like (u,v):"); 

     Graph g = new Graph(); 

     for (int i=0; i<3; i++) { 

      String nodes = in.nextLine(); 
      String[] data = nodes.split(","); 

      String u = data[0]; 
      String v = data[1]; 
      int inNode = Integer.parseInt(u); 
      int outNode =Integer.parseInt(v); 

      g.addEdge(inNode,outNode); 
      System.out.println("Added to list"); 

     } 


      g.print(); 

    } 

} 

Answer 1

從我可以告訴你有哪些source -> List<destination>要更新的Map。

您添加一個新的source節點，並將其作爲destination映射到所有現有的sources。

所以，比如我有

1 -> [2,3] 
2 -> [1,3] 
3 -> [1,2] 

如果我通過調用addEdge(4, 5)我應該結束了

1 -> [2,3,5] 
2 -> [1,3,5] 
3 -> [1,2,5] 
4 -> [5] 

添加一個新的映射是正確的？

在這種情況下，您的代碼是有缺陷的。首先要注意的是，這裏：

adj.get(source).add(destination); 

您總是添加destination屬於源節點的List<destination>。所以，當你在上面的例子調用addEdge(4, 5)（假設迭代爲簡明起見）：

1. entry.key()是1，1 != 4，加5到adj.get(4)
2. entry.key()是2，2 != 4，加5到adj.get(4)
3. entry.key()是3，3 != 4，add 5 to adj.get(4)
4. entry.key()是4,4 == 4，noop。

所以你最終獲得：

1 -> [2,3] 
2 -> [1,3] 
3 -> [1,2] 
4 -> [5,5,5] 

爲了解決這個問題，我需要知道你所期望的輸出是一個給定的初始狀態和投入 - 也就是我需要算法。在猜測我會說你想要做到這一點：

Map<Integer, List<Integer>> adj = new HashMap<>(); 

public void addEdge(int source, int destination) { 
    List<Integer> list = new ArrayList<>(); 
    adj.put(source, list); 
    list.add(destination); 
    for (final Entry<Integer, List<Integer>> entry : adj.entrySet()) { 
     if (source != entry.getKey()) { 
      entry.getValue().add(destination); 
     } 
    } 
} 

即

1. entry.key()是1，1 != 4，添加5到adj.get(1)
2. entry.key()是2，2 != 4，添加5到adj.get(2)
3. entry.key()是3，3 != 4，添加5到adj.get(3)
4. entry.key()是4，4 == 4，noop。

我也改變了代碼程序到interface和使用Java 7鑽石語法可讀性。

在這種情況下，您需要執行檢查的唯一原因是您putdestination納入您在循環之前創建的新List。我建議：

public void addEdge(int source, int destination) { 
    if (adj.get(source) == null) { 
     adj.put(source, new ArrayList<>()); 

    } 
    for (final Entry<Integer, List<Integer>> entry : adj.entrySet()) { 
     entry.getValue().add(destination); 
    } 
} 

即我們檢查的source映射是否null，如果它是我們添加一個new ArrayList到adj。然後，我們遍歷全部映射並將目標添加到每個映射。結果將如上所述。

下面是新的代碼的一些輸出：

public static void main(final String[] args) throws Exception { 
    System.out.println(adj); 
    addEdge(1, 2); 
    System.out.println(adj); 
    addEdge(3, 7); 
    System.out.println(adj); 
    addEdge(4, 2);   
    System.out.println(adj); 
} 

輸出：

{} 
{1=[2]} 
{1=[2, 7], 3=[7]} 
{1=[2, 7, 2], 3=[7, 2], 4=[2]} 

所以有可能是另一個錯誤 - 也就是說，如果我把相同的目的地在兩次我得到一個重複這個辦法。如果這不是你想要的，需要一個小的變化：

Map<Integer, Collection<Integer>> adj = new HashMap<>(); 

public void addEdge(int source, int destination) { 
    if (adj.get(source) == null) { 
     adj.put(source, new LinkedHashSet<>()); 

    } 
    for (final Entry<Integer, Collection<Integer>> entry : adj.entrySet()) { 
     entry.getValue().add(destination); 
    } 
} 

更改Map舉行一般性Collection並添加LinkedHashSet而非ArrayList。 A LinkedHashSet維護訂單（Linked）並且不允許重複元素（Set）。

輸出現在是：

{} 
{1=[2]} 
{1=[2, 7], 3=[7]} 
{1=[2, 7], 3=[7, 2], 4=[2]} 

編輯

而且老年退休金計劃發表評論

在下面輸入節點等（U，V）：2,1添加到列表2,3添加到列表5,6添加到列表{2 = [3，6]，5 = [6]}

看起來這是sim PLER。 OP希望維護一個簡單的映射 - 並且只更新相關的source -> destination並且不允許重複的目的地。該代碼是：

Map<Integer, Collection<Integer>> adj = new HashMap<>(); 

public void addEdge(int source, int destination) { 
    //see if adj contains source already 
    Collection<Integer> destinations = adj.get(source); 
    //if not add in a new LinkedHashSet 
    if (destinations == null) { 
     destinations = new LinkedHashSet<>(); 
     adj.put(source, destinations); 
    } 
    //Set returns false if item exists 
    if (!destinations.add(destination)) { 
     System.out.println("This mapping already exists."); 
    } 
} 

輸出：

{} 
{1=[2]} 
{1=[2], 3=[7]} 
{1=[2], 3=[7], 4=[2]} 
{1=[2], 3=[7], 4=[2, 3]} 
This mapping already exists. 
{1=[2], 3=[7], 4=[2, 3]}