拓扑排序例子

手机的相机模块中，图像从传感器到输出JPEG格式图片会经过很多node的处理，这些node构成了一个图像处理的pipeline；其中的有些节点依赖于其他节点的输出，A->B表示B的执行依赖于A，假设每个node的执行时间为A（t）即 node A需要执行t秒，没有以来的node可以并行执行，请编写一个方法任意输入一个有向无环图的pipeline，输出该pipeline执行完需要的最短时间。

输入数据

3,1,2,5,3,1
2,3,4;5;5,6;0;6;0

输出数据

9

拓扑排序

import java.util.*;

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

        String[] timeStr = line1.split(",");
        String[] dep = line2.split(";");
        int len = timeStr.length + 1;
        int[] time = new int[len];
        for (int i = 1; i < len; i++) {
            time[i] = Integer.parseInt(timeStr[i - 1]);
        }

        List<Integer>[] edge = new List[len];
        int[] deg = new int[len];

        edge[0] = new ArrayList<>();
        for (int i = 0; i < dep.length; i++) {
            edge[i+1] = new ArrayList<Integer>();
            String[] e = dep[i].split(",");

            for (int j = 0; j < e.length; j++) {
                int next = Integer.parseInt(e[j]);
                edge[i+1].add(next);
                deg[next]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 1; i < len; i++) {
            if (deg[i] == 0) queue.offer(i);
        }
        int[] dp = new int[len];

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int i = 0; i < edge[node].size(); i++) {
                int nex = edge[node].get(i);
                deg[nex]--;
                dp[nex] = Math.max(dp[nex], dp[node] + time[node]);
                if (deg[nex] == 0) queue.offer(nex);
            }
        }

        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans = Math.max(ans, dp[i] + time[i]);
        }
        System.out.println(ans);
    }
}

赏

谢谢你请我吃糖果

微信