您的位置：首页 > 新闻 > 会展 > 任务执行拓扑排序（华为od机考题）

任务执行拓扑排序（华为od机考题）

2024/12/27 13:57:26 来源：https://blog.csdn.net/qq_57223586/article/details/141674684  浏览:  次   关键词：任务执行拓扑排序（华为od机考题）

一、题目

1.原题

一个应用启动时，会有多个初始化任务需要执行，
并且任务之间有依赖关系，
例如：A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。
现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，
规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，
如果同时有多个任务要执行，则根据任务名称字母顺序排序。
例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。
那么执行任务的顺序由先到后是：A任务，E任务，B任务，C任务，D任务。
这里A和E任务都是没有依赖的，立即执行。
 

2.题目理解

考点：[数组, 树, DFS搜索]

拓扑排序问题，通过建立任务之间的依赖关系图，然后按照一定规则执行任务，即先执行没有依赖的任务，然后再执行依赖于前面任务的任务。

二、思路与代码过程

1.思路

多任务依赖关系的规则：贪婪策略，一个任务如果没有依赖的任务，则立刻开始执行，若同时有多个任务要执行，则根据任务名称字母顺序排序；

输入：H->F,Y->H ,B->Y ,Y->M ,M->L ,L->T

输出：F T H L M Y B

对输入进行拆分，对依赖关系进行建表，使用outdegree和depend来描述依赖关系；

首先将outdegree为0的存入队列中，当队列不为空的时候，进行从队列q中移除加入已执行任务列表中Execute；

当处理完一轮之后，若上一轮产生了outdegree为0的任务则将其加入处理队列，若未产生则按照字典顺序依次处理任务；

直到没有新的可加入，队列为空，输出执行列表Excute，若Excute长度不等于任务总数则表示该系列任务存在回路，无法全部完成，若相等则执行完毕，输出执行顺序。

2.代码过程

①main函数

public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入任务依赖关系的数量：");int n = sc.nextInt();System.out.println("请输入任务之间的依赖关系：");ArrayList<String[]> task = new ArrayList<>();for (int i = 0; i < n; i++) {String[] s = sc.next().split("->");task.add(s);}Collections.sort(task, new Comparator<String[]>() {@Overridepublic int compare(String[] a, String[] b) {// 以第一个元素进行比较return a[0].compareTo(b[0]);}});Set<String> set = new TreeSet<>();for (int i = 0; i < n; i++) {set.add(task.get(i)[0]);set.add(task.get(i)[1]);}Map<String,Node> NodeTask = new HashMap<>();for (String s : set) {NodeTask.put(s,new Node(s,0,new ArrayList<>()));for (String[] t : task) {if (s.equals(t[0])) {Node node = NodeTask.get(s);node.outdegree++;//出度：->后有元素，即存在依赖node.depend.add(t[1]);//添加->后的元素，即添加依赖项//依赖者->被依赖者}}}TreeMap<String, Node> sortedNodeTask = new TreeMap<>(NodeTask);ArrayList<String> Execute = new ArrayList<>();//使用队列进行遍历Queue<String> q = new LinkedList<>();//初始化队列for (Node node : sortedNodeTask.values()) {if (node.outdegree == 0) {q.add(node.name);}}//创建函数ArrayList<String>ExecuteOrder = TaskCal(q,Execute,sortedNodeTask,set);if (Execute.size() != set.size()) {System.out.println("图中存在环路，无法完成拓扑排序。");}else {System.out.println("任务的执行顺序为：");System.out.println(Execute);}}

②TaskCal函数

private static ArrayList<String> TaskCal(Queue<String> q, ArrayList<String> execute, TreeMap<String, Node> sortedNodeTask, Set<String> set) {//先处理无依赖的点，因为无环所以必存在一个无依赖点//入队后，除依赖处理while(!q.isEmpty()){boolean newAdd = false;String current = q.poll();//移除execute.add(current);//加入已执行队列Node currentNode = sortedNodeTask.get(current);//遍历找到依赖于当前节点的任务，移除依赖for (Node node : sortedNodeTask.values()) {if(node.depend.contains(current)){node.outdegree--;node.depend.remove(current);}}for (Node node : sortedNodeTask.values()) {if (node.outdegree == 0&&!q.contains(node.name)&&!execute.contains(node.name)) {//队列检验1q.add(node.name);newAdd = true;//队列检验2}}if (!newAdd&&execute.size()<set.size()&&q.isEmpty()){ArrayList<String> tmp = new ArrayList<>(set);for (String key : execute) {tmp.remove(key);}q.add(tmp.get(0));//队列加入未处理字母中的第一个值，按照顺序慢慢处理}}return execute;}

③Node类

public static class Node {String name;int outdegree;ArrayList<String> depend;public Node(String name, int outdegree, ArrayList<String> depend) {this.name = name;this.outdegree = outdegree;this.depend = depend;}public String toString() {return "Node{" +"name='" + name + '\'' +", outdegree=" + outdegree +", depend=" + depend +'}';}}

三、运行结果

1.运行截图

2.带数据分析运行结果

请输入任务依赖关系的数量：
6
请输入任务之间的依赖关系：
H->F
Y->H
B->Y
Y->M
M->L
L->T
task:
[B, Y]
[H, F]
[L, T]
[M, L]
[Y, H]
[Y, M]
set:[B, F, H, L, M, T, Y]
sortedNodeTask:
Node{name='B', outdegree=1, depend=[Y]}
Node{name='F', outdegree=0, depend=[]}
Node{name='H', outdegree=1, depend=[F]}
Node{name='L', outdegree=1, depend=[T]}
Node{name='M', outdegree=1, depend=[L]}
Node{name='T', outdegree=0, depend=[]}
Node{name='Y', outdegree=2, depend=[H, M]}
1 element:F
1 element:T
q队列循环：
q拿出的currentNode:Node{name='F', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:F
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:F
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=1, depend=[F]}
current0:F
依赖判断0:Node{name='H', outdegree=1, depend=[F]}node.depend:[F]
---------------------------current1:F
依赖判断1:Node{name='H', outdegree=1, depend=[F]}node.depend:[F]
--------------------------依赖移除后:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=1, depend=[T]}
current0:F
依赖判断0:Node{name='L', outdegree=1, depend=[T]}node.depend:[T]
sortedNodeTask循环:Node{name='M', outdegree=1, depend=[L]}
current0:F
依赖判断0:Node{name='M', outdegree=1, depend=[L]}node.depend:[L]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:F
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=2, depend=[H, M]}
current0:F
依赖判断0:Node{name='Y', outdegree=2, depend=[H, M]}node.depend:[H, M]
2 qele:T
3 qele:T
3 qele:H
4 qele:T
4 qele:H
q队列循环：
q拿出的currentNode:Node{name='T', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:T
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:T
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:T
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=1, depend=[T]}
current0:T
依赖判断0:Node{name='L', outdegree=1, depend=[T]}node.depend:[T]
---------------------------current1:T
依赖判断1:Node{name='L', outdegree=1, depend=[T]}node.depend:[T]
--------------------------依赖移除后:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=1, depend=[L]}
current0:T
依赖判断0:Node{name='M', outdegree=1, depend=[L]}node.depend:[L]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:T
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=2, depend=[H, M]}
current0:T
依赖判断0:Node{name='Y', outdegree=2, depend=[H, M]}node.depend:[H, M]
2 qele:H
3 qele:H
3 qele:L
4 qele:H
4 qele:L
q队列循环：
q拿出的currentNode:Node{name='H', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:H
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:H
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:H
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=0, depend=[]}
current0:H
依赖判断0:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=1, depend=[L]}
current0:H
依赖判断0:Node{name='M', outdegree=1, depend=[L]}node.depend:[L]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:H
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=2, depend=[H, M]}
current0:H
依赖判断0:Node{name='Y', outdegree=2, depend=[H, M]}node.depend:[H, M]
---------------------------current1:H
依赖判断1:Node{name='Y', outdegree=2, depend=[H, M]}node.depend:[H, M]
--------------------------依赖移除后:Node{name='Y', outdegree=1, depend=[M]}node.depend:[M]
4 qele:L
q队列循环：
q拿出的currentNode:Node{name='L', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:L
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:L
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:L
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=0, depend=[]}
current0:L
依赖判断0:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=1, depend=[L]}
current0:L
依赖判断0:Node{name='M', outdegree=1, depend=[L]}node.depend:[L]
---------------------------current1:L
依赖判断1:Node{name='M', outdegree=1, depend=[L]}node.depend:[L]
--------------------------依赖移除后:Node{name='M', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:L
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=1, depend=[M]}
current0:L
依赖判断0:Node{name='Y', outdegree=1, depend=[M]}node.depend:[M]
3 qele:M
4 qele:M
q队列循环：
q拿出的currentNode:Node{name='M', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:M
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:M
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:M
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=0, depend=[]}
current0:M
依赖判断0:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=0, depend=[]}
current0:M
依赖判断0:Node{name='M', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:M
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=1, depend=[M]}
current0:M
依赖判断0:Node{name='Y', outdegree=1, depend=[M]}node.depend:[M]
---------------------------current1:M
依赖判断1:Node{name='Y', outdegree=1, depend=[M]}node.depend:[M]
--------------------------依赖移除后:Node{name='Y', outdegree=0, depend=[]}node.depend:[]
3 qele:Y
4 qele:Y
q队列循环：
q拿出的currentNode:Node{name='Y', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=1, depend=[Y]}
current0:Y
依赖判断0:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
---------------------------current1:Y
依赖判断1:Node{name='B', outdegree=1, depend=[Y]}node.depend:[Y]
--------------------------依赖移除后:Node{name='B', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='M', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=0, depend=[]}
current0:Y
依赖判断0:Node{name='Y', outdegree=0, depend=[]}node.depend:[]
3 qele:B
4 qele:B
q队列循环：
q拿出的currentNode:Node{name='B', outdegree=0, depend=[]}
sortedNodeTask循环:Node{name='B', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='B', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='F', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='F', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='H', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='H', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='L', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='L', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='M', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='M', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='T', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='T', outdegree=0, depend=[]}node.depend:[]
sortedNodeTask循环:Node{name='Y', outdegree=0, depend=[]}
current0:B
依赖判断0:Node{name='Y', outdegree=0, depend=[]}node.depend:[]
7 7
任务的执行顺序为：

[F, T, H, L, M, Y, B]

3.带数据分析完整代码

import java.util.*;public class test40 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入任务依赖关系的数量：");int n = sc.nextInt();System.out.println("请输入任务之间的依赖关系：");ArrayList<String[]> task = new ArrayList<>();for (int i = 0; i < n; i++) {String[] s = sc.next().split("->");task.add(s);}Collections.sort(task, new Comparator<String[]>() {@Overridepublic int compare(String[] a, String[] b) {// 以第一个元素进行比较return a[0].compareTo(b[0]);}});System.out.println("task:");for (String[] s : task) {System.out.println(Arrays.toString(s));}Set<String> set = new TreeSet<>();for (int i = 0; i < n; i++) {set.add(task.get(i)[0]);set.add(task.get(i)[1]);}System.out.println("set:"+set);//无意义?Map<String,Node> NodeTask = new HashMap<>();for (String s : set) {NodeTask.put(s,new Node(s,0,new ArrayList<>()));for (String[] t : task) {if (s.equals(t[0])) {Node node = NodeTask.get(s);node.outdegree++;//出度：->后有元素，即存在依赖node.depend.add(t[1]);//添加->后的元素，即添加依赖项//依赖者->被依赖者}}}TreeMap<String, Node> sortedNodeTask = new TreeMap<>(NodeTask);System.out.println("sortedNodeTask:");for (Node node : sortedNodeTask.values()) {System.out.println(node);}ArrayList<String> Execute = new ArrayList<>();//使用队列进行遍历Queue<String> q = new LinkedList<>();//初始化队列for (Node node : sortedNodeTask.values()) {if (node.outdegree == 0) {q.add(node.name);}}for (String element : q) {System.out.println("1 element:"+element);}//创建函数ArrayList<String>ExecuteOrder = TaskCal(q,Execute,sortedNodeTask,set);//System.out.println(Execute.size()+" "+set.size());if (Execute.size() != set.size()) {System.out.println("图中存在环路，无法完成拓扑排序。");}else {System.out.println("任务的执行顺序为：");for (String s : Execute) {System.out.println(s);}}System.out.println("任务的顺序执行序列为;");for (String s : Execute) {System.out.println(s);}}private static ArrayList<String> TaskCal(Queue<String> q, ArrayList<String> execute, TreeMap<String, Node> sortedNodeTask, Set<String> set) {//先处理无依赖的点，因为无环所以必存在一个无依赖点//入队后，除依赖处理while(!q.isEmpty()){boolean newAdd = false;System.out.println("q队列循环：");String current = q.poll();//移除execute.add(current);//加入已执行队列Node currentNode = sortedNodeTask.get(current);System.out.println("q拿出的currentNode:"+currentNode);//遍历找到依赖于当前节点的任务，移除依赖for (Node node : sortedNodeTask.values()) {System.out.println("sortedNodeTask循环:"+node);System.out.println("current0:"+current);System.out.println("依赖判断0:"+node+"node.depend:"+node.depend);if(node.depend.contains(current)){System.out.println("---------------------------current1:"+current);System.out.println("依赖判断1:"+node+"node.depend:"+node.depend);node.outdegree--;node.depend.remove(current);System.out.println("--------------------------依赖移除后:"+node+"node.depend:"+node.depend);}}for (Node node : sortedNodeTask.values()) {if (node.outdegree == 0&&!q.contains(node.name)&&!execute.contains(node.name)) {//队列检验1for (String element : q) {System.out.println("2 qele:"+element);}q.add(node.name);newAdd = true;//队列检验2for (String element : q) {System.out.println("3 qele:"+element);}}}if (!newAdd&&execute.size()<set.size()&&q.isEmpty()){System.out.println("======================================================字典序处理！");ArrayList<String> tmp = new ArrayList<>(set);for (String key : execute) {tmp.remove(key);}q.add(tmp.get(0));//队列加入未处理字母中的第一个值，按照顺序慢慢处理}for (String element : q) {System.out.println("4 qele:"+element);}}return execute;}public static class Node {String name;int outdegree;ArrayList<String> depend;public Node(String name, int outdegree, ArrayList<String> depend) {this.name = name;this.outdegree = outdegree;this.depend = depend;}public String toString() {return "Node{" +"name='" + name + '\'' +", outdegree=" + outdegree +", depend=" + depend +'}';}}
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

《高性能网站建设指南》阅读笔记_规则6- 将脚本放在底部 [ARC189D] Takahashi is Slime 题解 劳保工具佩戴监测识别摄像机 Nginx性能优化全方案：打造一个高效服务器 音视频入门基础：MPEG2-TS专题（23）——通过FFprobe显示TS流每个packet的信息 六大政府单位指导，“防城港惠民保2024”正式启动

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989