查找指定组件中的所有连接（简单、断开、无向图）

Question

我有以下简单的、断开的、无向图：

G1 = (V1, E1)  
V1 = {'a', 'b', 'c', 'd', 'e', 'f', 'k', 'l', 'x', 'y', 'z'}  
E1 = {
        {'a', 'b'}, {'a', 'c'},  
        {'d', 'e'}, {'d', 'f'},  
        {'k', 'l'},  
        {'x', 'y'}, {'x', 'z'}
     }

我是这样存储的：

private final Map<String, List<String>> graph = Map.of(
    "a", List.of("b", "c"),
    "d", List.of("e", "f"),
    "k", List.of("l"),
    "x", List.of("y", "z"));

我需要实现以下方法：

public void apply(String connectFrom, List<String> connectTos)

如果我们调用它，它应该应用新连接并输出连接组件的每个连接，其中 from（在本例中：'a'）是：

apply("a", List.of("d", "k"));

输出应该是这样的：

['a - b','a - c','a - d','a - e','a - f','a - k','a - l','b - a','b - c','b - d','b - e','b - f','b - k','b - l','c - a','c - b','c - d','c - e','c - f','c - k','c - l','d - a','d - b','d - c','d - e','d - f','d - k','d - l','e - a','e - b','e - c','e - d','e - f','e - k','e - l','f - a','f - b','f - c','f - d','f - e','f - k','f - l','k - a','k - b','k - c','k - d','k - e','k - f','k - l','l - a','l - b','l - c','l - d','l - e','l - f','l - k']

在此示例中，输出包含图形的每个连接，排除：

['x - y', 'x - z', 'y - x', 'y - z', 'z - x', 'z - y']

因为{'x', 'y'}, {'x', 'z'}形成一个单独的组件：

G1 = (V1, E1)  
V1 = {'a', 'b', 'c', 'd', 'e', 'f', 'k', 'l', 'x', 'y', 'z'}  
E1 = {
        {'a', 'b'}, {'a', 'c'}, {'a', 'd'}, {'a', 'k'},  
        {'d', 'e'}, {'d', 'f'},  
        {'k', 'l'},  
        {'x', 'y'}, {'x', 'z'}
     }

Answer 1

我创建了一个关于我的想法的GitHub Gist and a Replit snippet。

在我的解决方案中，我使用了 adjacency matrix，这首先是相当昂贵的...
但是非常有帮助，而且维护起来也很便宜。
便宜...尤其是没有 updateComponentMapping

这些是我 Graph<T> class:

底部的静态助手

//...
    public static <T extends Comparable<T>> Set<T> getNodeSet(Map<T, List<T>> graph) {
        Set<T> nodeSet = new TreeSet<>(graph.keySet());
        nodeSet.addAll(
            graph.values().stream()
                .flatMap(List::stream)
                .collect(Collectors.toSet()));

        return nodeSet;
    }

    public static <T extends Comparable<T>> int[][] getAdjacencyMatrix(Map<T, List<T>> graph) {
        return getAdjacencyMatrix(graph, getNodeSet(graph));
    }

    public static <T extends Comparable<T>> int[][] getAdjacencyMatrix(Map<T, List<T>> graph, Set<T> nodes) {
        List<T> nodeList = new ArrayList<>(nodes);
        int[][] matrix = new int[nodeList.size()][nodeList.size()];

        graph.forEach(
            (from, toList) ->
                toList.forEach(
                    to -> setAdjacency(matrix, nodeList.indexOf(from), nodeList.indexOf(to), 1)));

        return matrix;
    }

    private static void setAdjacency(int[][] matrix, int from, int to, int value) {
        matrix[from][to] = value;
        matrix[to][from] = value;
    }
}

基于静态辅助方法，我构建了一个 Graph<T> 对象：

public static class Graph<T extends Comparable<T>> {
    private final List<T> nodeList;
    private final int[][] adjacencyMatrix;
    private final int[] componentMapping;

    public Graph(Map<T, List<T>> graph) {
        var nodeSet = getNodeSet(graph);
        nodeList = new ArrayList<>(nodeSet);
        adjacencyMatrix = getAdjacencyMatrix(graph, nodeSet);
        componentMapping = new int[nodeList.size()];
        updateComponentMapping();
    }

// ...

我在 componentMapping 中填充 ID 以标记连接的组件：

//...

    private void updateComponentMapping() {
        IntStream.range(0, componentMapping.length).forEach(
            i -> componentMapping[i] = i
        );

  
        int componentId;
        for (int i = 0; i < componentMapping.length; i++) {
            componentId = componentMapping[i];

            for (int j = i; j < componentMapping.length; j++) {

                if (adjacencyMatrix[i][j] == 1 && componentMapping[j] == j) {
                    componentMapping[j] = componentId;
                }
            }
        }
    }

//...

之后打印就很简单了：

//...

    public int getNodeId(T node) {
        int index = nodeList.indexOf(node);

        if (0 <= index && index < nodeList.size()) {
            return index;
        } else {
            throw new IllegalArgumentException("Node index is out of range.");
        }
    }

    public int getComponentId(T node) {
        return componentMapping[getNodeId(node)];
    }

    public void printAllConnections() {
        printComponentConnections(-1);
    }

    public void printComponentConnections(int componentId) {
        StringJoiner result = new StringJoiner("','", "['", "']");

        nodeList.forEach(
            from -> {
                if (getComponentId(from) == componentId || componentId < 0) {
                    nodeList.forEach(
                        to ->  {
                            if (isConnected(from, to)) {
                                result.add(String.format("%s - %s", from, to));
                            }
                        }
                    );
                }});
        System.out.println(result);
    }

    public boolean isConnected(T from, T to) {
        return isConnected(getNodeId(from), getNodeId(to));
    }

    public boolean isConnected(int indexFrom, int indexTo) {
        return indexFrom == indexTo
            ? adjacencyMatrix[indexFrom][indexTo] == 1
            : componentMapping[indexFrom] == componentMapping[indexTo];
    }

//...

但是我们也需要新的连接，所以有 addConnection 和它的助手：

//...
    public void addConnections(T from, List<T> to) {
        int fromIndex = getNodeId(from);
        to.forEach(node -> connect(fromIndex, getNodeId(node)));
        updateComponentMapping();
    }

    private void connect(int from, int to) {
        set(from, to, 1);
    }

    private void disconnect(int from, int to) {
        set(from, to, 0);
    }

    private void set(int from, int to, int value) {
        setAdjacency(adjacencyMatrix, from, to, value);
    }
//...

最后...

private static final Map<String, List<String>> graphMap =
    Map.of(
        "a", List.of("b", "c"),
        "d", List.of("e", "f"),
        "k", List.of("l"),
        "x", List.of("y", "z"));

public static void main(String[] args) {
    var graph = new Graph<>(graphMap);
    graph.addConnections("a", List.of("d", "k"));

    int componentId = graph.getComponentId("a");
    graph.printComponentConnections(componentId);
    //graph.printAllConnections();
}

---

我是大 O 表示法的新手，但我认为：

• 第一次构建邻接矩阵：O(n²)
• 向邻接矩阵添加新连接：O(1)
• 更新组件映射：O(n²)
• 打印连接也是：O(n²)