吃包子引发的问题……

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

吃包子引发的问题……

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

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
分享
相关文章
极智AI | 一文看懂昇腾达芬奇架构计算单元
本文详细解释了昇腾达芬奇架构中计算单元的架构与计算原理。
1483 0
【Ubuntu系统更换清华大学镜像源【详解】】
Ubuntu是一种基于Debian的Linux操作系统,它的软件仓库中包含了许多开源软件包。由于全球用户的数量众多,因此Ubuntu的官方镜像源可能会受到访问压力的影响而变得较慢。为了避免这种情况,我们可以将Ubuntu系统的镜像源切换到清华大学镜像源。本文将详细介绍如何在Ubuntu系统中更换清华大学镜像源。
3280 0
Docker容器内不能联网的6种解决方案
Docker容器内不能联网的6种解决方案   注:下面的方法是在容器内能ping通公网IP的解决方案,如果连公网IP都ping不通,那主机可能也上不了网(尝试ping 8.
11704 2
第四范式首席科学家杨强教授:未来人工智能会让二流科学家失业
近日,机器之心对杨强教授进行了专访,他对迁移学习、人工智能行业与技术进行了深入讲解,并对人工智能从业者提供了众多有价值的建议。
647 0
第四范式首席科学家杨强教授:未来人工智能会让二流科学家失业
SpringBoot+Vue 完整的外卖系统,手机端和后台管理,附源码!
SpringBoot+Vue 完整的外卖系统,手机端和后台管理,附源码!
638 0
SpringBoot+Vue 完整的外卖系统,手机端和后台管理,附源码!

热门文章

最新文章

登录插画

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

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