计算图中两个顶点的所有路径，你会吗-六虎

持续创造，加快生长！这是我参加「日新方案 10 月更文应战」的第28天，点击查看活动概况

前语

最近公司的项目上有个需求，还挺有分享价值的，这边做个记载。需求大致如下，下面的一个流程图，点击条件线上挑选的内容，有必要是前面装备过的节点，假如不是，需求在保存的时分做强校验提示。

需求其实很明确，抽象出来便是获取图中两个极点之间一切可达途径的极点调集，咱们能够考虑下，该如何完成？这里边涉及到了数据结构中图相关常识，而数据结构算法也是本事最大的弱项，还是废了我一番工夫。

抽象数据模型

实际上，看到这个需求就很简单想到咱们的有向图，那么在java中该用怎么样的数据结构表明有向图呢？在恶补了一番图相关的常识今后，终究确定用”邻接表”的方法完成。邻接表是图的一种最主要存储结构,用来描述图上的每一个点。

咱们假定下面的一个有向图：

那么能够抽象出下面的数据结构：

不知道咱们发现规则了吗，每个极点相关了它相关的其他极点，比如A经过边相关了B,C,D, 能够理解为A有3条边，他们的方针极点是B,C,D，那如何用java表明呢？

代码完成数据模型

极点类Vertex

/**
 * 极点
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Vertex {
    /**
     * 极点id
     */
    private String id;
    /**
     * 极点的称号
     */
    private String name;
    /**
     * 极点发散出去的边信息
     */
    private List<Edge> edges = new ArrayList<>();
}

成员变量edges表明极点相关的一切的边

极点相关的边类Edge

/**
 * 边
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Edge {
    /**
     * 边的方针id
     */
    private String targetVertexId;
    /**
     * 边的id
     */
    private String id;
    /**
     * 边的称号
     */
    private String name;
}

成员变量targetVertexId用来存储边的方针极点id

创立有向图DirectedDiagraph

/**
 * 有向图
 *
 * @author alvin
 * @date 2022/10/26
 * @since 1.0
 **/
@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
    /**
     * 有向图的的极点信息
     */
    private Map<String, Vertex> vertextMap = new HashMap<>();
    /**
     * 边的数量
     */
    private int edgeNum;
    /**
     * 增加极点信息
     *
     * @param vertexId   极点的id
     * @param vertexName 极点的称号
     */
    public void addVertex(String vertexId, String vertexName) {
        if (StrUtil.isEmpty(vertexId)) {
            throw new RuntimeException("极点id不能为空");
        }
        Vertex node = new Vertex().setId(vertexId).setName(vertexName);
        // 增加到有向图中
        vertextMap.put(vertexId, node);
    }
    /**
     * 增加边信息
     *
     * @param fromVertexId   边的开始节点
     * @param targetVertexId 边的方针节点
     * @param edgeId         边id
     * @param edgeName       边称号
     */
    public void addEdge(String fromVertexId, String targetVertexId, String edgeId, String edgeName) {
        if (StrUtil.isEmpty(fromVertexId) || StrUtil.isEmpty(targetVertexId)) {
            throw new RuntimeException("边的开始极点或许方针极点不能为空");
        }
        Edge edge = new Edge().setTargetVertexId(targetVertexId).setId(edgeId).setName(edgeName);
        // 获取极点
        Vertex fromVertex = vertextMap.get(fromVertexId);
        // 增加到边中
        fromVertex.getEdges().add(edge);
        // 边的数量+1
        edgeNum++;
    }
    /**
     * 增加边信息
     * @param fromVertexId   边的开始节点
     * @param targetVertexId 边的方针节点
     */
    public void addEdge(String fromVertexId, String targetVertexId) {
        this.addEdge(fromVertexId, targetVertexId, null, null);
    }
    /**
     * 获取图中边的数量
     */
    public int getEdgeNum() {
        return edgeNum;
    }
}

成员变量vertextMap存储图中的极点信息
addVertex() 方法用来增加极点数据
addEdge()方法用来增加边数据

核算两个极点之间途径算法

回到前语的需求，目前图的数据模型现已创立好了，现在需求完成核算两个极点之间可达途径的一切极点调集，直接上代码。

因为用到的参数比较多，这边封装了一个算法的类CalcTwoVertexPathlgorithm

calcPaths()方法便是算法的核心入口
成员变量allPathList中存放了一切可达的途径列表。
printAllPaths()方法打印一切的途径。
getAllVertexs()回来一切可达的极点调集。

/**
* 核算两个极点之间途径的算法
*/
@Slf4j(topic = "a.CalcTwoVertexPathlgorithm")
class CalcTwoVertexPathlgorithm {
/**
 * 开始极点
 */
private String fromVertexId;
/**
 * 查询的方针极点
 */
private String toVertextId;
/**
 * 当时的图
 */
private DirectedDiagraph directedDiagraph;
/**
 * 一切的途径
 */
private final List<List<String>> allPathList = new ArrayList<>();
public CalcTwoVertexPathlgorithm(DirectedDiagraph directedDiagraph, String fromVertexId, String toVertextId) {
    this.fromVertexId = fromVertexId;
    this.toVertextId = toVertextId;
    this.directedDiagraph = directedDiagraph;
}
/**
 * 打印一切的途径
 */
public void printAllPaths() {
    log.info("the path betweent {} and {}:", fromVertexId, toVertextId);
    allPathList.forEach(item -> {
        log.info("{}", item);
    });
}
/**
 * 获取两点之间一切或许的极点数据
 * @return
 */
public Set<String> getAllVertexs() {
    return allPathList.stream().flatMap(Collection::stream).collect(Collectors.toSet());
}
public void calcPaths() {
    // 先整理之前调用留下的数据
    allPathList.clear();
    DirectedDiagraph.Vertex fromNode = directedDiagraph.getVertextMap().get(fromVertexId);
    DirectedDiagraph.Vertex toNode = directedDiagraph.getVertextMap().get(toVertextId);
    // 无法找到边
    if (fromNode == null || toNode == null) {
        throw new RuntimeException("极点id不存在");
    }
    // 假如其实节点等于方针节点，则也作为一个边
    if (fromNode == toNode) {
        List<String> paths = new ArrayList<>();
        paths.add(fromVertexId);
        allPathList.add(paths);
        return;
    }
    // 递归调用
    coreRecGetAllPaths(fromNode, toNode, new ArrayDeque<>());
}
private void coreRecGetAllPaths(DirectedDiagraph.Vertex fromVertex, DirectedDiagraph.Vertex toVertex, Deque<String> nowPaths) {
    // 查看是否存在环，越过
    if (nowPaths.contains(fromVertex.getId())) {
        System.out.println("存在环");
        // 出栈
        nowPaths.pop();
        return;
    }
    // 当时途径加上其实节点
    nowPaths.push(fromVertex.getId());
    // 深度查找边
    for (DirectedDiagraph.Edge edge : fromVertex.getEdges()) {
        // 假如边的方针极点和途径的终究节点一向，表明找到成功
        if (StrUtil.equals(edge.getTargetVertexId(), toVertex.getId())) {
            // 将数据增加到当时途径中
            nowPaths.push(toVertex.getId());
            // 拷贝一份数据放到allPathList中
            List<String> findPaths = new ArrayList<>();
            findPaths.addAll(nowPaths);
            CollUtil.reverse(findPaths);
            allPathList.add(findPaths);
            // 加入了终究节点，回来一次
            nowPaths.pop();
            // 越过，查询下一个边
            continue;
        }
        // 以边的方针极点作为其实极点，持续查找
        DirectedDiagraph.Vertex nextFromVertex = directedDiagraph.getVertextMap().get(edge.getTargetVertexId());
        if (nextFromVertex == null) {
            throw new RuntimeException("极点id不存在");
        }
        // 递归调用下一次
        coreRecGetAllPaths(nextFromVertex, toVertex, nowPaths);
    }
    // 完毕了，没找到，弹出数据
    nowPaths.pop();
}

代码注释比较明晰的，就不再介绍了，主要是利用了深度查找的方法+ 栈保存暂时途径。

然后在DirectedDiagraph类中增加一个方法findAllPaths()，查找一切的途径，如下图：

@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
    .....
    /**
     * 获取两个极点之间一切或许的数据
     *
     * @param fromVertexId 开始极点
     * @param targetVertexId 方针极点
     * @return
     */
    public Set<String> findAllPaths(String fromVertexId, String targetVertexId) {
        CalcTwoVertexPathlgorithm calcTwoVertexPathlgorithm = new CalcTwoVertexPathlgorithm(this, fromVertexId, targetVertexId);
        // 先核算
        calcTwoVertexPathlgorithm.calcPaths();
        // 打印找到的途径
        calcTwoVertexPathlgorithm.printAllPaths();
        // 然后回来一切的内容
        return calcTwoVertexPathlgorithm.getAllVertexs();
    }
     ....
}

最终，咱们写个单元测试验证下吧。

@Test
public void test1() {
    DirectedDiagraph directedDiagraph = new DirectedDiagraph();
    directedDiagraph.addVertex("A", "A");
    directedDiagraph.addVertex("B", "B");
    directedDiagraph.addVertex("C", "C");
    directedDiagraph.addVertex("D", "D");
    directedDiagraph.addVertex("E", "E");
    directedDiagraph.addEdge("A", "B");
    directedDiagraph.addEdge("B", "C");
    directedDiagraph.addEdge("C", "D");
    directedDiagraph.addEdge("A", "D");
    directedDiagraph.addEdge("B", "D");
    directedDiagraph.addEdge("A", "C");
    directedDiagraph.addEdge("D", "E");
    Set<String> allPaths = directedDiagraph.findAllPaths("A", "D");
    log.info("all vertexIds: {}", allPaths);
}

创立的例子也是咱们前面图片中的例子，咱们看下运行成果是否符合预期。

总结

本次需求利用了图这个数据结构得到成果，忽然感觉数据结构和算法真的很重要，感觉现在的做法也不是最优解，功能应该也不是最佳，可是考虑到流程节点数据不会很多，应该能满意业务需求。不知道咱们有没有更好的做法呢？

计算图中两个顶点的所有路径，你会吗

前语

抽象数据模型

代码完成数据模型

核算两个极点之间途径算法

总结

相关文章

一条update语句是怎样执行的

前端开发如何做新手引导

Flink ML的新特性解析与应用

Android组件化工具-SPI

作者信息