Brandes算法计算无向图节点最短路径之和-Java代码实现

2401_86354028

469人浏览 · 2024-09-01 01:28:21

2401_86354028 · 2024-09-01 01:28:21 发布

蜂信物联FastBee平台https://gitee.com/beecue/fastbee

阿里资料开源项目https://gitee.com/vip204888

百度低代码前端框架https://gitee.com/baidu/amis

OpenHarmony开源项目https://gitcode.com/openharmony

仓颉编程语言开放项目https://gitcode.com/Cangjie

public static void main(String[] args) {
    // 获取JSON对象，该对象包含了图的节点和边信息
    JSONObject graphJson = getJsonObject();

    // 创建邻接表表示图结构，键为节点ID，值为连接到该节点的所有节点ID列表
    Map<String, List<String>> adjacencyList = new HashMap<>();
    // 创建一个HashSet存储所有节点ID
    Set<String> nodesSet = new HashSet<>();

    // 解析JSON对象中的"nodes"数组，获取所有节点ID并添加到nodesSet中
    JSONArray nodesArray = graphJson.getJSONArray("nodes");
    for (int i = 0; i < nodesArray.length(); i++) {
        JSONObject nodeObj = nodesArray.getJSONObject(i);
        String nodeId = nodeObj.getString("id");
        nodesSet.add(nodeId);
    }

    // 解析JSON对象中的"edges"数组，构建邻接表
    JSONArray edgesArray = graphJson.getJSONArray("edges");
    for (int i = 0; i < edgesArray.length(); i++) {
        JSONObject edgeObj = edgesArray.getJSONObject(i);
        String source = edgeObj.getString("source");
        String target = edgeObj.getString("target");

        // 假设图是无向的，所以在邻接表中双向添加边
        adjacencyList.computeIfAbsent(source, k -> new ArrayList<>()).add(target);
        adjacencyList.computeIfAbsent(target, k -> new ArrayList<>()).add(source);
    }

    // 计算并存储每个节点的中介中心性
    Map<String, Double> nodeCentralities = new HashMap<>();
    for (String nodeId : nodesSet) {
        double centrality = calculateBetweennessCentrality(adjacencyList, nodeId);
        nodeCentralities.put(nodeId, centrality);
    }

    // 将节点按照其中介中心性降序排列
    List<Map.Entry<String, Double>> sortedNodes = new ArrayList<>(nodeCentralities.entrySet());
    sortedNodes.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

    // 输出每个节点及其对应的中介中心性
    System.out.println("节点：该节点到其他节点最短路径距离之和：");
    for (Map.Entry<String, Double> entry : sortedNodes) {
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }
}

// 从固定JSON字符串中创建并返回JSONObject
private static JSONObject getJsonObject() {
    String jsonData = "{\"nodes\":[\n" +
            "{\"id\":\"3.1\"},\n" +
            "{\"id\":\"4.1\"},\n" +
            "{\"id\":\"4.4\"},\n" +
            "{\"id\":\"2.3\"},\n" +
            "{\"id\":\"1.1\"},\n" +
            "{\"id\":\"1.2\"}\n" +
            "],\n" +
            "\"edges\": [\n" +
            " {\n" +
            " \"id\":\"e1\",\n" +
            " \"source\": \"3.1\",\n" +
            " \"target\": \"4.1\"\n" +
            " },\n" +
            " {\n" +
            " \"id\":\"e2\",\n" +
            " \"source\": \"4.4\",\n" +
            " \"target\": \"4.1\"\n" +
            " },\n" +
            " {\n" +
            " \"id\":\"e3\",\n" +
            " \"source\": \"3.1\",\n" +
            " \"target\": \"4.4\"\n" +
            " },\n" +
            " {\n" +
            " \"id\":\"e4\",\n" +
            " \"source\": \"4.1\",\n" +
            " \"target\": \"2.3\"\n" +
            " },\n" +
            " {\n" +
            " \"id\":\"e5\",\n" +
            " \"source\": \"4.4\",\n" +
            " \"target\": \"1.1\"\n" +
            " },\n" +
            " {\n" +
            " \"id\":\"e6\",\n" +
            " \"source\": \"1.2\",\n" +
            " \"target\": \"1.1\"\n" +
            " }\n" +
            " ]\n}";

    JSONObject graphJson = new JSONObject(jsonData);
    return graphJson;
}


// 根据给定的邻接表和节点ID，计算该节点的中介中心性
private static double calculateBetweennessCentrality(Map<String, List<String>> graph, String node) {
    // 初始化用于计算中介中心性的三个HashMap
    Map<String, Integer> sigma = new HashMap<>();
    Map<String, Double> delta = new HashMap<>();
    Map<String, Double> betweenness = new HashMap<>();

    // 初始化所有节点的sigma、delta和betweenness值
    for (String v : graph.keySet()) {
        sigma.put(v, 0);
        delta.put(v, 0.0);
        betweenness.put(v, 0.0);
    }

    // 设置当前节点的sigma值为1
    sigma.put(node, 1);

    // 创建队列（BFS）和栈（用于回溯），以及预处理器列表和距离映射表
    Queue<String> queue = new LinkedList<>();
    Stack<String> stack = new Stack<>();
    Map<String, List<String>> predecessors = new HashMap<>();
    Map<String, Integer> distances = new HashMap<>();

    // 初始化所有节点的预处理器列表和距离值
    for (String v : graph.keySet()) {
        predecessors.put(v, new ArrayList<>());
        distances.put(v, -1);
    }

    // 将当前节点加入队列，并设置距离为0
    queue.offer(node);
    distances.put(node, 0);

    // 开始广度优先搜索（BFS）
    while (!queue.isEmpty()) {
        String v = queue.poll();
        stack.push(v);

        // 遍历当前节点的所有邻居节点
        for (String w : graph.get(v)) {
            // 如果邻居节点尚未访问过，则将其加入队列，并更新距离
            if (distances.get(w) < 0) {
                queue.offer(w);
                distances.put(w, distances.get(v) + 1);
            }

            // 当前邻居节点与当前节点的距离等于二者直接相连的距离时，更新sigma值和预处理器列表
            if (distances.get(w) == distances.get(v) + 1) {
                sigma.put(w, sigma.get(w) + sigma.get(v));
                predecessors.get(w).add(v);
            }
        }
    }

    // 回溯过程，计算中介中心性
    while (!stack.isEmpty()) {
        String w = stack.pop();
        for (String v : predecessors.get(w)) {
            double c = (double) sigma.get(v) / sigma.get(w) * (1.0 + delta.get(w));
            delta.put(v, delta.get(v) + c);
            betweenness.put(w, betweenness.get(w) + c);
        }
    }

    // 计算给定节点对整个图中介中心性的贡献
    double centrality = 0.0;
    for (String v : graph.keySet()) {
        if (!v.equals(node)) {
            centrality += betweenness.get(v);
        }
    }

    // 返回该节点的中介中心性
    return centrality;
}

}


        运行结果：


![](https://img-blog.csdnimg.cn/direct/ef499503d45944fba1a944d05236a491.png)


        可以看到，节点“4.4”到其他节点的最短路径之和的值最小，因此，我们可以认为节点“4.4”就是示例图的中心节点。


![](https://img-blog.csdnimg.cn/direct/cb16e647936948659bba1829d109ad86.png)





### 最后

作为过来人，小编是整理了很多进阶架构视频资料、面试文档以及PDF的学习资料，针对上面一套系统大纲小编也有对应的相关进阶架构视频资料

![](https://img-blog.csdnimg.cn/img_convert/17976884b6b275ba96d002de68b6316a.webp?x-oss-process=image/format,png)
![](https://img-blog.csdnimg.cn/img_convert/c9c5f7d0ddab9bd0ae31e0469d89748e.webp?x-oss-process=image/format,png)

7936948659bba1829d109ad86.png)





### 最后

作为过来人，小编是整理了很多进阶架构视频资料、面试文档以及PDF的学习资料，针对上面一套系统大纲小编也有对应的相关进阶架构视频资料

[外链图片转存中...(img-v4dVAEgv-1725125291361)]
[外链图片转存中...(img-QPGeukFO-1725125291362)]