算法相关，有依赖关系的日程顺序安排问题

[Raven316]

有 n 个日程，互相可能有先后依赖关系，例如 A 必须在 B 之前执行，依赖关系可以用 N*N 的 01 矩阵表示。

求：给出要执行的日程，ABCD 等等，返回一个合法的执行顺序。

感觉应该是非常基础的问题，无奈还是不会。。

我现在想的方法是类似穷举：
依次取任意一个没有任何依赖的日程，执行日程 A 后，把只依赖日程 A 的日程设为无依赖；依次深度优先搜索，无合法日程顺序就搜索另一个叶子。。。

有没有更好的方法

[imn1]

字段都没有给出没法回答

原则是同一时间、同一空间、同一人，无法做两件事
但这个顶多只是排序，并不能确定依赖关系，依赖关系必须有字段说明

[Raven316]

@imn1 啥字段，没懂啊

[leishi1313]

topological sort

[favourstreet]

楼主如果不需要优化的算法一个栈就搞定了，这肯定是最简单的。计算带括号有各种优先级的表达式不就是楼主说的 n 个日程，有依赖关系（括号外依赖括号内的结果）这种问题吗。

[Raven316]

@favourstreet 好像不是吧，感觉楼上说的 topological sort 就是我想要的答案了

[snowfuck]

我感觉也像有向无环图拓扑排序

[Raven316]

@snowfuck 就是了

[imn1]

@Raven316 #2
16:00 - 17:00 总结会议
17:00 打卡下班
17:00 - 18:00 买菜
-----------
这些日程不是同一件事，是没有依赖关系的，所以肯定需要一个字段表明是有关联的同一件事
这个字段的表述方式就决定了算法，如果是父子级（或前置项）表述，自然就是拓扑等方法；
如果是 path 方式表述，如：
庆生宴 /买菜
庆生宴 /准备 /食材清洗
庆生宴 /准备 /食材预处理
庆生宴 /准备 /调料准备
庆生宴 /做菜
……
有 xpath selector 等方法，当然日程不会写这么细，只是举个例子

[mikulch]

斧王头像最近又出现了，似乎之前消失了一段时间啊。

[linvon]

拓扑排序，每次清掉入度为零的节点就 OK 了

[xupefei]

标准的 topological sort 问题。

昨天还有一群人说刷 leetcode 没用，这不就用到了吗？

[Raven316]

@imn1 啊。。还是没看懂，可能我表达的不好吧

@mikulch 作为人人讨厌的喷子低调了一段时间

[Raven316]

@xupefei 对啊，就是工作中用到了。。

[imn1]

@Raven316 #12
想了想，应该是你所说的“日程”和我理解不一样
你所说的应该是类似项目管理的 item，项目管理自然就是同一件事
我理解的是日历管理的日程（事件 /任务），这个就方方面面，事情多了去，完全不能确定是关联事件

[Raven316]

@imn1 我随便起了个名字，不知道起啥名字好

[yukong]

看看 拓扑排序

[yukong]

dfs bfs 都可以 构造好临接链表去描述有向图 构造一个入度 map 首先找到入度为 0 的节点 通过 bfs 或 dfs 遍历其连接节点 并且更新节点的入度即可