3

我正在寻求改进我的解决方案，以使用快速查找算法在有向图中查找所有弱连接组件。

问题陈述

给定一个 列表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]
]

我使用快速查找算法解决了这个问题。下面的代码：

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 回答