17.4:图的拓扑排序

这篇具有很好参考价值的文章主要介绍了17.4:图的拓扑排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

拓扑序一定是有向无环图。

拓扑排序不唯一

17.4:图的拓扑排序
17.4:图的拓扑排序

拓扑排序方法一:

利用入度为零进行排序

思路:谁的入度为0,谁就是开始节点,将开始节点打印完之后,将开始节点的直接邻居的入度减1,然后重复。

17.4:图的拓扑排序

package algorithmbasic.class17;

import java.util.*;

//图的拓扑排序
public class TopologySort {
    public static List<Node> sortedTopology(Graph graph) {
        //result用来盛放排序结果。
        List<Node> result = new ArrayList<>();
        //inmap存放节点与入度的对应值。
        //key ——> 某个节点, value ——> 剩余入度
        HashMap<Node, Integer> inmap = new HashMap<>();
        //只有节点的入度为0才可以进入此队列。
        Queue<Node> inZeroQueue = new LinkedList<>();

        for (Node node : graph.nodes.values()) {
            inmap.put(node, node.in);
            if (node.in == 0) {
                inZeroQueue.add(node);
            }
        }

        Node cur = inZeroQueue.poll();
        result.add(cur);
        for (Node next : cur.nexts) {
            //剩余入度减1.
            inmap.put(next, inmap.get(next) - 1);
            if (inmap.get(next) == 0) {
                inZeroQueue.add(next);
            }
        }
        return result;
    }
}

拓扑排序方法二:

利用点次进行排序。

17.4:图的拓扑排序

点次越大的,排序位置越靠前。

而且我发现可以使用递归进行求点次。我们要求0的点次,那就需要求他的直接邻居1,2,3的点次,然后对邻居的点次求和再加1,就是0的点次。我们可以将每个点的点次放在一个表里面,这个表记录着哪个节点的点次对应着多少。这样我们再求其他节点点次时直接从表里拿就行,减少重复性工作。

思路:
1:创建一个表 HashMap<DirectedGraphNode, Record> order = new HashMap<>() 用来记录每个节点对应的点次是多少。

2:遍历整个图中的每一个节点,记录其点次。

3:创建一个有序表ArrayList records = new ArrayList<>() 用来记录点次。

4:根据点次进行由大到小的排序。records.sort(new MyComparator());

5:然后再创建一个有序表ArrayList dnodes = new ArrayList<>() 根据点次的顺序记录节点。

注意为什么要创建Record这个内部类。因为在 “ 根据点次的顺序记录节点” 时,我们需要根据点次找到对应的节点,使用map是不可以的,因为点次大小有重复的。所以我们采用内部类的方法,这样每个点次都会有一一对应的节点。

package algorithmbasic.class17;
//图的拓扑排序方法二

import java.util.*;

// OJ链接:https://www.lintcode.com/problem/topological-sorting
public class TopologicalOrderDFS2 {
    /**
     * 节点内部类
     */
    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }
    
    /**
     * 点次内部类。
     */

    //记录某个节点的点次。
    public static class Record {
        public DirectedGraphNode node;
        //点次。
        public long nodes;

        public Record(DirectedGraphNode node, long nodes) {
            this.node = node;
            this.nodes = nodes;
        }
    }

    /**
     * topSort方法
     * 传入一张图的所有节点,返回排序好后的所有节点。
     */

    public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        //采用计算每个节点点次的方法。
        //建立一张表用来记录每个节点对应的点次是多少。
        HashMap<DirectedGraphNode, Record> order = new HashMap<>();
        ArrayList<Record> records = new ArrayList<>();
        ArrayList<DirectedGraphNode> dnodes = new ArrayList<>();

        //遍历图中每个节点,并记录每个节点出现的点次。
        for (DirectedGraphNode cur : graph) {
            Record record = process(cur, order);
            records.add(record);
            //order.put(cur, record);
        }
        //Arrays.sort(records,new MyComparator());
        records.sort(new MyComparator());
        for (Record r : records) {
            dnodes.add(r.node);//这就是为什么要建立Record这个内部类的原因。
        }
        return dnodes;
    }
    
    /**
     * 求点次的方法。
     */

    //传入一个节点返回这个节点的点次。在递归的过程当中每个节点的点次其实都已经记录好了。
    public static Record process(DirectedGraphNode node, HashMap<DirectedGraphNode, Record> order) {
        if (order.containsKey(node)) {
            return order.get(node);
        }
        //order中没有该点。
        long count = 0;
        for (DirectedGraphNode n : node.neighbors) {
            Record r = process(n, order);
            count += r.nodes;
        }
        Record record = new Record(node, count + 1);
        //先把当前节点及其点次放入map中然后再返回。这样我们再求其他节点点次时直接从表里拿就行,减少重复性工作。
        order.put(node, record);
        return record;
    }

    /**
     * 比较器
     */
    
    public static class MyComparator implements Comparator<Record> {
        @Override
        public int compare(Record o1, Record o2) {
            //不要将long类型数据强制转换成int类型,会出现溢出和截断的风险,导致数据出现错误。
            //例如2147483648L -> int:-2147483648
            //它超过了int类型的最大值 2147483647。当将其强制转换为int类型时,结果被截断为int类型的最小值 -2147483648。
            //return (int)(o2.nodes - o1.nodes);
            return o1.nodes == o2.nodes ? 0 : (o1.nodes > o2.nodes ? -1 : 1);
        }
    }
}

拓扑排序方法三:

根据深度进行排序

17.4:图的拓扑排序

package algorithmbasic.class17;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

public class TopologicalOrderDFS1 {

    /**
     * 节点内部类
     */

    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }

    /**
     * 深度内部类。
     */

    public static class Deep {
        public long deep;
        public DirectedGraphNode node;

        public Deep(long deep, DirectedGraphNode node) {
            this.deep = deep;
            this.node = node;
        }
    }

    /**
     * topSort方法
     */

    public static ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode, Deep> order = new HashMap<>();
        ArrayList<Deep> deeps = new ArrayList<>();
        ArrayList<DirectedGraphNode> dNodes = new ArrayList<>();

        for (DirectedGraphNode node : graph) {
            Deep d = process(node, order);
            deeps.add(d);
        }
        deeps.sort(new MyComparator());
        for (Deep d : deeps) {
            dNodes.add(d.node);
        }
        return dNodes;
    }


    public static Deep process(DirectedGraphNode node, HashMap<DirectedGraphNode, Deep> order) {
        if (order.containsKey(node)) {
            return order.get(node);
        }
        long max = Long.MIN_VALUE;
        for (DirectedGraphNode n : node.neighbors) {
            Deep d = process(n, order);
            max = Math.max(max, d.deep);
        }
        Deep deep = new Deep(max + 1, node);
        order.put(node, deep);
        return deep;
    }

    public static class MyComparator implements Comparator<Deep> {
        @Override
        public int compare(Deep o1, Deep o2) {
            return o1.deep == o2.deep ? 0 : (o1.deep > o2.deep ? -1 : 1);
        }
    }
}

文章来源地址https://www.toymoban.com/news/detail-469899.html

到了这里,关于17.4:图的拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构——有向图】有环无环判定、拓扑排序(DFS、BFS)

    有向图(Directed Graph),也被称为有向图形或方向图,是一种图的类型。在有向图中,图中的边具有方向,从一个顶点指向另一个顶点。 在有向图中,每个顶点表示一个实体,而有向边则表示实体之间的关系或连接。这种有方向性的边表明了连接的起点和终点之间的单向关系

    2024年02月09日
    浏览(47)
  • 有向无环图的应用—描述表达式、AOV网、AOE网

    目录 一、有向无环图描述表达式 二、拓扑排序 相关概念  实现方法  算法代码  补充 三、关键路径 相关概念  算法步骤  补充  四、总结图的应用我们都学了什么 有向无环图 :若一个有向图中不存在环,则称为有向无环图,简称DAG图。  对于一个表达式 ( (a+b)* ( b*(c+d)

    2024年02月12日
    浏览(43)
  • 有向图的拓扑排序

    拓扑排序 。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到

    2024年02月09日
    浏览(44)
  • 2023-8-29 有向图的拓扑排序

    题目链接:有向图的拓扑排序

    2024年02月11日
    浏览(34)
  • 教学计划编制问题(数据结构 有向图 拓扑排序)

     本文对以下教学计划编制问题的解决作出实现,主要使用c语言(带一点cpp),开发环境为codeblocks 17.12,希望对各位读者有所帮助。(源码和数据文件可在主页获取,同时还有使用视频文件压缩包,数据文件需要和exe在同一目录下,结合某读者的意见同时放到github了 ) 地址如下

    2024年02月09日
    浏览(54)
  • 图的拓扑排序

            拓扑排序是一个 有向无环图(有向图、弧不形成闭环) 的所有顶点的线性序列。该线性序列中,图的每个顶点只出现一次,若顶点A到顶点B之间存在有向弧v1,v2,则顶点A一定在顶点B前面。             图的拓扑排序实现很简单,基本操作思想:         1、开

    2024年02月13日
    浏览(33)
  • 图的拓扑排序(AOV网络)

    概念 拓扑排序是对有向无环图的顶点的一种排序. AOV网络 : 在有向图中, 用顶点表示活动或者任务, 弧表示活动或者任务间的优先关系, 则此有向图称为用顶点表示活动的网络(Activity On Vertex简称AOV网络). 拓扑序列(Topolagical Order) : 在有向无环图中, 若存在顶点v i 到顶点v j 的路径

    2024年01月22日
    浏览(37)
  • 【数据结构与算法】图的遍历与拓扑排序

    再上一篇中我们讲了树的两种存储方式:【数据结构与算法】图——邻接表与邻接矩阵 这一篇我们可以用数组来模拟邻接表。 假设现在我们要进行n次操作,实现无向图。 首先需要一个 保存是哪个节点 的数组 e 然后就是类似指针数组的 表 h ,每个表都会连一串单链表 e,ne

    2024年02月04日
    浏览(44)
  • 搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

    往深里搜,搜到叶子结点那里,回溯,到可以继续到叶子结点深搜的位置。 1、回溯一定要恢复现场 2、定义一个与当前递归层数有关的终止条件(题目要求的东西) 3、每层都用循环判断是否存在可以dfs的路 输出数字组合 全排列的思想解决n皇后问题,用三个bool数组描述限制

    2024年02月19日
    浏览(46)
  • 【数据结构】有向无环图(AOE-网)的关键路径(C语言)

    把用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间的有向无环图称为 边表示活动的网 ,简称 AOE-网 。 在AOE-网中存在唯一的、入度为0的顶点,称为 源点 ;存在唯一的、出度为0的顶点,称为 汇点 。从源点到汇点的最长路径长度即为完成整个工程任务所需的

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包