使用快速查找算法在有向图中查找所有弱连通组件的优化 (Java)

Question

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

问题陈述

给定 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]
]

我使用 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) 因为每次它都需要对并集进行线性搜索。很好奇有没有办法改善这个问题

感谢您的建议！

Answer 1

这是经过编辑的答案。抱歉，我混淆了弱连通分量和强连通分量。

确定弱连通分量实际上非常简单。只需将所有边转换为无向边，然后执行 BFS 或 DFS。

运行时间将是 O(|V| + |E|)，其中 V 是顶点集，E 是边集。

使用快速查找算法在有向图中查找所有弱连通组件的优化 (Java)

Optimization for Find All Weakly Connected Components in Directed Graph Using Quick-Find Algorithm (Java)

java

algorithm

graph

connected-components

union-find