JavaのHashMapの隣接リストグラフパーティション

Question

私はHashMapを持っている：

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

これは、隣接リストです。第1の区画がノード{A、B、C、D}を含み、第2の区画が{E、F}である2つの区画を有するグラフを有する。

問題：隣接リストを表すHashMapが与えられた場合、パーティションを返します。言い換えれば

：これを解決するためにJavaで

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

いくつかのソリューション/アルゴリズム???

シモンズ：ジャワに限らず、任意のヘルプは、事前に

TKS歓迎:)です:)

Answer 1

あなたは、このための任意のグラフトラバーサル技術（BFSまたはDFS）を使用することができます。例えば

、あなたはBFSを使用している場合：任意のノードから

• スタート（X言うことができます）。

• このノードに接続されているすべてのノードにアクセスしたら、グラフのすべてのノードが訪問したかどうかを確認します。訪問されていないノードが発生した場合は、このノードから新しいBFSを開始します。これが2番目のパーティションになります。

• などなど...あなたの場合

、あなたはAからBFSを開始した場合、それは[C、B、D]を訪問します。これは1番目のパーティションです。

グラフ（E）に未訪問のノードがあるかどうかを確認します。これで、EからBFSを起動し、訪問したすべてのノードが2番目のパーティションにあります。

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]