当前位置： 首页 > article >正文

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

article 2024/11/9 5:46:41

一、题目

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[]>() {
            @Override
            public 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)) {
                    //队列检验1
                    q.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[]>() {
            @Override
            public 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)) {
                    //队列检验1
                    for (String element : q) {
                        System.out.println("2 qele:"+element);
                    }
                    q.add(node.name);
                    newAdd = true;
                    //队列检验2
                    for (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 +
                    '}';

        }
    }
}


http://www.kler.cn/a/295002.html

相关文章：

  • OpenCV相机标定与3D重建(1)概述
  • Uniapp全局文件执行顺序详解
  • linux crash使用和环境部署
  • 网页版五子棋——匹配模块（客户端开发）
  • 100种算法【Python版】第56篇——Delaunay三角剖分之增量法
  • printf影响单片机中断速度
  • Elasticsearch - SpringBoot 索引与文档相关demo
  • Spring Boot 部署方案！打包 + Shell 脚本详解
  • 【知识分享】MQTT实战-使用mosquitto客户端连接emqx服务器
  • 【人工智能】Transformers之Pipeline（十五）：总结（summarization）
  • ubuntu上通过openvswitch卸载实现roce over vxlan
  • 橘子学ES实战操作之管道类型Ingest pipelines的基本使用
  • Kubernetes 1.25 containerd 环境部署 SuperMap iManager
  • 【MRI基础】TR 和 TE 时间概念
  • 文心快码前端工程师观点分享：人机协同新模式的探索之路（三）
  • day44-测试平台搭建之前端vue学习-基础4
  • java-redis-雪崩
  • QString如何格式化字符串
  • 3.门锁_STM32_矩阵按键设备实现
  • 手机同时传输USB功能与充电的实现及LDR6500的作用
  • Java爬虫开发：Jsoup库在图片URL提取中的实战应用
  • 使用Node-API进行线程安全开发
  • 枚举和联合体
  • 在生产线打包机中RFID技术的赋能
  • Vue3.5正式发布带来了那些新特性？
  • MMO地图传送