从分手厨房看拓扑排序

news/2024/10/31 1:28:21/

点击上方 "程序员小乐"关注, 星标或置顶一起成长

每天凌晨00点00分, 第一时间与你相约

每日英文

Don't judge people by their outlook for you don't know what stories behind their eyes. 

不要以貌取人,因为你不知道他们的双眼后面藏着什么故事。

每日掏心

这世上,没有谁活得比谁容易,只是有人在呼天抢地,有人在默默努力。

来自:Mark Lux | 责编:乐乐

链接:marklux.cn/blog/117

程序员小乐(ID:study_tech) 第 865 次推文  图源:百度

往日回顾:读写分离很难吗?SpringBoot结合aop简单就实现了!

     

   正文   

分手厨房(Over Cooked!)是一款以高难度合作著称的游戏,在形形色色的厨房中,你需要和你的同伴一起克服重重难关,按照指定的顺序生产出美味佳肴,满足客人的味蕾。在游戏过程中,制作一道菜需要完成许多的步骤,以第一关中的寿司为例,需要蒸米饭、切鱼片、切黄瓜、然后用紫菜把他们包在一起,与此同时你还要兼顾洗掉脏盘子。不难看出,当有多个玩家参战的时候,这里有些工序是可以同时进行的(比如蒸米饭和切鱼片),但也有些工序是有顺序依赖的(比如只有一个案板,那么切鱼片和切黄瓜就不可能同时进行),那么,如何才能将所有的工序进行一个合理的排序,来保证其正常运作呢?

其实这个问题,正是一个典型的拓扑排序问题,要讲拓扑排序,我们还得先从一种基本的数据结构:**图(Graph)**说起。

图是一种由节点和边组成的数据结构,你可以简单地联想平常使用的思维导图,这就是一种非常典型的图结构。图中的边可以是有方向的,也可以是没有方向的,这两种图分别称为有向图和无向图(注意,并不是所有节点都必须连接在一起):

接下来我们需要看看如何使用图的结构来描述上面制作寿司的工序,因为不同的工序在“顺序”上有依赖,所以需要采用有向图的结构来描述:

如图,我们把游戏中制作寿司的过程用有向图的方式来描述,分别将五个步骤标记为A,B,C,D,E,这便是图的五个节点,除此之外,由于各个步骤之间存在着互相依赖,因此还需要添加四条边(A -> D),(B -> D),(C -> D),(B -> C)。

在此基础上我们需要引入一个额外概念,那就是节点的入度和出度,入度是“指向某个节点的边的数量”,出度则是“从某个节点出发的边的数量”,在上面的图中,各个节点入度和出度的情况如下图所示:

很明显,要制作一个寿司我们需要完成上面的所有5个步骤,但各个步骤实际执行的顺序很重要,比如按照A,B,C,D,E的顺序就可以顺利制作一个寿司,但是按照D,C,B,A,E的顺序就不行,因为执行包紫菜这个步骤的时候,米饭、鱼片、黄瓜都还没有准备好,就无法继续下去了。

那么,如何对这些节点进行合理的排序,得到一个可以执行的序列,这就是图论中的拓扑排序问题,用更加抽象一点的语言来描述,就是要求得一个线性序列,使得该序列中的任意两个节点u,v,如果存在边(u -> v),保证u的顺序在v之前。

关于拓扑排序有两个显而易见的结论:

  • 拓扑排序的结果不是唯一的

  • 如果要排序的有向图中存在环,那么拓扑排序是得不到结果的,所以拓扑排序只能针对有向无环图

接下来看一看如何对一张图进行拓扑排序得到线性序列S吧:

第一步:从图中找到一个入度为0的节点,将其加入序列S

第二步:从图中删除该节点,以及从该节点出发的边,当边被删除后,同步图中所有节点的入度

不断地重复第一步和第二步,直到图中所有的节点都被删除,最终得到的序列就是这张图的一个拓扑排序了。

这个过程其实也非常的容易理解,仍然以寿司的制作为例,来看看整个拓扑排序是如何进行的:

首先选中一个入度为0的节点A,然后删除节点A。此时D的入度更新为2

选中入度为0的节点B,然后删除节点B。此时D的入度更新为1,C的入度更新为0

选中入度为0的节点C,然后删除节点C。此时D的入度更新为0

选中入度为0的节点D,然后删除节点D。

选中入度为0的节点E,然后删除节点E。

得到一个拓扑排序结果(A,B,C,D,E)


Java代码实现

顶点的结构定义

public class Vertex<T> {/*** 节点值*/private T value;/*** 节点入度*/private int inDegree;/*** 储存从该定点出发的边*/private List<Edge<T>> edges;
}

边的定义

public class Edge<T> {/*** 终点边*/private Vertex<T> endVertex;/*** 权重*/private int cost;
}

图的定义

public class DirectedGraph<T> {private List<Vertex<T>> vertexList;private List<Edge<T>> edgeList;
}


拓扑排序实现

/*** 拓扑排序*/
public List<T> topologySort() throws Exception {int cnt = 0;List<T> sortedList = new ArrayList<>();Queue<Vertex<T>> queue = new LinkedList<>();// 将所有入度为0的节点入队for (Vertex<T> vertex: vertexList) {if (vertex.getInDegree() == 0) {queue.offer(vertex);}}// 如果没有入度为0的节点,说明出现循环依赖if (queue.isEmpty()) {throw new Exception("detected circle, no zero indegree node.");}while (!queue.isEmpty()) {Vertex<T> v = queue.poll();// 排序sortedList.add(v.getValue());cnt++;for (Edge<T> edge: v.getEdges()) {// 更新所有关联顶点的入度Vertex<T> endVertex = edge.getEndVertex();if (endVertex != null) {endVertex.setInDegree(endVertex.getInDegree() - 1);if (endVertex.getInDegree() == 0) {queue.offer(endVertex);}}}}if (cnt != vertexList.size()) {// 如果拓扑排序结束后数量不匹配,说明有环throw new Exception("detected circle!");}return sortedList;
}

欢迎在留言区留下你的观点,一起讨论提高。如果今天的文章让你有新的启发,学习能力的提升上有新的认识,欢迎转发分享给更多人。

欢迎各位读者加入订阅号程序员小乐技术群,在后台回复“加群”或者“学习”即可。

猜你还想看

阿里、腾讯、百度、华为、京东最新面试题汇集

解决Kubernetes Pod故障的5个简单技巧

这张「二维码」火到了GitHub热榜第一:扫一扫,打破系统边界,文件秒传

什么才是真正的架构设计?

关注订阅号「程序员小乐」,收看更多精彩内容

嘿,你在看吗


http://www.ppmy.cn/news/463966.html

相关文章

分手厨房2联机得买两份吗_你在厨房里表现出色吗?

分手厨房2联机得买两份吗 These days, I dont have to cook too often, but company is coming tonight. So, I dug out a slow cooker recipe, and got ready to brown the meat. 这些天&#xff0c;我不必经常做饭&#xff0c;但是公司今晚就要来了。 因此&#xff0c;我挖出…

掌握Spring Cloud:打造高效可靠的微服务生态系统

1、SpringCloud概述 Spring Cloud是一个用于构建分布式系统的开源框架&#xff0c;它提供了一系列的组件和工具&#xff0c;用于实现微服务架构中的各项核心功能。本文将重点介绍Spring Cloud中的关键组件&#xff0c;并详细探讨它们的功能和作用。 网关&#xff1a;Zuul/Gat…

如何利用数据化营销助力新零售企业发展?”

​“新零售”这个概念诞生至今已有5年&#xff0c;但对于其具体的定义&#xff0c;行业内仍然有许多争议。有人认为“新零售”是对传统零售模式的颠覆&#xff1b;也有人认为“新零售”就是将线上和线下相结合。不论如何&#xff0c;在这个不断变化的行业中&#xff0c;新零售企…

各品牌服务器的默认带外BMC管理地址

连接网段到sugon服务器的带外BMC管理端&#xff0c;在本地网络的属性中&#xff0c;选择ipv4更改使用固定IP地址10.0.0.5和默认的10.0.0.10为同一个网段&#xff0c; 然后在浏览器输入默认的地址:10.0.0.10 sugon TC6600 默认的带外管理地址 10.0.0.10 帐号&#xff1a;adm…

服务器Kvm加载文件,通过kvm安装操作系统?KVM如何加载ISO文件安装操作系统?

本帖最后由 米拿现’ 于 2012-12-5 14:14 编辑 如何通过kvm安装操作系统&#xff1f;Lantronix的kvm如何安装系统&#xff1f;KVM如何加载ISO文件安装操作系统&#xff1f; 1.首先&#xff0c;我们需要登录kvm并链接上服务器(参考教材&#xff1a;KVM如何使用)。 2. 然后点击op…

服务器在线迁移,服务器又进行了迁移

上个月将博客从上海机房迁移到深圳机房&#xff0c;感觉不是很好&#xff0c;因此我一直在寻找较好的主机供应商&#xff0c;而现在终于可以将博客迁移到另外一个机房了。 我在深圳的服务器用的是P4 3.0E的CPU&#xff0c;这台服务器的使用已经接近瓶颈&#xff0c;随便重建一下…

服务器重装系统步骤,服务器操作系统怎么安装(服务器装系统教程)

HP服务器的操作系统安装方法&#xff1a; 1。首先开机&#xff0c;看到下面的界面&#xff0c;按F10&#xff0c;然后E68A 进入开机操作界面。 2.单击配置和安装。 3.单击右下角的箭头&#xff0c;直接进入下一步。 4.选择自定义安装&#xff0c;然后单击右下角的下一步。 5.默…

速卖通、阿里国际、Lazada、Shopee测评自养号,卖家该怎么让店铺产品排名靠前?

运营店铺的卖家都希望自己的店铺产品排名可以靠前&#xff0c;这样店铺就会有更多流量&#xff0c;从而有更多销量。那么卖家该怎么让店铺产品排名靠前&#xff1f; 1、关键词。消费者想在速卖通上买产品的话&#xff0c;能看到的第一个就是新产品和买家之间的匹配程度。越匹配…