3

Quick-Findアルゴリズムを使用して、有向グラフ内のすべての弱結合コンポーネントを検索するソリューションを改善しようとしています。

問題文

のリストが与えられた場合、DirectedGraphNodeすべての島 (弱連結成分) を見つけます。

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

したがって、次の有向グラフが与えられます。

A —&gt; B —&gt; <— C 
     ^
     |
     E <— F —&gt; D —&gt; 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]
]

Quick-Findアルゴリズムを使用してこれを解決しました。以下のコード:

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)で実行されます。これは、ユニオンの線形検索を毎回行う必要があるためです。これを改善する方法があれば非常に興味があります。

提案ありがとう！

4

1 に答える 1

1

これは編集された回答です。弱連結成分と強連結成分を混同して申し訳ありません。

弱連結成分を特定するのは、実際には非常に簡単です。すべてのエッジを無向に変換し、BFS または DFS を実行するだけです。

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

于 2016-08-17T02:44:27.550 に答える