这是一个创建于 1682 天前的主题，其中的信息可能已经有所发展或是发生改变。
有 n 个日程，互相可能有先后依赖关系，例如 A 必须在 B 之前执行，依赖关系可以用 N*N 的 01 矩阵表示。
求：给出要执行的日程，ABCD 等等，返回一个合法的执行顺序。
感觉应该是非常基础的问题，无奈还是不会。。
我现在想的方法是类似穷举：
依次取任意一个没有任何依赖的日程，执行日程 A 后，把只依赖日程 A 的日程设为无依赖；依次深度优先搜索，无合法日程顺序就搜索另一个叶子。。。
有没有更好的方法
求：给出要执行的日程，ABCD 等等，返回一个合法的执行顺序。
感觉应该是非常基础的问题，无奈还是不会。。
我现在想的方法是类似穷举：
依次取任意一个没有任何依赖的日程，执行日程 A 后，把只依赖日程 A 的日程设为无依赖；依次深度优先搜索，无合法日程顺序就搜索另一个叶子。。。
有没有更好的方法
 |
1
imn1 2020-04-24 14:40:24 +08:00
字段都没有给出没法回答
原则是同一时间、同一空间、同一人，无法做两件事 但这个顶多只是排序，并不能确定依赖关系，依赖关系必须有字段说明 |
 |
3
leishi1313 2020-04-24 14:56:02 +08:00 via Android  1
topological sort
|
 |
4
favourstreet 2020-04-24 15:04:22 +08:00
楼主如果不需要优化的算法一个栈就搞定了，这肯定是最简单的。计算带括号有各种优先级的表达式不就是楼主说的 n 个日程，有依赖关系（括号外依赖括号内的结果）这种问题吗。
|
 |
5
Raven316 OP @favourstreet 好像不是吧，感觉楼上说的 topological sort 就是我想要的答案了
|
 |
6
snowfuck 2020-04-24 15:26:15 +08:00
我感觉也像有向无环图拓扑排序
|
|
8
imn1 2020-04-24 15:42:13 +08:00
@Raven316 #2
16:00 - 17:00 总结会议 17:00 打卡下班 17:00 - 18:00 买菜 ----------- 这些日程不是同一件事，是没有依赖关系的，所以肯定需要一个字段表明是有关联的同一件事 这个字段的表述方式就决定了算法，如果是父子级（或前置项）表述，自然就是拓扑等方法； 如果是 path 方式表述，如： 庆生宴 /买菜 庆生宴 /准备 /食材清洗 庆生宴 /准备 /食材预处理 庆生宴 /准备 /调料准备 庆生宴 /做菜 …… 有 xpath selector 等方法，当然日程不会写这么细，只是举个例子 |
 |
9
mikulch 2020-04-24 15:44:55 +08:00
斧王头像最近又出现了，似乎之前消失了一段时间啊。
|
 |
10
linvon 2020-04-24 15:52:56 +08:00
拓扑排序，每次清掉入度为零的节点就 OK 了
|
 |
11
xupefei 2020-04-24 15:54:27 +08:00 via iPhone
标准的 topological sort 问题。
昨天还有一群人说刷 leetcode 没用，这不就用到了吗？ |
|
14
imn1 2020-04-24 16:05:35 +08:00
@Raven316 #12
想了想，应该是你所说的“日程”和我理解不一样 你所说的应该是类似项目管理的 item，项目管理自然就是同一件事 我理解的是日历管理的日程（事件 /任务），这个就方方面面，事情多了去，完全不能确定是关联事件 |
 |
16
yukong 2020-04-24 16:18:12 +08:00
看看 拓扑排序
|
|
17
yukong 2020-04-24 16:20:08 +08:00
dfs bfs 都可以 构造好临接链表去描述有向图 构造一个入度 map 首先找到入度为 0 的节点 通过 bfs 或 dfs 遍历其连接节点 并且更新节点的入度即可
|
Select Language