返回目录

题目描述

一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。

现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。

例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：

A任务，E任务，B任务，C任务，D任务

这里A和E任务都是没有依赖的，立即执行。

输入描述

输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号"->"表示依赖方向，例如：

A->B：表示A依赖B

多个依赖之间用单个空格分隔

输出描述

输出排序后的启动任务列表，多个任务之间用单个空格分隔

示例：

解题思路

1. 构建图的邻接表和计算每个任务的入度。邻接表 graph用于表示任务间的依赖关系，而入度表 inDegree用于记录每个任务依赖的任务数量。
2. 遍历输入的依赖关系，更新邻接表和入度表。对于每个依赖 A->B，将 B添加到 A的邻接列表中，并将 B的入度加1。同时，确保每个任务至少在入度表中出现一次，如果任务没有依赖，则其入度为0。
3. 使用一个队列（或列表）来收集入度为0的任务，即可以立即执行的任务。
4. 按照字母顺序执行入度为0的任务，并在执行过程中更新其它任务的入度。对于每个执行的任务，检查它的所有后继任务，将每个后继任务的入度减1。如果后继任务的入度减为0，则将其加入到下一轮执行的队列中。
5. 重复步骤4，直到没有任务可以执行。

用例 A->B C->B模拟计算过程：

• 输入：A->B C->B
• 分割输入，得到依赖关系：A依赖于 B，C依赖于 B。

• 构建邻接表和入度表：

  • 邻接表：B -> [A, C]（B完成后，可以执行 A和 C）
  • 入度表：A: 1, C: 1, B: 0（A和 C各有1个依赖，B没有依赖）
• 由于 B的入度为0，它可以立即执行。执行 B，更新队列。
• 执行 B后，更新 A和 C的入度，它们的入度都变为0，可以执行。将 A和 C加入执行队列。
• 根据字母顺序，先执行 A，然后执行 C。
• 最终输出的执行顺序为：B A C。

Python算法源码

def find_order(dependencies):
    # 存储图的邻接表表示，键是任务，值是依赖于键的任务列表
    graph = {}
    # 存储每个任务的入度（依赖于它的其他任务的数量）
    in_degree = {}
  
    # 构建图和计算入度
    for dep in dependencies:
        parts = dep.split("->")
        from_task, to_task = parts[1], parts[0]  # 注意：这里与通常的表示相反，表示to依赖于from
        graph.setdefault(from_task, []).append(to_task)
        in_degree[to_task] = in_degree.get(to_task, 0) + 1
        in_degree.setdefault(from_task, 0)

    # 收集入度为0的任务，即可以立即执行的任务
    queue = [task for task, degree in in_degree.items() if degree == 0]

    # 存储任务执行顺序
    order = []

    while queue:
        # 准备新队列，用于存储下一轮入度变为0的任务
        new_queue = []

        for current in queue:
            # 添加当前任务到执行顺序中
            order.append(current)
            # 遍历当前任务的所有后继任务
            for next_task in graph.get(current, []):
                # 减少后继任务的入度
                in_degree[next_task] -= 1
                # 如果后继任务的入度为0，则添加到新队列中
                if in_degree[next_task] == 0:
                    new_queue.append(next_task)

        # 更新队列为新队列，并对其排序以保证字母顺序
        queue = sorted(new_queue)

    # 返回构建的任务执行顺序字符串
    return " ".join(order)

if __name__ == "__main__":
    dependencies = input().split()  # 读取一行输入并根据空格分割字符串
    print(find_order(dependencies))

C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_TASK_SIZE 50000
#define MAX_TASK_NAME_LEN 10

// 定义一个宏，用于表示任务数组的最大行数
#define MAX_TASK_X 50000
// 定义一个宏，用于表示任务名称的最大长度
#define MAX_TASK_Y_LEN 10

// 定义任务节点结构体
typedef struct TaskNode {
    int ele;                // 任务索引
    struct TaskNode *prev;  // 前一个任务节点指针
    struct TaskNode *next;  // 后一个任务节点指针
} TaskNode;

// 定义任务链表结构体
typedef struct TaskList {
    int size;               // 链表大小
    TaskNode *head;         // 链表头指针
    TaskNode *tail;         // 链表尾指针
} TaskList;

// 创建一个新的任务链表
TaskList *new_TaskList();
// 向任务链表尾部添加一个任务节点
void addLast_TaskList(TaskList *list, int ele);
// 处理输入的任务字符串
void processTasks(char *input);

// 创建一个新的任务链表
TaskList *new_TaskList() {
    TaskList *list = (TaskList *) malloc(sizeof(TaskList));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// 向任务链表尾部添加一个任务节点
void addLast_TaskList(TaskList *list, int ele) {
    TaskNode *node = (TaskNode *) malloc(sizeof(TaskNode));
    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

    if (list->size == 0) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        node->prev = list->tail;
        list->tail = node;
    }

    list->size++;
}

// 定义全局变量

// 用于存储输入的任务字符串
char t[MAX_TASK_X * MAX_TASK_Y_LEN];
// 用于存储任务名称的二维数组
char tasks[MAX_TASK_X][MAX_TASK_Y_LEN];
// 任务数量
int tasks_size = 0;
// 用于存储每个任务的入度
int inDegree[MAX_TASK_X] = {0};
// 用于存储每个任务的后继任务链表
TaskList *next[MAX_TASK_X];

// 用于比较两个任务名称的函数
int cmp(const void *a, const void *b) {
    int a_index = *((int *) a);
    int b_index = *((int *) b);
    return strcmp(tasks[a_index], tasks[b_index]);
}

// 处理输入的任务字符串
void processTasks(char *input) {
    char *token = strtok(input, " ");
    while (token != NULL) {
        char *tmp = strstr(token, "->");
        tmp[0] = '\0';      // 将'-'替换为'\0'
        tmp[1] = '\0';      // 将'>'替换为'\0'

        char *x = token;    // 任务 x
        char *y = tmp + 2;  // 任务 y

        int x_index = -1;   // 任务 x 的索引
        int y_index = -1;   // 任务 y 的索引

        // 遍历已有的任务数组，查找任务 x 和任务 y 是否已存在
        for (int i = 0; i < tasks_size; i++) {
            if (strcmp(tasks[i], x) == 0) {
                x_index = i;
            }

            if (strcmp(tasks[i], y) == 0) {
                y_index = i;
            }
        }

        // 若任务 x 不存在，则添加任务 x
        if (x_index == -1) {
            x_index = tasks_size;
            strcpy(tasks[tasks_size++], x);
        }

        // 若任务 y 不存在，则添加任务 y
        if (y_index == -1) {
            y_index = tasks_size;
            strcpy(tasks[tasks_size++], y);
        }

        // 增加任务 y 的入度
        inDegree[x_index]++;
        // 若任务 y 的后继任务链表为空，则创建一个新的链表
        if (next[y_index] == NULL) {
            next[y_index] = new_TaskList();
        }
        // 向任务 y 的后继任务链表中添加任务 x 的索引
        addLast_TaskList(next[y_index], x_index);

        token = strtok(NULL, " ");
    }
}

int main() {
    gets(t);    // 获取输入的任务字符串
    processTasks(t);    // 处理任务字符串

    // 创建一个队列，用于存储入度为 0 的任务索引
    int* queue = (int*) malloc(sizeof(int) * tasks_size);
    int queue_size = 0;

    // 将入度为 0 的任务索引加入队列中
    for (int i = 0; i < tasks_size; i++) {
        if (inDegree[i] == 0) {
            queue[queue_size++] = i;
        }
    }

    // 遍历队列中的任务索引，进行拓扑排序
    while (queue_size > 0) {
        // 按字典序对队列中的任务索引排序
        qsort(queue, queue_size, sizeof(queue[0]), cmp);

        // 创建一个新的队列，用于存储下一轮入度为 0 的任务索引
        int* newQueue = (int*) malloc(sizeof(int) * tasks_size);
        int newQueue_size = 0;

        // 遍历当前队列中的任务索引
        for (int i = 0; i < queue_size; i++) {
            int fa = queue[i];  // 当前任务索引

            // 输出当前任务名称
            printf("%s ", tasks[fa]);

            // 若当前任务存在后继任务
            if(next[fa] != NULL) {
                TaskNode* cur = next[fa]->head;
                // 遍历当前任务的后继任务链表
                while (cur != NULL) {
                    int ch = cur->ele;  // 后继任务索引

                    // 减少后继任务的入度
                    inDegree[ch] -= 1;

                    // 若后继任务的入度为 0，则加入新的队列中
                    if(inDegree[ch] == 0) {
                        newQueue[newQueue_size++] = ch;
                    }

                    cur = cur

Java算法源码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] dependencies = input.split("\\s+");
        System.out.println(findOrder(dependencies));
        scanner.close();
    }

    public static String findOrder(String[] dependencies) {
        Map<String, List<String>> graph = new HashMap<>();
        Map<String, Integer> inDegree = new HashMap<>();

        for (String dep : dependencies) {
            String[] parts = dep.split("->");
            String from = parts[1], to = parts[0];

            graph.putIfAbsent(from, new ArrayList<>());
            graph.get(from).add(to);

            inDegree.put(to, inDegree.getOrDefault(to, 0) + 1);
            inDegree.putIfAbsent(from, 0);
        }

        List<String> queue = new ArrayList<>();
        for (String task : inDegree.keySet()) {
            if (inDegree.get(task) == 0) {
                queue.add(task);
            }
        }

        List<String> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            Collections.sort(queue);

            List<String> newQueue = new ArrayList<>();
            for (String current : queue) {
                order.add(current);

                List<String> successors = graph.getOrDefault(current, new ArrayList<>());
                for (String next : successors) {
                    inDegree.put(next, inDegree.get(next) - 1);
                    if (inDegree.get(next) == 0) {
                        newQueue.add(next);
                    }
                }
            }
            queue = newQueue;
        }

        StringBuilder result = new StringBuilder();
        for (String task : order) {
            result.append(task).append(" ");
        }
        return result.toString();
    }
}