Java数据结构——应用DFS算法计算流程图下游节点（1）

╰+哭是因爲堅強的太久メ 2024-02-21 08:52 6阅读 0赞

## 问题描述： ##

![04698e5601c442099be2238e04360b9b.png][]

前端在绘制流程图的时候，某些情况需要对某个节点之后的流程图进行折叠，因此需要得到某个节点的ID后，计算出这个ID下游之后的所有节点（找到的节点，边也就找到了）

## 已知条件： ##

某个节点的ID，流程图解析成对应的JSON对象文件（有的是将流程图解析成XML文件）

例如：

{
        "nodes": [
            {
                "id": "A"
            },
            {
                "id": "B"
            },
            {
                "id": "C"
            }
        ],
        "edges": [
            {
                "sourceNode": "A",
                "targetNode": "B"
            },
            {
                "sourceNode": "B",
                "targetNode": "C"
            }
        ]
    }

## 问题解决： ##

import com.alibaba.fastjson2.JSONArray;
    import com.alibaba.fastjson2.JSONObject;
    
    import java.util.*;
    
    public class FlowChartDFS {
    
        // 定义节点类
        static class Node {
            public String id; // 节点ID
            public Set<String> nextNodes = new HashSet<>(); // 存放下游节点id的集合
    
            public Node(String id) {
                this.id = id;
            }
        }
    
        // 定义边类
        static class Edge {
            public String sourceNode; // 边的起始节点ID
            public String targetNode; // 边的目标节点ID
    
            public Edge(String sourceNode, String targetNode) {
                this.sourceNode = sourceNode;
                this.targetNode = targetNode;
            }
        }
    
        // 解析JSON数据，构建节点和边的关系图
        public static Map<String, Node> buildGraphFromJson(String jsonStr) {
    
            JSONObject flowChartJson = JSONObject.parseObject(jsonStr);
            JSONArray nodesJson = flowChartJson.getJSONArray("nodes");
            JSONArray edgesJson = flowChartJson.getJSONArray("edges");
    
            Map<String, Node> graph = new HashMap<>();
            for (int i = 0; i < nodesJson.size(); i++) {
                JSONObject nodeJson = nodesJson.getJSONObject(i);
                String nodeId = nodeJson.getString("id");
                Node node = new Node(nodeId);
                graph.put(nodeId, node);
            }
            for (int i = 0; i < edgesJson.size(); i++) {
                JSONObject edgeJson = edgesJson.getJSONObject(i);
                String sourceNodeId = edgeJson.getString("sourceNode");
                String targetNodeId = edgeJson.getString("targetNode");
                Node sourceNode = graph.get(sourceNodeId);
                sourceNode.nextNodes.add(targetNodeId);
            }
            return graph;
        }
    
        // DFS深度优先递归搜索指定节点的下游所有节点和边
        public static void dfs(String startNodeId, Set<String> visitedNodeIds, List<Edge> edges, Map<String, Node> graph) {
            Node node = graph.get(startNodeId);
            if (node == null || visitedNodeIds.contains(startNodeId)) {
                return;
            }
            visitedNodeIds.add(startNodeId);
            for (String nextNodeId : node.nextNodes) {
                Edge edge = new Edge(startNodeId, nextNodeId); // 记录边的信息
                edges.add(edge);
                // 递归循环
                dfs(nextNodeId, visitedNodeIds, edges, graph);
            }
        }
    
        public static void main(String[] args) {
            // JSON数据示例
            String jsonStr = "{\"nodes\": [{\"id\": \"A\"},{\"id\": \"B\"},{\"id\": \"C\"}], \"edges\": [{\"sourceNode\": \"A\", \"targetNode\": \"B\"},{\"sourceNode\": \"B\",\"targetNode\": \"C\"}]}";
    
            // 构建关系图
            Map<String, Node> graph = buildGraphFromJson(jsonStr);
    
            // 指定起始节点ID
            String startNodeId = "A";
    
            // 初始化已访问节点集合和边列表
            Set<String> visitedNodeIds = new HashSet<>();
            List<Edge> edges = new ArrayList<>();
    
            // 进行DFS深度优先搜索
            dfs(startNodeId, visitedNodeIds, edges, graph);
    
            // 输出搜索结果
            System.out.println("节点" + startNodeId + "的下游节点和边：");
            for (Edge edge : edges) {
                System.out.println(edge.sourceNode + "->" + edge.targetNode);
            }
        }
    }

![d5406cbeb15049aa905eae8d2cad7e32.png][]

## 补充：[gson/UserGuide.md at main · google/gson · GitHub][gson_UserGuide.md at main _ google_gson _ GitHub] ##

## 引入Gson依赖 ##

<dependency>
                <groupId>com.google.code.gson</groupId>
                <artifactId>gson</artifactId>
                <version>2.10.1</version>
            </dependency>

## [在线json格式化，json在线解析格式化，在线json验证，json格式化工具，json压缩-在线JSON (zxjson.com)][json_json_json_json_json_-_JSON _zxjson.com] ##

## [JSON代码工具 - 代码工具 - 脚本之家在线工具 (jb51.net)][JSON_ - _ - _ _jb51.net] ##

## 使用Gson将JSON对象转换为字符串 ##

Gson gson = new Gson();
    String jsonString = gson.toJson();

[04698e5601c442099be2238e04360b9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/5c425e33ad924d349e4d3f540e41ae65.png
[d5406cbeb15049aa905eae8d2cad7e32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/926cc0b84fc04c22a1946cfc8709fc95.png
[gson_UserGuide.md at main _ google_gson _ GitHub]: https://github.com/google/gson/blob/main/UserGuide.md
[json_json_json_json_json_-_JSON _zxjson.com]: https://zxjson.com/
[JSON_ - _ - _ _jb51.net]: http://tools.jb51.net/code/json