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

流程图下游节点（1）"/>

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

问题描述：

前端在绘制流程图的时候，某些情况需要对某个节点之后的流程图进行折叠，因此需要得到某个节点的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; // 节点IDpublic Set<String> nextNodes = new HashSet<>(); // 存放下游节点id的集合public Node(String id) {this.id = id;}}// 定义边类static class Edge {public String sourceNode; // 边的起始节点IDpublic String targetNode; // 边的目标节点IDpublic 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);// 指定起始节点IDString 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);}}
}

补充：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)

JSON代码工具 - 代码工具 - 脚本之家在线工具 (jb51)

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

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