快捷導(dǎo)航

Java實(shí)現(xiàn)計(jì)算圖中兩個(gè)頂點(diǎn)的所有路徑

更新時(shí)間：2022年10月27日 09:01:16 作者：JAVA旭陽

這篇文章主要為大家詳細(xì)介紹了如何利用Java語言實(shí)現(xiàn)計(jì)算圖中兩個(gè)頂點(diǎn)的所有路徑功能，文中通過示例詳細(xì)講解了實(shí)現(xiàn)的方法，需要的可以參考一下

前言

最近公司的項(xiàng)目上有個(gè)需求，還挺有分享價(jià)值的，這邊做個(gè)記錄。需求大致如下，下面的一個(gè)流程圖，點(diǎn)擊條件線上選擇的內(nèi)容，必須是前面配置過的節(jié)點(diǎn)，如果不是，需要在保存的時(shí)候做強(qiáng)校驗(yàn)提示。

需求其實(shí)很明確，抽象出來就是獲取圖中兩個(gè)頂點(diǎn)之間所有可達(dá)路徑的頂點(diǎn)集合，大家可以思考下，該如何實(shí)現(xiàn)？這里面涉及到了數(shù)據(jù)結(jié)構(gòu)中圖相關(guān)知識(shí)，而數(shù)據(jù)結(jié)構(gòu)算法也是本事最大的弱項(xiàng)，還是廢了我一番工夫。

抽象數(shù)據(jù)模型

實(shí)際上，看到這個(gè)需求就很容易想到我們的有向圖，那么在java中該用怎么樣的數(shù)據(jù)結(jié)構(gòu)表示有向圖呢？在惡補(bǔ)了一番圖相關(guān)的知識(shí)以后，最終確定用"鄰接表"的方式實(shí)現(xiàn)。鄰接表是圖的一種最主要存儲(chǔ)結(jié)構(gòu),用來描述圖上的每一個(gè)點(diǎn)。

我們假設(shè)下面的一個(gè)有向圖：

那么可以抽象出下面的數(shù)據(jù)結(jié)構(gòu)：

不知道大家發(fā)現(xiàn)規(guī)律了嗎，每個(gè)頂點(diǎn)關(guān)聯(lián)了它關(guān)聯(lián)的其他頂點(diǎn)，比如A通過邊關(guān)聯(lián)了B,C,D, 可以理解為A有3條邊，他們的目標(biāo)頂點(diǎn)是B,C,D，那如何用java表示呢？

代碼實(shí)現(xiàn)數(shù)據(jù)模型

1.頂點(diǎn)類Vertex

/**
 * 頂點(diǎn)
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Vertex {
    /**
     * 頂點(diǎn)id
     */
    private String id;

    /**
     * 頂點(diǎn)的名稱
     */
    private String name;

    /**
     * 頂點(diǎn)發(fā)散出去的邊信息
     */
    private List<Edge> edges = new ArrayList<>();

}

成員變量edges表示頂點(diǎn)關(guān)聯(lián)的所有的邊

2.頂點(diǎn)關(guān)聯(lián)的邊類Edge

/**
 * 邊
 */
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Edge {

    /**
     * 邊的目標(biāo)id
     */
    private String targetVertexId;

    /**
     * 邊的id
     */
    private String id;

    /**
     * 邊的名稱
     */
    private String name;
}

成員變量targetVertexId用來存儲(chǔ)邊的目標(biāo)頂點(diǎn)id

3.創(chuàng)建有向圖DirectedDiagraph

/**
 * 有向圖
 *
 * @author alvin
 * @date 2022/10/26
 * @since 1.0
 **/
@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {

    /**
     * 有向圖的的頂點(diǎn)信息
     */
    private Map<String, Vertex> vertextMap = new HashMap<>();

    /**
     * 邊的數(shù)量
     */
    private int edgeNum;

    /**
     * 添加頂點(diǎn)信息
     *
     * @param vertexId   頂點(diǎn)的id
     * @param vertexName 頂點(diǎn)的名稱
     */
    public void addVertex(String vertexId, String vertexName) {
        if (StrUtil.isEmpty(vertexId)) {
            throw new RuntimeException("頂點(diǎn)id不能為空");
        }

        Vertex node = new Vertex().setId(vertexId).setName(vertexName);
        // 添加到有向圖中
        vertextMap.put(vertexId, node);
    }

    /**
     * 添加邊信息
     *
     * @param fromVertexId   邊的起始節(jié)點(diǎn)
     * @param targetVertexId 邊的目標(biāo)節(jié)點(diǎn)
     * @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("邊的起始頂點(diǎn)或者目標(biāo)頂點(diǎn)不能為空");
        }
        Edge edge = new Edge().setTargetVertexId(targetVertexId).setId(edgeId).setName(edgeName);
        // 獲取頂點(diǎn)
        Vertex fromVertex = vertextMap.get(fromVertexId);
        // 添加到邊中
        fromVertex.getEdges().add(edge);
        // 邊的數(shù)量+1
        edgeNum++;
    }

    /**
     * 添加邊信息
     * @param fromVertexId   邊的起始節(jié)點(diǎn)
     * @param targetVertexId 邊的目標(biāo)節(jié)點(diǎn)
     */
    public void addEdge(String fromVertexId, String targetVertexId) {
        this.addEdge(fromVertexId, targetVertexId, null, null);
    }

    /**
     * 獲取圖中邊的數(shù)量
     */
    public int getEdgeNum() {
        return edgeNum;
    }

}

成員變量vertextMap存儲(chǔ)圖中的頂點(diǎn)信息
addVertex() 方法用來添加頂點(diǎn)數(shù)據(jù)
addEdge()方法用來添加邊數(shù)據(jù)

計(jì)算兩個(gè)頂點(diǎn)之間路徑算法

回到前言的需求，目前圖的數(shù)據(jù)模型已經(jīng)創(chuàng)建好了，現(xiàn)在需要實(shí)現(xiàn)計(jì)算兩個(gè)頂點(diǎn)之間可達(dá)路徑的所有頂點(diǎn)集合，直接上代碼。

由于用到的參數(shù)比較多，這邊封裝了一個(gè)算法的類CalcTwoVertexPathlgorithm

calcPaths()方法就是算法的核心入口
成員變量allPathList中存放了所有可達(dá)的路徑列表。
printAllPaths()方法打印所有的路徑。
getAllVertexs()返回所有可達(dá)的頂點(diǎn)集合。

/**
* 計(jì)算兩個(gè)頂點(diǎn)之間路徑的算法
*/
@Slf4j(topic = "a.CalcTwoVertexPathlgorithm")
class CalcTwoVertexPathlgorithm {

/**
 * 起始頂點(diǎn)
 */
private String fromVertexId;

/**
 * 查詢的目標(biāo)頂點(diǎn)
 */
private String toVertextId;

/**
 * 當(dāng)前的圖
 */
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);
    });
}

/**
 * 獲取兩點(diǎn)之間所有可能的頂點(diǎn)數(shù)據(jù)
 * @return
 */
public Set<String> getAllVertexs() {
    return allPathList.stream().flatMap(Collection::stream).collect(Collectors.toSet());
}

public void calcPaths() {
    // 先清理之前調(diào)用留下的數(shù)據(jù)
    allPathList.clear();

    DirectedDiagraph.Vertex fromNode = directedDiagraph.getVertextMap().get(fromVertexId);
    DirectedDiagraph.Vertex toNode = directedDiagraph.getVertextMap().get(toVertextId);
    // 無法找到邊
    if (fromNode == null || toNode == null) {
        throw new RuntimeException("頂點(diǎn)id不存在");
    }

    // 如果其實(shí)節(jié)點(diǎn)等于目標(biāo)節(jié)點(diǎn)，則也作為一個(gè)邊
    if (fromNode == toNode) {
        List<String> paths = new ArrayList<>();
        paths.add(fromVertexId);
        allPathList.add(paths);
        return;
    }

    // 遞歸調(diào)用
    coreRecGetAllPaths(fromNode, toNode, new ArrayDeque<>());
}

private void coreRecGetAllPaths(DirectedDiagraph.Vertex fromVertex, DirectedDiagraph.Vertex toVertex, Deque<String> nowPaths) {
    // 檢查是否存在環(huán)，跳過
    if (nowPaths.contains(fromVertex.getId())) {
        System.out.println("存在環(huán)");
        // 出棧
        nowPaths.pop();
        return;
    }

    // 當(dāng)前路徑加上其實(shí)節(jié)點(diǎn)
    nowPaths.push(fromVertex.getId());
    // 深度搜索邊
    for (DirectedDiagraph.Edge edge : fromVertex.getEdges()) {
        // 如果邊的目標(biāo)頂點(diǎn)和路徑的最終節(jié)點(diǎn)一直，表示找到成功
        if (StrUtil.equals(edge.getTargetVertexId(), toVertex.getId())) {
            // 將數(shù)據(jù)添加到當(dāng)前路徑中
            nowPaths.push(toVertex.getId());
            // 拷貝一份數(shù)據(jù)放到allPathList中
            List<String> findPaths = new ArrayList<>();
            findPaths.addAll(nowPaths);
            CollUtil.reverse(findPaths);
            allPathList.add(findPaths);
            // 加入了最終節(jié)點(diǎn)，返回一次
            nowPaths.pop();
            // 跳過，查詢下一個(gè)邊
            continue;
        }

        // 以邊的目標(biāo)頂點(diǎn)作為其實(shí)頂點(diǎn)，繼續(xù)搜索
        DirectedDiagraph.Vertex nextFromVertex = directedDiagraph.getVertextMap().get(edge.getTargetVertexId());
        if (nextFromVertex == null) {
            throw new RuntimeException("頂點(diǎn)id不存在");
        }
        // 遞歸調(diào)用下一次
        coreRecGetAllPaths(nextFromVertex, toVertex, nowPaths);
    }

    // 結(jié)束了，沒找到，彈出數(shù)據(jù)
    nowPaths.pop();
}

代碼注釋比較清晰的，就不再介紹了，主要是利用了深度搜索的方式+ 棧保存臨時(shí)路徑。

然后在DirectedDiagraph類中添加一個(gè)方法findAllPaths()，查找所有的路徑，如下圖：

@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
    .....
    /**
     * 獲取兩個(gè)頂點(diǎn)之間所有可能的數(shù)據(jù)
     *
     * @param fromVertexId 起始頂點(diǎn)
     * @param targetVertexId 目標(biāo)頂點(diǎn)
     * @return
     */
    public Set<String> findAllPaths(String fromVertexId, String targetVertexId) {
        CalcTwoVertexPathlgorithm calcTwoVertexPathlgorithm = new CalcTwoVertexPathlgorithm(this, fromVertexId, targetVertexId);
        // 先計(jì)算
        calcTwoVertexPathlgorithm.calcPaths();
        // 打印找到的路徑
        calcTwoVertexPathlgorithm.printAllPaths();
        // 然后返回所有的內(nèi)容
        return calcTwoVertexPathlgorithm.getAllVertexs();
    }
     ....
}

最后，我們寫個(gè)單元測(cè)試驗(yàn)證下吧。

@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);
}

創(chuàng)建的例子也是我們前面圖片中的例子，我們看下運(yùn)行結(jié)果是否符合預(yù)期。

總結(jié)

本次需求利用了圖這個(gè)數(shù)據(jù)結(jié)構(gòu)得到結(jié)果，突然感覺數(shù)據(jù)結(jié)構(gòu)和算法真的很重要，感覺現(xiàn)在的做法也不是最優(yōu)解，性能應(yīng)該也不是最佳，但是考慮到流程節(jié)點(diǎn)數(shù)據(jù)不會(huì)很多，應(yīng)該能滿足業(yè)務(wù)需求。不知道大家有沒有更好的做法呢？

以上就是Java實(shí)現(xiàn)計(jì)算圖中兩個(gè)頂點(diǎn)的所有路徑的詳細(xì)內(nèi)容，更多關(guān)于Java計(jì)算頂點(diǎn)所有路徑的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: