(C卷,200分)- 启动多任务排序（Java & JS & Python & C）

题目描述

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

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

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

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

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

输入描述

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

A->B：表示A依赖B

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

输出描述

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

用例

题目解析

本题是拓扑排序问题，本题解析可以参考下面博客：

本题没有说明循环依赖的情况该如何处理，因此我认为本题没有循环依赖的情况。实际考试需要注意下。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const relations = (await readline()).split(" ").map((s) => s.split("->"));

  const inDegree = {};
  const next = {};

  // a依赖b, 即b执行完，才能执行a
  for (let [a, b] of relations) {
    // b的入度不变
    inDegree[b] = inDegree[b] ?? 0;
    // a的入度+1
    inDegree[a] = (inDegree[a] ?? 0) + 1;

    // b的后继节点集合添加a
    if (next[b] == undefined) next[b] = [];
    next[b].push(a);

    // a的后继节点集合不变
    if (next[a] == undefined) next[a] = [];
  }

  // queue收集第一层入度为0的点
  let queue = [];
  for (let task in inDegree) {
    if (inDegree[task] == 0) {
      queue.push(task);
    }
  }

  // 记录任务执行的顺序
  const ans = [];

  while (queue.length > 0) {
    // 如果同时有多个任务要执行，则根据任务名称字母顺序排序
    queue.sort();

    // newQueue用于记录下一层入度为0的点
    const newQueue = [];
    for (let fa of queue) {
      // fa执行，则加入已完成的任务列表
      ans.push(fa);

      for (let ch of next[fa]) {
        // fa是父任务，ch是子任务, 即fa执行完，才能执行ch
        // fa执行完，则对应ch的入度-1
        inDegree[ch] -= 1;

        // 如果ch的入度变为0，则加入新一层入度0的点集
        if (inDegree[ch] == 0) {
          newQueue.push(ch);
        }
      }
    }

    queue = newQueue;
  }

  console.log(ans.join(" "));
})();

Java算法源码

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    String[][] relations =
        Arrays.stream(sc.nextLine().split(" ")).map(s -> s.split("->")).toArray(String[][]::new);

    HashMap<String, Integer> inDegree = new HashMap<>();
    HashMap<String, ArrayList<String>> next = new HashMap<>();

    for (String[] relation : relations) {
      // a依赖b, 即b执行完，才能执行a
      String a = relation[0];
      String b = relation[1];

      // b的入度不变
      inDegree.put(b, inDegree.getOrDefault(b, 0));
      // a的入度+1
      inDegree.put(a, inDegree.getOrDefault(a, 0) + 1);

      // b的后继节点集合添加a
      next.putIfAbsent(b, new ArrayList<>());
      next.get(b).add(a);
      // a的后继节点集合不变
      next.putIfAbsent(a, new ArrayList<>());
    }

    // queue收集第一层入度为0的点
    ArrayList<String> queue = new ArrayList<>();
    for (String task : inDegree.keySet()) {
      if (inDegree.get(task) == 0) {
        queue.add(task);
      }
    }

    // 记录任务执行的顺序
    StringJoiner ans = new StringJoiner(" ");

    while (queue.size() > 0) {
      // 如果同时有多个任务要执行，则根据任务名称字母顺序排序
      queue.sort(String::compareTo);

      // newQueue用于记录下一层入度为0的点
      ArrayList<String> newQueue = new ArrayList<>();

      for (String fa : queue) {
        // fa执行，则加入已完成的任务列表
        ans.add(fa);

        for (String ch : next.get(fa)) {
          // fa是父任务，ch是子任务, 即fa执行完，才能执行ch
          // fa执行完，则对应ch的入度-1
          inDegree.put(ch, inDegree.get(ch) - 1);

          // 如果ch的入度变为0，则加入新一层入度0的点集
          if (inDegree.get(ch) == 0) {
            newQueue.add(ch);
          }
        }
      }

      queue = newQueue;
    }

    System.out.println(ans);
  }
}

Python算法源码

# 输入获取
relations = list(map(lambda s: s.split("->"), input().split()))


# 算法入口
def getResult():
    inDegree = {}
    next = {}

    # a依赖b, 即b执行完，才能执行a
    for a, b in relations:
        # b的入度不变
        inDegree[b] = inDegree.get(b, 0)
        # a的入度+1
        inDegree[a] = inDegree.get(a, 0) + 1

        # b的后继节点集合添加a
        next[b] = next.get(b, [])
        next[b].append(a)

        # a的后继节点集合不变
        next[a] = next.get(a, [])

    # queue收集第一层入度为0的点
    queue = []
    for task in inDegree:
        if inDegree[task] == 0:
            queue.append(task)

    # 记录任务执行的顺序
    ans = []

    while len(queue) > 0:
        # 如果同时有多个任务要执行，则根据任务名称字母顺序排序
        queue.sort()

        # newQueue用于记录下一层入度为0的点
        newQueue = []
        for fa in queue:
            # fa执行，则加入已完成的任务列表
            ans.append(fa)

            for ch in next[fa]:
                # fa是父任务，ch是子任务, 即fa执行完，才能执行ch
                # fa执行完，则对应ch的入度-1
                inDegree[ch] -= 1

                # 如果ch的入度变为0，则加入新一层入度0的点集
                if inDegree[ch] == 0:
                    newQueue.append(ch)

        queue = newQueue

    return " ".join(ans)


# 算法调用
print(getResult())

C算法源码

 本题没有说明任务名的长度，可能不是单个字母，因此C语言下面代码写的有点复杂

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

#define MAX_TASK_SIZE 50000
#define MAX_TASK_NAME_LEN 10

typedef struct ListNode {
    int ele;
    struct ListNode *prev;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

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

    link->size++;
}

// 缓存输入
char s[MAX_TASK_SIZE * MAX_TASK_NAME_LEN];

// 任务名数组，task[i]记录的是任务名，方便后续将任务名映射为索引i
char tasks[MAX_TASK_SIZE][MAX_TASK_NAME_LEN];
int tasks_size = 0;

// 记录每个任务的入度，inDegree[i] 表示任务i的入度
int inDegree[MAX_TASK_SIZE] = {0};
// 记录每个任务的子任务，next[i] 表示任务i的子任务集合
LinkedList *next[MAX_TASK_SIZE];

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]);
}

int main() {
    gets(s);

    char *token = strtok(s, " ");
    while (token != NULL) {
        char *tmp = strstr(token, "->");
        tmp[0] = '';
        tmp[1] = '';

        // a依赖b, 即b执行完，才能执行a
        // a任务
        char *a = token;
        // b任务
        char *b = tmp + 2;

        // a任务的索引号
        int a_index = -1;
        // b任务的索引号
        int b_index = -1;

        for (int i = 0; i < tasks_size; i++) {
            if (strcmp(tasks[i], a) == 0) {
                a_index = i;
            }

            if (strcmp(tasks[i], b) == 0) {
                b_index = i;
            }
        }

        if (a_index == -1) {
            a_index = tasks_size;
            strcpy(tasks[tasks_size++], a);
        }

        if (b_index == -1) {
            b_index = tasks_size;
            strcpy(tasks[tasks_size++], b);
        }

        // b的入度不变
        // a的入度+1
        inDegree[a_index]++;

        // b的后继节点集合添加a
        if (next[b_index] == NULL) {
            next[b_index] = new_LinkedList();
        }
        addLast_LinkedList(next[b_index], a_index);

        token = strtok(NULL, " ");
    }

    // queue收集第一层入度为0的点
    int* queue = (int*) malloc(sizeof(int) * tasks_size);
    int queue_size = 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);

        // newQueue用于记录下一层入度为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];

            // fa执行完成，则打印
            printf("%s ", tasks[fa]);

            if(next[fa] != NULL) {
                ListNode* cur = next[fa]->head;
                while (cur != NULL) {
                    // fa是父任务，ch是子任务, 即fa执行完，才能执行ch
                    // fa执行完，则对应ch的入度-1
                    int ch = cur->ele;

                    inDegree[ch] -= 1;

                    // 如果ch的入度变为0，则加入新一层入度0的点集
                    if(inDegree[ch] == 0) {
                        newQueue[newQueue_size++] = ch;
                    }

                    cur = cur->next;
                }
            }
        }

        queue = newQueue;
        queue_size = newQueue_size;
    }

    return 0;
}