### 华为OD机试C卷 - 启动多任务排序题目详解
#### 题目背景
在软件开发过程中，特别是在系统启动阶段，经常会出现多个任务需要按一定顺序执行的情况，这些任务之间可能存在着相互依赖的关系。如何合理地安排这些任务的执行顺序，使其既能满足依赖关系的要求又能高效地执行，就成为了需要解决的问题之一。
#### 题目描述
假设在一个应用启动的过程中，有多个初始化任务需要执行，并且这些任务之间存在一定的依赖关系。例如，任务A依赖于任务B，那么必须在任务B执行完成后，才能开始执行任务A。本题的目标是在给定多个任务及其依赖关系的情况下，输出一个符合贪婪策略的任务执行序列。这里的贪婪策略指的是：当一个任务没有任何依赖时，可以立即执行；如果有多个无依赖任务，则按照任务名称的字母顺序执行。
#### 输入描述
输入包括一系列任务之间的依赖关系，每对依赖关系用 "任务名称 -> 任务名称" 的格式表示，多个依赖关系之间用空格分隔。例如，输入 `"A -> B C -> A D -> B C E"` 表示任务A依赖任务B，任务C依赖任务A，任务D依赖任务B和任务C，以及任务D还依赖任务E。
#### 输出描述
输出符合题目要求的排序后的任务列表，任务名称之间用空格分隔。
#### 题目解析
本题需要设计一个算法来根据输入的任务依赖关系找到一个合理的执行顺序。具体而言，可以使用图论中的拓扑排序算法来解决这个问题。拓扑排序是一种针对有向无环图（DAG）的排序方法，可以将图中的顶点排成一个线性序列，使得图中每条有向边的起点都比终点靠前。在本题中，可以将每个任务视为图中的一个顶点，将依赖关系视为图中的有向边。
为了实现这个算法，我们可以采用以下步骤：
1. **构建图**：根据输入的任务依赖关系，构建一个有向图。
2. **寻找入度为0的顶点**：遍历所有顶点，找出所有入度为0的顶点（即没有其他顶点指向该顶点的顶点）。
3. **进行排序**：将入度为0的顶点添加到结果列表中，并从图中移除该顶点及其出边。重复此过程，直到图为空或无法找到新的入度为0的顶点。
4. **检查是否有环**：如果最终图不为空，则说明存在环，无法完成拓扑排序。
接下来，我们将分别用Java、JavaScript、Python和C语言来实现上述算法。
#### Java实现
```java
import java.util.*;
class TaskNode {
char task;
List<Character> dependencies = new ArrayList<>();
TaskNode(char task) {
this.task = task;
}
}
public class Main {
public static void main(String[] args) {
String input = "A->B C->A D->B C E";
System.out.println(resolveTaskOrder(input));
}
public static String resolveTaskOrder(String input) {
Map<Character, TaskNode> graph = new HashMap<>();
String[] dependencies = input.split(" ");
for (String dep : dependencies) {
char from = dep.charAt(0);
char to = dep.charAt(3);
if (!graph.containsKey(from)) graph.put(from, new TaskNode(from));
if (!graph.containsKey(to)) graph.put(to, new TaskNode(to));
graph.get(to).dependencies.add(from);
}
Queue<Character> queue = new LinkedList<>();
graph.forEach((k, v) -> {
if (v.dependencies.isEmpty()) queue.offer(k);
});
StringBuilder order = new StringBuilder();
while (!queue.isEmpty()) {
Character current = queue.poll();
order.append(current);
graph.values().stream()
.filter(node -> node.dependencies.remove((Character) current))
.filter(node -> node.dependencies.isEmpty())
.forEach(node -> queue.offer(node.task));
if (queue.size() > 0) order.append(" ");
}
return order.toString();
}
}
```
#### JavaScript实现
```javascript
function resolveTaskOrder(input) {
const graph = {};
const dependencies = input.split(' ');
for (const dep of dependencies) {
const from = dep.charAt(0);
const to = dep.charAt(3);
if (!graph[from]) graph[from] = [];
if (!graph[to]) graph[to] = [];
graph[to].push(from);
}
const queue = [];
for (const key in graph) {
if (graph[key].length === 0) {
queue.push(key);
}
}
let order = '';
while (queue.length > 0) {
const current = queue.shift();
order += current + ' ';
for (const key in graph) {
const index = graph[key].indexOf(current);
if (index !== -1) {
graph[key].splice(index, 1);
if (graph[key].length === 0) {
queue.push(key);
}
}
}
}
return order.trim();
}
console.log(resolveTaskOrder('A->B C->A D->B C E'));
```
#### Python实现
```python
from collections import defaultdict, deque
def resolve_task_order(input_str):
dependencies = defaultdict(list)
for dep in input_str.split():
pre, post = dep.split("->")
dependencies[post.strip()].append(pre.strip())
graph = {task: set(deps) for task, deps in dependencies.items()}
no_deps = deque(task for task, deps in graph.items() if not deps)
order = []
while no_deps:
current = no_deps.popleft()
order.append(current)
for task, deps in graph.items():
if current in deps:
deps.remove(current)
if not deps:
no_deps.append(task)
return ' '.join(order)
print(resolve_task_order('A->B C->A D->B C E'))
```
#### C实现
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TaskNode {
char task;
int *dependencies;
int numDependencies;
} TaskNode;
int stringCompare(const void *a, const void *b) {
return strcmp(*(const char **)a, *(const char **)b);
}
void resolveTaskOrder(const char *input) {
int numTasks = strlen(input) / 4 + 1;
TaskNode *tasks = malloc(numTasks * sizeof(TaskNode));
int *dependencyCounts = malloc(numTasks * sizeof(int));
memset(dependencyCounts, 0, numTasks * sizeof(int));
for (int i = 0; i < numTasks; ++i) {
tasks[i].task = input[i * 4];
tasks[i].numDependencies = 0;
tasks[i].dependencies = NULL;
}
for (int i = 0; i < numTasks - 1; ++i) {
char from = input[i * 4];
char to = input[i * 4 + 3];
dependencyCounts[from - 'A']++;
if (tasks[to - 'A'].dependencies == NULL) {
tasks[to - 'A'].dependencies = malloc(sizeof(int));
tasks[to - 'A'].numDependencies = 1;
tasks[to - 'A'].dependencies[0] = from - 'A';
} else {
tasks[to - 'A'].dependencies = realloc(tasks[to - 'A'].dependencies, (tasks[to - 'A'].numDependencies + 1) * sizeof(int));
tasks[to - 'A'].dependencies[tasks[to - 'A'].numDependencies] = from - 'A';
tasks[to - 'A'].numDependencies++;
}
}
char *order = malloc(numTasks * sizeof(char));
int orderIndex = 0;
qsort(&tasks, numTasks, sizeof(TaskNode), stringCompare);
for (int i = 0; i < numTasks; ++i) {
if (dependencyCounts[i] == 0) {
order[orderIndex++] = i + 'A';
for (int j = 0; j < tasks[i].numDependencies; ++j) {
dependencyCounts[tasks[i].dependencies[j]]--;
}
}
}
free(tasks);
free(dependencyCounts);
order[orderIndex] = '\0';
printf("%s\n", order);
free(order);
}
int main() {
resolveTaskOrder("A->BC->AD->B,C,E");
return 0;
}
```
通过以上实现，我们可以看到不同的编程语言在处理这类问题时有着相似的逻辑结构，但具体的语法和细节会有所不同。这些实现都可以有效地解决题目中所提出的问题，帮助我们在实际项目中更好地组织和管理初始化任务的执行顺序。
