积分商城

最新搜索： xc7a50t stm32f0 usb源码 STM32F103C8T6 aiwa I9300
您现在的位置是：首页 > 技术资料 > 拓扑排序的补充：关键路径与任务调度
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

拓扑排序的补充：关键路径与任务调度

更新时间：2026-10-18 10:01:22 大小：38K 上传用户：潇潇江南查看TA发布的资源 标签：拓扑排序关键路径DAG任务调度最长路径 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

拓扑排序的补充：关键路径与任务调度 一、关键路径问题 1.1 问题定义 在DAG中，每个任务有执行时间，任务间有依赖关系。求完成所有任务的最早时间（即关键路径长度）。 // 任务依赖图（DAG）A(3) → B(2) → C(4) ↘ ↗ D(5) → E(1)// 关键路径 = 最长路径 = A→D→E→C = 3+5+1+4 = 13// 或 A→B→E→C = 3+2+1+4 = 10// 关键路径是13（决定总工期） 1.2 用拓扑排序求解 利用拓扑排序的处理顺序，保证处理某任务时所有前驱已完成。 int criticalPath(int n, int *time, int **graph) { // 1. 拓扑排序 int *inDegree = (int *)calloc(n, sizeof(int)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j]) inDegree[j]++; } } int *queue = (int *)malloc(n * sizeof(int)); int front = 0, rear = 0; for (int i = 0; i < n; i++) { if (inDegree[i] == 0) queue[rear++] = i; } int *topo = (int *)malloc(n * sizeof(int)); int topoCount = 0; while (front < rear) { int u = queue[front++]; topo[topoCount++] = u; for (int v = 0; v < n; v++) { if (graph[u][v]) { inDegree[v]--; if (inDegree[v] == 0)

部分文件列表

文件名 大小
拓扑排序的补充：关键路径与任务调度.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号