クイック検索アルゴリズム（Java）を使用した有向グラフで弱く接続されたコンポーネントをすべて最適化する

Question

私は、クイック検索アルゴリズムを使用して有向グラフ内の弱く接続されたコンポーネントをすべて見つけるためにソリューションを改善しようとしています。 DirectedGraphNodeのリストを考えると

問題文

、すべての島（すなわち、弱連結成分）を見つけます。

public class DirectedGraphNode { 
    String val; 
    List<DirectedGraphNode> neighbors; 
} 

はこのように、以下の有向グラフ与えられた：

A —> B —> <— C 
    ^
    | 
    E <— F —> D —> G 

X -> <- Y 

node : neighbors 
    A : [B] 
    B : [C, E] 
    C : [B] 
    D : [G] 
    E : [] 
    F : [E, D] 
    G : [] 
    X : [Y] 
    Y : [X] 

次のように出力が（順番は関係ありません）次のようになります。

[ 
    [A, B, C, E, D, F, G], 
    [X, Y] 
] 

私が使用してこれを解決しクイック検索しますアルゴリズム。以下のコードは：

public static List<List<Node>> connectedComponents(List<Node> nodes) { 
    if (nodes == null || nodes.size() == 0) { 
     throw new IllegalArgumentException("List node is empty"); 
    } 

    // Maintain array with name for each element 
    String[] labels = new String[nodes.size()]; 
    // Initially, set the labels of each element to itself 
    // Use HashMap to memorize the index 
    Map<String, Integer> map = new HashMap<>(); 
    for (int i = 0; i < labels.length; i++) { 
     labels[i] = nodes.get(i).val; 
     map.put(nodes.get(i).val, i); 
    } 

    for (Node node : nodes) { 
     if (node.neighbors == null || node.neighbors.isEmpty()) { 
      continue; 
     } 

     int changerIdx = map.get(node.val); 
     for (Node nbr : node.neighbors) { 
      int changeeIdx = map.get(nbr.val); 
      String symbol = labels[changeeIdx]; 
      for (int i = 0; i < labels.length; i++) { 
       if (labels[i] == symbol) { 
        labels[i] = labels[changerIdx]; 
       } 
      } 
     } 
    } 
    return createIslandList(labels, nodes); 
} 

private static List<List<Node>> createIslandList(String[] labels, List<Node> nodes) { 
    List<List<Node>> res = new ArrayList<List<Node>>(); 
    if (labels == null || labels.length == 0) { 
     return res; 
    } 

    Map<String, List<Node>> map = new HashMap<String, List<Node>>(); 
    for (int i = 0; i < labels.length; i++) { 
     if (!map.containsKey(labels[i])) { 
      List<Node> island = new ArrayList<>(); 
      island.add(nodes.get(i)); 
      map.put(labels[i], island); 
     } else { 
      map.get(labels[i]).add(nodes.get(i)); 
     } 
    } 

    for (String key : map.keySet()) { 
     res.add(map.get(key)); 
    } 

    return res; 
} 

しかし、最悪の場合、このアルゴリズムは、それが労働組合のための線形探索を行う必要があるたび以来O（N^3）で実行されます。これを改善する方法があれば私は非常に興味があります。

ありがとうございます。

Answer 1

これは編集された回答です。私は弱く接続されたコンポーネントと強く接続されたコンポーネントの間で混乱していました。

実際には、弱く接続されたコンポーネントを特定するのは非常に簡単です。すべてのエッジを無向に変換し、BFSまたはDFSを実行するだけです。

実行時間はO(|V| + |E|)になります。ここで、Vは頂点のセットで、Eはエッジのセットです。