因公司业务需要，在表单中每个字段都会配置自动计算，但自动计算公式中会引用到其他字段中的值。所以希望可以根据计算公式，优先计算引用的公式。所以最终使用了无回路有向图的扩扑排序来实现。
直接上代码，后边讲解实现思路。
代码语言：javascript复制/**
* 无回路有向图(Directed Acyclic Graph)的拓扑排序
* 该DAG图是通过邻接表实现的。
*
* @author lyz
*/
public class FieldListDG {
/**
* 邻接表中表对应的链表的顶点
*/
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
/**
* 邻接表中表的顶点
*/
private class VNode {
String data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
}
/**
* 顶点数组
*/
private List<VNode> mVexs;
/**
* 创建图(用已提供的矩阵)
* <p>
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public FieldListDG(List<String> vexs, List<List<String>> edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.size();
int elen = edges.size();
// 初始化"顶点"
mVexs = new ArrayList<>();
for (int i = 0; i < vlen; i ) {
// 新建VNode
VNode vnode = new VNode();
vnode.data = vexs.get(i);
vnode.firstEdge = null;
// 将vnode添加到数组mVexs中
mVexs.add(vnode);
}
// 初始化"边"
for (int i = 0; i < elen; i ) {
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges.get(i).get(0));
int p2 = getPosition(edges.get(i).get(1));
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if (mVexs.get(p1).firstEdge == null) {
mVexs.get(p1).firstEdge = node1;
} else {
linkLast(mVexs.get(p1).firstEdge, node1);
}
}
}
/**
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while (p.nextEdge != null) {
p = p.nextEdge;
}
p.nextEdge = node;
}
/**
* 返回String位置
*/
private int getPosition(String str) {
for (int i = 0; i < mVexs.size(); i ) {
if (mVexs.get(i).data.equals(str)) {
return i;
}
}
return -1;
}
/**
* 拓扑排序
* <p>
* 返回值：
* -1 -- 失败(由于内存不足等原因导致)
* 0 -- 成功排序，并输入结果
* 1 -- 失败(该有向图是有环的)
*/
public List<String> topologicalSort() {
int index = 0;
int num = mVexs.size();
int[] ins; // 入度数组
String[] tops; // 拓扑排序结果数组，记录每个节点的排序后的序号。
Queue<Integer> queue; // 辅组队列
ins = new int[num];
tops = new String[num];
queue = new LinkedList<>();
// 统计每个顶点的入度数
for (int i = 0; i < num; i ) {
ENode node = mVexs.get(i).firstEdge;
while (node != null) {
ins[node.ivex] ;
node = node.nextEdge;
}
}
// 将所有入度为0的顶点入队列
for (int i = 0; i < num; i ) {
if (ins[i] == 0) {
// 入队列
queue.offer(i);
}
}
// 队列非空
while (!queue.isEmpty()) {
// 出队列。j是顶点的序号
int j = queue.poll().intValue();
// 将该顶点添加到tops中，tops是排序结果
tops[index ] = mVexs.get(j).data;
// 获取以该顶点为起点的出边队列
ENode node = mVexs.get(j).firstEdge;
// 将与"node"关联的节点的入度减1；
// 若减1之后，该节点的入度为0；则将该节点添加到队列中。
while (node != null) {
// 将节点(序号为node.ivex)的入度减1。
ins[node.ivex]--;
// 若节点的入度为0，则将其"入队列"
if (ins[node.ivex] == 0) {
// 入队列
queue.offer(node.ivex);
}
node = node.nextEdge;
}
}
if (index != num) {
return Collections.emptyList();
}
List<String> labelList = Arrays.asList(tops);
Collections.reverse(labelList);
return labelList;
}
/**
* 测试用例
*/
public static void main(String[] args) {
List<String> vexs = new ArrayList<>();
vexs.add("a");
vexs.add("b");
vexs.add("c");
vexs.add("d");
vexs.add("e");
vexs.add("f");
vexs.add("g");
List<List<String>> edges = new ArrayList<>();
List<String> node = new ArrayList<>();
node.add("a");
node.add("g");
edges.add(node);
List<String> node1 = new ArrayList<>();
node1.add("a");
node1.add("c");
edges.add(node1);
List<String> node2 = new ArrayList<>();
node2.add("b");
node2.add("a");
edges.add(node2);
List<String> node3 = new ArrayList<>();
node3.add("b");
node3.add("d");
edges.add(node3);
List<String> node4 = new ArrayList<>();
node4.add("c");
node4.add("f");
edges.add(node4);
List<String> node5 = new ArrayList<>();
node5.add("c");
node5.add("g");
edges.add(node5);
List<String> node6 = new ArrayList<>();
node6.add("d");
node6.add("e");
edges.add(node6);
List<String> node7 = new ArrayList<>();
node7.add("d");
node7.add("f");
edges.add(node7);
long start = System.currentTimeMillis();
for (int i = 0; i < 10; i ) {
FieldListDG pG = new FieldListDG(vexs, edges);
// 拓扑排序
List<String> list = pG.topologicalSort();
}
System.out.println("共计时间" (System.currentTimeMillis() - start));
// list.forEach(e -> System.out.println(e));
}
}
