本次需求利用了圖這個數(shù)據(jù)結構得到結果，突然感覺數(shù)據(jù)結構和算法真的很重要，感覺現(xiàn)在的做法也不是最優(yōu)解，性能應該也不是最佳，但是考慮到流程節(jié)點數(shù)據(jù)不會很多，應該能滿足業(yè)務需求。不知道大家有沒有更好的做法呢？
前言
最近公司的項目上有個需求，還挺有分享價值的，這邊做個記錄。需求大致如下，下面的一個流程圖，點擊條件線上選擇的內(nèi)容，必須是前面配置過的節(jié)點，如果不是，需要在保存的時候做強校驗提示。
需求其實很明確，抽象出來就是獲取圖中兩個頂點之間所有可達路徑的頂點集合，大家可以思考下，該如何實現(xiàn)？這里面涉及到了數(shù)據(jù)結構中圖相關知識，而數(shù)據(jù)結構算法也是本事最大的弱項，還是廢了我一番工夫。
抽象數(shù)據(jù)模型
實際上，看到這個需求就很容易想到我們的有向圖，那么在java中該用怎么樣的數(shù)據(jù)結構表示有向圖呢？在惡補了一番圖相關的知識以后，最終確定用"鄰接表"的方式實現(xiàn)。鄰接表是圖的一種最主要存儲結構,用來描述圖上的每一個點。
我們假設下面的一個有向圖：
那么可以抽象出下面的數(shù)據(jù)結構：
不知道大家發(fā)現(xiàn)規(guī)律了嗎，每個頂點關聯(lián)了它關聯(lián)的其他頂點，比如A通過邊關聯(lián)了B,C,D, 可以理解為A有3條邊，他們的目標頂點是B,C,D，那如何用java表示呢？
代碼實現(xiàn)數(shù)據(jù)模型
1.頂點類Vertex
/**
* 頂點
*/
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Vertex {
/**
* 頂點id
*/
private String id;
/**
* 頂點的名稱
*/
private String name;
/**
* 頂點發(fā)散出去的邊信息
*/
private List<Edge> edges = new ArrayList<>();
}
成員變量edges表示頂點關聯(lián)的所有的邊。
2.頂點關聯(lián)的邊類Edge
/**
* 邊
*/
@Data
@AllArgsConstructor
@Accessors(chain = true)
@NoArgsConstructor
class Edge {
/**
* 邊的目標id
*/
private String targetVertexId;
/**
* 邊的id
*/
private String id;
/**
* 邊的名稱
*/
private String name;
}
成員變量targetVertexId用來存儲邊的目標頂點id
3.創(chuàng)建有向圖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<>();
/**
* 邊的數(shù)量
*/
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 邊的起始節(jié)點
* @param targetVertexId 邊的目標節(jié)點
* @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);
// 邊的數(shù)量+1
edgeNum++;
}
/**
* 添加邊信息
* @param fromVertexId 邊的起始節(jié)點
* @param targetVertexId 邊的目標節(jié)點
*/
public void addEdge(String fromVertexId, String targetVertexId) {
this.addEdge(fromVertexId, targetVertexId, null, null);
}
/**
* 獲取圖中邊的數(shù)量
*/
public int getEdgeNum() {
return edgeNum;
}
}
- 成員變量vertextMap存儲圖中的頂點信息
- addVertex() 方法用來添加頂點數(shù)據(jù)
- addEdge()方法用來添加邊數(shù)據(jù)
計算兩個頂點之間路徑算法
回到前言的需求，目前圖的數(shù)據(jù)模型已經(jīng)創(chuàng)建好了，現(xiàn)在需要實現(xiàn)計算兩個頂點之間可達路徑的所有頂點集合，直接上代碼。
由于用到的參數(shù)比較多，這邊封裝了一個算法的類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);
});
}
/**
* 獲取兩點之間所有可能的頂點數(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("頂點id不存在");
}
// 如果其實節(jié)點等于目標節(jié)點，則也作為一個邊
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;
}
// 當前路徑加上其實節(jié)點
nowPaths.push(fromVertex.getId());
// 深度搜索邊
for (DirectedDiagraph.Edge edge : fromVertex.getEdges()) {
// 如果邊的目標頂點和路徑的最終節(jié)點一直，表示找到成功
if (StrUtil.equals(edge.getTargetVertexId(), toVertex.getId())) {
// 將數(shù)據(jù)添加到當前路徑中
nowPaths.push(toVertex.getId());
// 拷貝一份數(shù)據(jù)放到allPathList中
List<String> findPaths = new ArrayList<>();
findPaths.addAll(nowPaths);
CollUtil.reverse(findPaths);
allPathList.add(findPaths);
// 加入了最終節(jié)點，返回一次
nowPaths.pop();
// 跳過，查詢下一個邊
continue;
}
// 以邊的目標頂點作為其實頂點，繼續(xù)搜索
DirectedDiagraph.Vertex nextFromVertex = directedDiagraph.getVertextMap().get(edge.getTargetVertexId());
if (nextFromVertex == null) {
throw new RuntimeException("頂點id不存在");
}
// 遞歸調(diào)用下一次
coreRecGetAllPaths(nextFromVertex, toVertex, nowPaths);
}
// 結束了，沒找到，彈出數(shù)據(jù)
nowPaths.pop();
}
代碼注釋比較清晰的，就不再介紹了，主要是利用了深度搜索的方式+ 棧保存臨時路徑。
然后在DirectedDiagraph?類中添加一個方法findAllPaths()，查找所有的路徑，如下圖：
@Data
@Slf4j(topic = "a.DirectedDiagraph")
public class DirectedDiagraph {
.....
/**
* 獲取兩個頂點之間所有可能的數(shù)據(jù)
*
* @param fromVertexId 起始頂點
* @param targetVertexId 目標頂點
* @return
*/
public Set<String> findAllPaths(String fromVertexId, String targetVertexId) {
CalcTwoVertexPathlgorithm calcTwoVertexPathlgorithm = new CalcTwoVertexPathlgorithm(this, fromVertexId, targetVertexId);
// 先計算
calcTwoVertexPathlgorithm.calcPaths();
// 打印找到的路徑
calcTwoVertexPathlgorithm.printAllPaths();
// 然后返回所有的內(nèi)容
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);
}
創(chuàng)建的例子也是我們前面圖片中的例子，我們看下運行結果是否符合預期。
總結
本次需求利用了圖這個數(shù)據(jù)結構得到結果，突然感覺數(shù)據(jù)結構和算法真的很重要，感覺現(xiàn)在的做法也不是最優(yōu)解，性能應該也不是最佳，但是考慮到流程節(jié)點數(shù)據(jù)不會很多，應該能滿足業(yè)務需求。不知道大家有沒有更好的做法呢？
