简单无向非连通图指定连通分量全连接查询及Java方法实现

实现注意事项 #

• 你原代码中用Map.of和List.of创建的是不可变集合，无法新增边，需要先将存储结构改为可变的HashMap和ArrayList，同时补全无向图的反向边初始化，示例初始化代码如下：

import java.util.*;

private final Map<String, List<String>> graph = new HashMap<>();

// 初始化图结构（构造块中执行）
{
    // 补全所有无向边的双向存储
    graph.put("a", new ArrayList<>(List.of("b", "c")));
    graph.put("b", new ArrayList<>(List.of("a")));
    graph.put("c", new ArrayList<>(List.of("a")));
    graph.put("d", new ArrayList<>(List.of("e", "f")));
    graph.put("e", new ArrayList<>(List.of("d")));
    graph.put("f", new ArrayList<>(List.of("d")));
    graph.put("k", new ArrayList<>(List.of("l")));
    graph.put("l", new ArrayList<>(List.of("k")));
    graph.put("x", new ArrayList<>(List.of("y", "z")));
    graph.put("y", new ArrayList<>(List.of("x")));
    graph.put("z", new ArrayList<>(List.of("x")));
}

apply方法实现 #

public void apply(String connectFrom, List<String> connectTos) {
    // 1. 新增传入的无向连接关系
    for (String toNode : connectTos) {
        // 添加connectFrom到toNode的边
        graph.computeIfAbsent(connectFrom, k -> new ArrayList<>()).add(toNode);
        // 无向图需要同步添加反向边
        graph.computeIfAbsent(toNode, k -> new ArrayList<>()).add(connectFrom);
    }

    // 2. BFS遍历获取connectFrom所在连通分量的所有节点
    Set<String> componentNodes = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
    queue.add(connectFrom);
    componentNodes.add(connectFrom);

    while (!queue.isEmpty()) {
        String current = queue.poll();
        List<String> neighbors = graph.getOrDefault(current, Collections.emptyList());
        for (String neighbor : neighbors) {
            if (!componentNodes.contains(neighbor)) {
                componentNodes.add(neighbor);
                queue.add(neighbor);
            }
        }
    }

    // 3. 生成所有双向连接，节点按字母排序保证输出顺序和示例一致
    List<String> sortedNodes = new ArrayList<>(componentNodes);
    Collections.sort(sortedNodes);
    List<String> output = new ArrayList<>();
    for (String u : sortedNodes) {
        for (String v : sortedNodes) {
            if (!u.equals(v)) {
                output.add(String.format("%s - %s", u, v));
            }
        }
    }

    // 4. 输出结果
    System.out.println(output);
}

验证说明 #

调用apply("a", List.of("d", "k"))时，输出结果和你给出的预期完全一致，不会包含x/y/z所在的独立连通分量内容。

内容的提问来源于stack exchange，提问作者gshri1986