的java HashMap中鄰接解釋圖分區

Question

我有一個HashMap：

Key,Value 
A,C 
B,C 
C,D 
E,F 

這是一個鄰接表。帶有兩個分區的圖，其中第一個分區包含節點{A，B，C，D}，第二個分區是{E，F}。

問題：給定表示鄰接列表的HashMap返回分區。

換句話說：

Input: {[A,C],[B,C],[C,D],[E,F]} 
Output: {[A,B,C,D],[E,F]} 

一些溶液/算法在Java中解決這個???

詩：不限於Java，任何幫助，歡迎:)

韓國社交協會提前:)

Answer 1

你可以使用這個（BFS或DFS）的任何圖形的穿越技術。

例如，如果你正在使用BFS：從任何節點

• 開始（可以說X）。

• 訪問了連接到此節點的所有節點後，檢查是否訪問過圖的所有節點。如果遇到未訪問的節點，請從此節點啓動新的BFS，這將成爲您的第二個分區。

• 等等...

在你的情況，如果你從A開始BFS，它會訪問[C，B，d]。這是第一個分區。

現在您檢查圖（E）中是否有未訪問的節點。所以，現在你從E開始一個BFS，並且你訪問的所有節點都在第二個分區中。

Answer 2

IMO最好的解決辦法是Union-Find algorithm

public class UnionFind { 
    Map<String, String> parents = new HashMap<>(); 
    Map<String, Integer> representantElements = new HashMap<>(); 

    public void union(String p0, String p1) { 
     String cp0 = find(p0); 
     String cp1 = find(p1); 
     if (!cp0.equals(cp1)) { 
      int size0 = representantElements.get(cp0); 
      int size1 = representantElements.get(cp1); 
      if (size1 < size0) { 
       String swap = cp0; 
       cp0 = cp1; 
       cp1 = swap; 
      } 
      representantElements.put(cp0, size0 + size1); 
      parents.put(cp1, cp0); 
      representantElements.put(cp1, 0); 
     } 
    } 

    public String find(String p) { 
     if (!representantElements.containsKey(p)){ 
      representantElements.put(p, 1); 
      return p; 
     } 
     String result = parents.get(p); 
     if (result == null) { 
      result = p; 
     } else { 
      result = find(result); 
      parents.put(p, result); 
     } 
     return result; 
    } 

    public Set<Set<String>> getPartitions() { 
     Map<String, Set<String>> result = new HashMap<>(); 
     representantElements.forEach((key, value) -> {if (value > 0) {result.put(key, new HashSet<>(value));};}); 
     representantElements.forEach((key, value) -> result.get(find(key)).add(key)); 
     return new HashSet<>(result.values()); 
    } 

    public static Set<Set<String>> partitions(String[][] pairs) { 
     UnionFind groups = new UnionFind(); 
     for (String[] pair : pairs) { 
      if (pair.length > 1) { 
       String first = pair[0]; 
       for (int i = 1; i < pair.length; i++) { 
        groups.union(first, pair[i]); 
       } 
      } 
     } 
     return groups.getPartitions(); 
    } 

    public static void main(String[] args) { 
     String[][] elements = {{"A","C"},{"B","C"},{"C","D"},{"E","F"}}; 
     for (Set<String> partition : partitions(elements)) { 
      System.out.println(partition); 
     } 
    } 
} 

它打印：

[A, B, C, D] 
[E, F]