文档章节

无回路有向图的拓扑排序

兜兜毛毛
 兜兜毛毛
发布于 09/23 12:07
字数 1008
阅读 17
收藏 0

因公司业务需要,在表单中每个字段都会配置自动计算,但自动计算公式中会引用到其他字段中的值。所以希望可以根据计算公式,优先计算引用的公式。所以最终使用了无回路有向图的扩扑排序来实现。

直接上代码,后边讲解实现思路。

/**
 * 无回路有向图(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));

    }
}

无回路有向图拓扑排序

© 著作权归作者所有

兜兜毛毛

兜兜毛毛

粉丝 16
博文 33
码字总数 21391
作品 0
朝阳
技术主管
私信 提问
有向无回路图的最短路径和拓扑排序

先要了解无回路 就是这种形式的 所以如果没有这种形式的东西 就可以得出一个线性的图 这就是拓扑排序做的事了 得到这样一个图以后,就可以利用松弛技术了,只需要遍历每个点,再松弛每个点所...

qq_36523667
2018/01/18
0
0
加权有向图问题1--单源最短路径问题(Dijkstra算法和Bellman - Ford算法)

加权有向图实现 我们实现两个类,权重边类和有向图类。有向图类中组合权重边类来实现加权有向图。 权重边类实现: 加权有向图实现: Dijkstra算法 Dijkstra算法可以解决边的权重非负的最短路...

SuperHeroes
2017/12/21
69
0
AOV网和AOE网

1、AOV网 定义:在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们成为AOV网(Activity On Vertex Network),AOV网中的弧表示活...

笨拙的小Q
2016/07/04
576
0
数据结构:关键路径,利用DFS遍历每一条关键路径JAVA语言实现

这是我们学校做的数据结构课设,要求分别输出关键路径,我查遍资料java版的只能找到关键路径,但是无法分别输出关键路径 c++有可以分别输出的,所以在明白思想后自己写了一个java版的 函数带...

dark_Souls
02/07
0
0
图论算法 有图有代码 万字总结 向前辈致敬

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/45827145 图的定义 背景知识 看到这篇博客相信一开始映入读者眼...

nomasp
2015/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kylin构建Cube过程详解

1 前言 在使用Kylin的时候,最重要的一步就是创建cube的模型定义,即指定度量和维度以及一些附加信息,然后对cube进行build,当然我们也可以根据原始表中的某一个string字段(这个字段的格式...

大数据技术进阶
17分钟前
4
0
Git保存密码

保存密码 $ git config --global credential.helper store 参数 --global 设置全局,如果用 --local 则只设置当前库 要注意保存时是用明文保存的,所以不要在公用电脑使用...

编程老陆
19分钟前
4
0
ofcms 说明文档

一、模板说明 项目概述 java 版CMS系统、基于java技术研发的内容管理系统、功能:栏目模板自定义、内容模型自定义、多个站点管理、在线模板页面编辑等功能、代码完全开源、MIT授权协议。 技术...

kuchawyz
26分钟前
4
0
理解CSS相对定位和固定定位

本文转载于:专业的前端网站➦理解CSS相对定位和固定定位 前面的话   一般地,说起定位元素是指position不为static的元素,包括relative、absolute和fixed。前面已经详细介绍过absolute绝对...

前端老手
36分钟前
4
0
iOS Xcode升级包地址(感谢大神)

下载地址:DeviceSupport

_____1____
50分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部