从分手厨房看拓扑排序（分手厨房单机版）

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

每天凌晨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); } } } }