吃包子引发的问题……

简介: 吃包子引发的问题……

吃包子引发的问题……

今天早上,小豆吃了十个包子,然后感慨了一句,早知道吃第十个包子能吃饱,我直接吃第十个就好了,前面还能省下九个。

emmm……


在实际生活中,有很多事情存在先后的依赖性,就像前面吃了九个包子,第十个包子才能吃饱。穿衣服时,先穿内衣再穿外套。在学校里,需要学完A课程和B课程,然后才能选修C课程。

那么我们如果通过两两课程之间的关系,找出修完所有的课程的完整关系呢?


这个问题就是一个拓扑排序的问题,很像在图中寻找一条路径,从起点到终点,每一步像一个节点走到另一个节点。

但是拓扑排序得到的最后序列一定是唯一的吗?


来看一下吃包子的问题,第十个包子吃饱了建立在前九个包子的基础上,但是前九个包子什么顺序吃,并不是确定的。你可以先吃第一个,也可以先吃第二个,反正最后是要把前九个吃完,吃第十个才会饱。拓扑排序的结果并不是唯一的。

我们可以使用有向图表示顶点之间的关系,还有一点,这必须是一个有向无环图,如果存在环,那么就会进入死循环,拓扑排序就凉凉了。

我们先来看看第一种实现的算法——Kahn 算法,这种方法是使用了贪心的思想,思路极其简单。

假设当 s 需要在 t 之前执行时,我们就添加一条 s 指向 t 的边,如果一个顶点的入度为 0 ,那么没有任何事情要在这个顶点之前执行,它就可以执行了。

要做的就是寻找入度为 0 的节点,然后把它们打印出来,这个顶点达到的下一个顶点的入度减一操作。然后以这些顶点为基础的顶点,最后会变成入度为 0 的顶点,我们重复上面的操作,直到所有顶点都被打印输出一遍。这时候输出的序列就是满足依赖关系的序列。

这里做了两次不同的代码比较,发现了一些不一样的东西。

使用数组加链表的数据结构存放数据。当 s 指向 t 时,有两种不同的存储方式,t 的链表中添加 s,或者 s 的链表中 添加 t。


先来瞅瞅 t 中添加 s 的代码。

class GraphMe {
    public int v;// 顶点数量
    public LinkedList<Integer>[] adj;
    public GraphMe(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();
        }
    }
    public void add(int s, int t) {
        adj[t].add(s);// t 中添加 s 
    }
}

拓扑排序实现代码

public void topoSort(GraphMe graph) {
    int v = graph.v;
    int[] status = new int[v];
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < v; i++) {
        status[i] = graph.adj[i].size();
        if (status[i] == 0) {
            queue.add(i);
        }
    }
    while (!queue.isEmpty()) {
        int temp = queue.poll();
        System.out.println(temp);
        for (int i = 0; i < v; i++) {
            if (status[i] != 0) {
                if (graph.adj[i].contains(temp)) {
                    status[i]--;
                    if (status[i] == 0) {
                        queue.add(i);
                    }
                }
            }
        }
    }
}


再来瞅瞅 s 中添加 t 的代码实现

public class Graph {
    public int v;// 顶点数量
    public LinkedList<Integer>[] adj;
    public Graph(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();
        }
    }
    public void add(int s, int t) {
        adj[s].add(t);// s 中添加 t 
    }
}

对应的排序代码

public void topoSort(Graph graph) {
    int v = graph.v;
    // 统计节点的入度数量
    int[] status = new int[v];
    for (int i = 0; i < v; i++) {
        List<Integer> list = graph.adj[i];
        for (int j = 0; j < list.size(); j++) {
            status[list.get(j)]++;
        }
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < v; i++) {
        if (status[i] == 0) {
            queue.add(i);
        }
    }
    while (!queue.isEmpty()) {
        int k = queue.poll();
        System.out.println(k);
        List<Integer> list = graph.adj[k];
        for (int temp : list) {
            if (--status[temp] == 0) {
                queue.add(temp);
            }
        }
    }

看起来好像差别也没那么大,emmm……

另外就是还可以使用 DFS 算法,通过深度优先遍历,遍历图中所有的顶点,这个下次一定实现……

如果存在环的情况下,那么怎么判断顶点之间存在环呢?

目录
打赏
0
0
0
0
91
分享
相关文章
Docker容器内不能联网的6种解决方案
Docker容器内不能联网的6种解决方案   注:下面的方法是在容器内能ping通公网IP的解决方案,如果连公网IP都ping不通,那主机可能也上不了网(尝试ping 8.
11711 2
极智AI | 一文看懂昇腾达芬奇架构计算单元
本文详细解释了昇腾达芬奇架构中计算单元的架构与计算原理。
1487 0
【Ubuntu系统更换清华大学镜像源【详解】】
Ubuntu是一种基于Debian的Linux操作系统,它的软件仓库中包含了许多开源软件包。由于全球用户的数量众多,因此Ubuntu的官方镜像源可能会受到访问压力的影响而变得较慢。为了避免这种情况,我们可以将Ubuntu系统的镜像源切换到清华大学镜像源。本文将详细介绍如何在Ubuntu系统中更换清华大学镜像源。
3286 0
火热招募|第八届“创客中国”钉钉低代码大赛正式开启
6月16日,由钉钉发起,中华人民共和国工业和信息化部网络安全产业发展中心、浙江省经济和信息化厅共同举办的第八届“创客中国”钉钉低代码大赛(以下简称“大赛”)宣布正式启动。大赛将面向全社会发起低代码应用征集评选,鼓励人人成为开发者,利用低代码发挥创意解决行业问题,同时推广普及低代码技术,助力企业加速实现数字化转型。
554 1
3DMAX2023软件序列号免费3D建模软件下载
3DMAX作为国内知名较高的3D建模软件,自然很多设计的朋友都在使用。难道你不知道成年人的世界干啥都觉得累,不巧的是,我去年刚成年,今年就选择了线上学习3D建模。到现在学习了8个月,自我感觉超级好,一点都不觉得累,还完成小道具的建模外包,赚到了在建模上的第一桶金。第一次听到3D建模的时候,说实话,虽然我热爱电竞,但除了“难”,我脑海里想不到别的词来形容了。接触之后才知道啥叫“只要肯开挂,世上就无难事”。所以我就偷偷在大佬群里混了1个多月,默默保存了所有的入门的资料。不过这终归也算是学习,不仅要自己认真学,还一定要勇于提问!我就抱着这个心态在这个免费群里混迹,几乎解决了我目前3D建模道路上所有遇
1897 9
Nacos: Namespace 和 Endpoint 在生产环境下的最佳实践
随着使用 Nacos 的企业越来越多,遇到的最频繁的两个问题就是:如何在我的生产环境正确的来使用 namespace 以及 endpoint。这篇文章主要就是针对这两个问题来聊聊使用 nacos 过程中关于这两个参数配置的最佳实践方式。
4114 62
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问